如何在没有递归的情况下找到给定N个元素集的K个元素的所有组合

Question

我试图用C编程，但它对我来说太深了…

我研究了一篇相关论文">Skordalakis，Papakonstantinou"一种用于可变数量嵌套回路的控制结构"；，我尝试过转换C中提出的流程图，但这在结构化编程中是不可能的。这个想法应该是这样的：

b1 = 1; 

for (m = 1 ; m <= K ; m++) {
for (i[m] = b[m] ; i[m] <= n; i[m]++) {
if ( m < K ) {
a[m] = i[m];
b[m+1] = i[m] + 1;
break;
}
a[m] = i[m];
if ( i[m] < n ){
i[m] = i[m] + 1;
m = m - 1;
continue;
}
}
}

i是每个循环(数组(的控制变量，b是每个循环的起始参数(再次是数组(，a数组保存每个组合。我看到了一些类似问题的解决方案，它们使用布尔流控制变量(也在论文中提出(。

有人能提供建议吗？

Answer 1

这是我刚刚想到的一个可能的解决方案。

给定一组n个元素，我们可以将k个元素的选择表示为二进制数。

例如，当n=6和k=2时，我们可以选择第二个和最后一个元素：

010001

我们可以列举n个数字的二进制数，并丢弃那些没有k个数字的数字。

例如，在n=4和k=2的情况下。

0000
0001
0010
0011 ✓
0100
0101 ✓
0110 ✓
0111
1000
1001 ✓
1010 ✓
1011
1100 ✓
1101
1111

但浪费的迭代太多了。

所以我想做一个序列，只产生k为1的数字。例如，当n=6和k=3时，我会列举如下：

1 1 1 0 0 0 
1 1 0 1 0 0 
1 0 1 1 0 0 
0 1 1 1 0 0 
1 1 0 0 1 0 
1 0 1 0 1 0 
0 1 1 0 1 0 
1 0 0 1 1 0 
0 1 0 1 1 0 
0 0 1 1 1 0 
1 1 0 0 0 1 
1 0 1 0 0 1 
0 1 1 0 0 1 
1 0 0 1 0 1 
0 1 0 1 0 1 
0 0 1 1 0 1 
1 0 0 0 1 1 
0 1 0 0 1 1 
0 0 1 0 1 1 
0 0 0 1 1 1 

如果你花点时间思考一下，你就会开始理解算法是如何工作的。

我们在开始时用所有(k(个1初始化数组。我们正在以某种方式将它们转移到最后，我们一直坚持到所有的都结束。

尝试在不考虑解决方案的情况下自行实现：https://ideone.com/aY9YBl