组合算法 -- 二进制模拟

【题目】 给定一个数组，其中元素个数为X，从中选择Y个元素的方法有多少种，并打印出来？（X元素中不含重复元素）

该题目，如果只是求个数，那很容易，高中学排列组合，最基本的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);

}