排列组合算法总结(基于C++实现)
全排列n!
1.1 递归法
设一组数p = {r1, r2, r3, … ,rn}, 全排列为perm(p)，pn = p –{rn}。则perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), … , rnperm(pn)。当n = 1时perm(p} = r1。
如：求{1, 2, 3, 4, 5}的全排列
1、首先看最后两个数4, 5。它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身，从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、4 5
3、 5 3
4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
#include iostream
using namespace std;
void Perm(int start, int end, int a[]) {
--得到全排列的一种情况，输出结果
if (start == end) {
for (int i = 0; i end; i++)
cout a[i] ' ';
cout endl;
for (int i = start; i end; i++) {
swap(a[start], a[i]); --交换
Perm(start + 1, end, a); --分解为子问题a[start+1.,end-1]的全排列
swap(a[i], a[start]); --回溯
int main() {
int i, n, a[10];
while (cin n, n) {
for (i = 0; i n; i++)
a[i] = i + 1;
Perm(0, n, a);
return 0;
C(n,k)，n个数中任取k个数
2.1 递归法
实际上就是在n个数中，标记k个数，然后输出这k个数的过程。使用一个visited数组来记录相应下标的数是否被选中。
#include iostream
using namespace std;
void dfs(int pos, int cnt, int n, int k, int a[],bool visited[]) {
--已标记了k个数，输出结果
if (cnt == k) {
for (int i = 0; i n; i++)
if (visited[i]) cout a[i] ' ';
cout endl;
--处理到最后一个数，直接返回
if (pos == n) return;
--如果a[pos]没有被选中
if (!visited[pos]) {
--选中a[pos]
visited[pos] = true;
--处理在子串a[pos+1, n-1]中取出k-1个数的子问题 dfs(pos + 1, cnt + 1, n, k, a,visited);
visited[pos] = false;
--处理在子串a[pos+1, n-1]中取出k个数的问题
dfs(pos + 1, cnt, n, k, a, visited);
int main() {
int i, n, k;
while (cin n k, n || k)
int *a = new int[n];
bool *visited = new bool[n];
for (i = 0; i n; i++)
a[i] = i + 1;
visited[i] = false;
dfs(0, 0, n, k, a, visited);
delete[] a;
delete[] visited;
getchar();
return 0;
2.2 ‘01’转换法
本程序的思路是开一个数组，其下标表示1到n个数，数组元素的值为1表示其代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的n-m的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。
例如求5中选3的组合：
1 1 1 0 0 --1,2,3
1 1 0 1 0 --1,2,4
1 0 1 1 0 --1,3,4
0 1 1 1 0 --2,3,4
1 1 0 0 1 --1,2,5
1 0 1 0 1 --1,3,5
0 1 1 0 1 --2,3,5
1 0 0 1 1 --1,4,5
0 1 0 1 1 --2,4,5
0 0 1 1 1 --3,4,5
#include iostream
using namespace std;
--输出结果
void printRes(int* a, bool* index, int n) for (int i=0;in;i++)
if (index[i])
cout a[i] " ";
cout endl;
--检查最后k个位置是否已全变成0
bool hasDone(bool* index, int n, int k) for (int i=n-1;i=n-k;i--)
if (!index[i])
return false;
return true;
void Comb(int* a, int n, int k)
bool *index = new bool[n]();
--选中前k个位置
for (int i = 0; i k; i++)
