为什么要写这篇文章
排列组合问题在数学中占有重要的地位，其与概率论也有密切的关系。而且排列组合问题大量出现在求职笔试面试中，同时编写排列组合问题，对于学习理解递归思想也是很有帮助的。在此总结一下排列组合的各种问法和变形！
首先，总结一下以往常常出现的排列组合题目，其对象一般都是整形数组或者字符类型，输入数据一般分为两类：有重复和无重复，按照输出数据分类，也可以分为有重复和无重复，而且排列问题偶尔也会考非递归求解。
排列篇之输入数据无重复
1. 输出数组a的全排列(不可重复取)
如a={1,2,3}。输出123，132，213，231，312，321
算法思想：假设输入数据中有n个不重复的数据，第一个元素可以有n中情况，第二个元素有n-1中情况，即可得n个不重复的数据有n!种全排列。用递归法求解该问题，第一个元素从1-n中任取一个，第二个元素从剩下的2-n中任取一个，依次下去直到最后一个元素，即可求得该全排列，详见下面的算法。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation2(int a[], int index, int n){
if (index == n){
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
return;
}
for (int i = index; i < n; ++i){
swap(a[index], a[i]);
permutation2(a, index + 1, n);
swap(a[index], a[i]);
}
}
void permutation(int a[], int n){
permutation2(a, 0, n);
}
int main()
{
int a[] = { 1, 5, 9 };
permutation(a, sizeof(a)/sizeof(a[0]));
return 0;
}
2. 输出数组a的全排列(可重复取)
如a={1,2}。输出11,12,21,22。
算法思想：假设数组中有n个元素，则可重复取的话，有n^n种情况，即每个元素，都有n种选取选择。对于第一个元素，可以从1-n中选取一个，对于第二个元素，同样从1-n中选取一个，一直到第n个元素，详见下面的算法。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <utility>
using namespace std;
void permutation2(int a[], int b[], int index, int n){
if (index == n){
for (int i = 0; i < n; ++i)
printf("%d ", b[i]);
printf("\n");
return;
}
for (int i = 0; i < n; ++i){
b[index] = a[i];
permutation2(a, b, index + 1, n);
}
}
void permutation(int a[], int n){
int *b = new int[n];
permutation2(a, b, 0, n);
delete []b;
}
int main()
{
int a[] = { 1,5,9 };
permutation(a, sizeof(a)/sizeof(a[0]));
return 0;
}
3. 输出数组a的全排列(非递归)
如a={1,2,3}。输出123,132,213,231,312,321
全排列的非递归算法也不唯一，这里列出一个最常用的按字典序排列的非递归算法。
算法思想：首先对数组a进行排序，然后依次求解出按字典序的下一个排列，这里可以采用STL库中的next_permutation函数。当然也可以自己实现next_permutation函数，leetcode上有一道这样的练习题next-permutation。
代码如下：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation(int a[], int n){
sort(a, a+n);
do {
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
} while (next_permutation(a, a + n));
}
int main()
{
int a[] = { 1, 5, 9 };
permutation(a, sizeof(a) / sizeof(a[0]));
return 0;
}
4. 输出从含n个数组a中取m个数的所有排列
如a={1,2,3}，m=3, n=2输出12，21，13，31，23，32.
算法思想：首先从n个元素中选取m个，然后对这m个元素进行全排列。 从n个元素中选取m个元素，对于每个元素，有选择和不选择两种情况，用一个额外的数组记录选择的m个元素，然后对这m个元素进行全排列即可。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation3(int b[], int index, int m){
if (index == m){
for (int i = 0; i < m; ++i)
printf("%d ", b[i]);
printf("\n");
return;
}
for (int i = index; i < m; ++i){
swap(b[index], b[i]);
permutation3(b, index + 1, m);
swap(b[index], b[i]);
}
}
void permutation2(int a[], int b[], int start1, int m, int start2, int n){
if (start1 == m){
permutation3(b, 0, m);
return;
}
if (m - start1 > n - start2) return;
if (m < start1) return;
if (n < start2) return;
permutation2(a, b, start1, m, start2+1, n);
b[start1] = a[start2];
permutation2(a, b, start1+1, m, start2+1, n);
}
void permutation(int a[], int m, int n){
int *b = new int[m];
permutation2(a, b, 0, m, 0, n);
delete[] b;
}
int main()
{
int a[] = { 1, 5, 9, 11};
int m = 3;
permutation(a, m, sizeof(a) / sizeof(a[0]));
return 0;
}
排列篇之输入数据有重复
例如a={1,3,2,3}，其中数字3出现了两次，用上面的方法进行求解会造成重复输出。
5. 输出含重复元素数组的全排列(递归)
例如a={1,3,2,3}，则其全排列为1233,1323,3123,1332,3132,2133,2313,3213,2331,3231,3312,3321
算法分析： 数组a中有n个元素，元素可表述为： a1,a1,...a1, a2,a2,...a2,.......,am,am,...am。则可以证明不重复的排列种类的数目为：n!/(n1!*n2!*...*nm!)。将这n个元素做全排列，这里只要限制将要选择的元素大小必须大于原来已经选择的元素大小即可达到目标，详见程序(含注释)。
#include <stdio.h>
#define N 5
void arrange(int rec[], int used[], int depth);
void write(int rec[], int maxdepth);
//int a[N] = { 1, 1, 5, 5, 9 }; //这些值必须升序排列且大于0
int a[] = { 1, 1, 1, 5, 5 };
int count = 0;
int main()
{
int rec[N + 1] = { 0 }, used[N + 1] = { 0 };
arrange(rec, used, 0);
printf("\ncount=%d ", count);
getchar();
return 0;
}
void write(int rec[])
{
int i;
for (i = 0; i <N; i++)
printf("%d ", a[rec[i]]);
printf("\n");
count++;
}
void arrange(int rec[], int used[], int depth)
{
int i, found_num;
if (depth>= N) write(rec); //找到了一个可行解，输出
else
{
found_num = 0; //增加这个变量记录原来本结点存储的数字
for (i = 0; i <N; i++) // 搜索该结点的孩子结点
{//如果该下标在前面还没有使用过，且该下标所指示的数字比
//原先所放置的数字要大，则是一个部分解
if (used[i] == 0 && a[i]> found_num)
{
rec[depth] = i; //记录下该结点放置的下标
found_num = a[i]; //记录下本结点存放的数字
used[i] = 1; // 标记该下标已经被使用
arrange(rec, used, depth + 1); // 扩展，进入孩子结点继续搜索
used[i] = 0; //退回来后要清除本结点所记录下标的使用记录
}
}
}
}
另一种算法：我们改进一下1的算法，在for中判断是否有包含重复元素，也就是index和i之间是否有和a[i]相等的值，比如对于2313这个数列，当index=0(a[index] = 2),i=3(a[i] = 3)的时候,如果要交换这两个数变成3312的话就是计算重复了，因为它们之间有1个3，当i=1的时候，它已经转换过3312了。所以加一个函数判断中间有没有包含重复元素，如有没有重复元素，再做交换；代码如下所示：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int total = 0;
bool contains(int a[], int index, int i){
for (int k = index; k < i; ++k)
if (a[k] == a[i])
return true;
return false;
}
void permutation2(int a[], int index, int n){
if (index == n){
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
total++;
return;
}
for (int i = index; i < n; ++i){
if (contains(a, index, i))
continue;
swap(a[index], a[i]);
permutation2(a, index + 1, n);
swap(a[index], a[i]);
}
}
void permutation(int a[], int n){
permutation2(a, 0, n);
}
int main()
{
int a[] = { 1, 5, 5, 5, 9, 9 };
total = 0;
permutation(a, sizeof(a) / sizeof(a[0]));
printf("total: %d\n", total);
return 0;
}
6. 输出含重复元素数组的全排列(非递归)
与算法3相同，使用next_permutation函数即可！
组合篇之输入数据无重复
1. 输入一个数组a和target，从数列数组a中任取几个数，使其和等于target，要求将其中所有的可能组合列出来（不可重复取）。
算法分析：这是一个典型的01背包问题， 对于数组中的没一个数，有取和不取两种方式，因为需要输出所有的情况，所以此处用回溯，不用动规求解。
动规求解数组a中任取几个数，其和为target的数目：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int solve(int a[], int n, int target)
{
int *tmp = new int[target + 1];
memset(tmp, 0, (target + 1)*sizeof(*tmp));
for (int i = 0; i < n; ++i){
if (a[i]>target) break;
for (int j = target - a[i]; j >= 1; --j){
if (tmp[j] > 0)
tmp[j + a[i]]++;
}
tmp[a[i]]++;
}
int x = tmp[target];
delete[] tmp;
return x;
}
int main()
{
int target;
int a[] = { 1, 3, 4, 6, 7 };
sort(a, a + sizeof(a) / sizeof(a[0]));
while (cin >> target){
cout << "total: " << solve(a, sizeof(a)/sizeof(a[0]), target) << endl;
}
return 0;
}
回溯法求出所有满足要求的情况：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
void permutation(int a[], int index, int n, int b[], int num, int target)
{//回溯求解所有的情况
if (target == 0){
for (int i = 0; i < num; ++i)
printf("%d ", b[i]);
printf("\n");
return;
}
if (index >= n) return;
permutation(a, index+1, n, b, num, target);
b[num] = a[index];
permutation(a, index + 1, n, b, num+1, target-a[index]);
}
int main()
{
int target;
int a[] = { 1, 3, 4, 6, 7 };
int *b = new int[sizeof(a) / sizeof(a[0])];
sort(a, a + sizeof(a) / sizeof(a[0]));
while (cin >> target){
permutation(a, 0, sizeof(a) / sizeof(a[0]), b, 0, target);
}
delete[] b;
return 0;
}
2. 输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数，使其和等于 m ,要求将其中所有的可能组合列出来（可重复取）
算法分析： 计算出每个元素可以加入的次数，分别为A,B,C....， 则第一个元素可加入0A次，第二个元素加入0B次，一直递归下去
详见下面的代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
void permutation(int a[], int index, int n, vector<int> vec, int target)
{//回溯求解所有的情况
if (target == 0){
for (auto it = vec.begin(); it != vec.end(); ++it)
cout << *it << " ";
printf("\n");
return;
}
if (index >= n) return;
int t = target / a[index];
for (int i = 0; i <= t; ++i){
permutation(a, index+1, n, vec, target);
vec.push_back(a[index]);
target = target - a[index];
}
}
int main()
{
int target;
int a[] = { 1, 3, 4, 6, 7 };
vector<int> vec;
sort(a, a + sizeof(a) / sizeof(a[0]));
while (cin >> target){
permutation(a, 0, sizeof(a) / sizeof(a[0]), vec, target);
}
return 0;
}
上面所述已经涉及到了排列组合常见的问题，其他的情况详见参考资料！
网友评论