时间戳

首页 > 解决方案 > 如何在没有递归的情况下找到给定 N 元素集的 K 元素的所有组合？

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

问题描述

我试图用 C 编写一些东西，但它对我来说太深了……</p>

我研究了一篇相关论文“ A CONTROL STRUCTURE FOR A VARIABLE NUMBER OF NESTED LOOPS, 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 数组包含每个组合。我已经看到了一些类似问题的解决方案，它们使用布尔流控制变量（也在论文中提出）。

有人可以建议吗？

标签： c

解决方案

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

给定一组 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 个数字的序列。例如，在 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) 个来初始化数组。我们正在以某种方式将它们移到最后，并且我们继续前进，直到所有的都结束。

尝试自己实施而不查看解决方案：https ://ideone.com/aY9YBl

推荐阅读