组合算法 -凯发app官方网站

该题目，如果只是求个数，那很容易，高中学排列组合，最基本的cxy。但要打印出来就不容易了。
网上有很多关于递归的实现，本文不表。递归实现在于效率问题，如果数据较大，还存在栈溢出等问题。
本文主要介绍一种2进制模拟的方法。网上也有很多讲解，但个人觉得不是很清晰，所有重新总结一遍。

先看一个abc的组合，abc三个元素所有组合包括：
{a， b，c，ab， ac， bc，abc}，总个数为: 2^3 - 1
但看一个组合a，它可以描述为：在abc三个元素中选择了a，bc元素均不选择
ab组合可以描述为：在abc三个元素中，选择了ab，c元素不选择
如果，我们用一个index数组（bit位）来表示各个元素在某一个组合中被选择的情况，那么会有：
000： 一个元素没选择
001：c
010：b
011：bc
100：a
101：ac
110：ab
111：abc
可以看出，一个数组的全组合，恰好对应了2^(元素个数)这些数的二进制表达式！

考虑如果是从abcd中任意选中2个字母的组合情况：
0011， 选中cd
0101， 选中bd
0110， 选中bc
1001， 选中ad
1010， 选中ac
1100， 选中ab

那么，对于任意cxy，所有组合情况为
00...0011...11 -- 11...1100...00（共有x位，其中包含1的个数为y）
我们从00...0011...11开始，逐步增大，直到11...1100...00，就是cxy所有的组合了。

那么，问题来了，如何增大？
在保证‘1’的个数不变得情况下，将从右向左第一个‘01’变成‘10’该序列增大（比如0111 --> 1011）；
注意，类似‘0110’增大的下一个序列是‘1001’而非‘1010’，这有点像进位后的反转。
对于任意0...01...0 序列，下一个序列是0...10...0/1...1， 即当最右边的位为0时，将从右至左第一个‘01’序列反转为‘10’，同时将其右边所有的1移至最右边。


分析至此，该算法和实现已经比较清楚明了了：
void printfcombination(int list[], int index[], int len)
{
int i; 
for ( i = 1; i <= len; i )
{
if (index[i])
printf("%d", list[i-1]);
}
printf("\n");
return ;
}

int combination(int list[], int nx, int ny)
{
int *pindex = null;
int carry = 0;
int i,j,k;

pindex = (int *)malloc(sizeof(int) * (nx 1)); // pindex[0] not use
if (null == pindex)
return -1;

memset(pindex, 0, sizeof(int) *(nx 1));
for (i = 0; i < ny; i )
{
pindex[nx - i] = 1;
}


do 
{
printfcombination(list, pindex, nx);

// 所有1都集中到左边，结束
for (i = 1;  i <= ny; i )
{
if (!pindex[i])
break;
}
if (i > ny)
break;

for (i = nx; i > 1; i--)
{
carry = (pindex[nx] == 0); // 类似进位发生


if (pindex[i] == 1 && pindex[i - 1] == 0) // 增大序列
{
pindex[i - 1] = 1;
pindex[i] = 0;

if (carry) // 类似进位反转, 把i右边的所有1移至最右边
{
for(j = i 1, k = nx; j < k; j )
{
if (pindex[j])
{
while(pindex[k])
k--;

if (j < k)
{
pindex[k--] = 1;
pindex[j] = 0;

}
}
}
}
break;
}
}

} while(1);
}


void main()
{
int list[] = {1,2,3,4,5,6,7};


combination(list, 7,3);

}