c++ - 生成从 1 到 n 的 k 个数字的 nCk 组合的程序

Question

我的函数定义看起来像 nxt_comb[] = 组合(comb[1:k],n)

此函数应给出输入组合comb(数组)之后的下一个组合。 comb 的 n 元素取值从 1 到 n。

例子:

• 如果函数被调用为 a = Combination([1,3,4,6],8)，则 a = [1,3,4,7]
• 如果函数调用为 a = Combination([1,3,4,8],8)，则 a = [1,3,5,6]
• 如果函数被调用为 a = Combination([1,3,7,8],8)，则 a = [1,4,5,6]
• 如果函数被调用为 a = Combination([3,6,7,8],8)，则 a = [4,5,6,7]

输入的组合永远不会是最后的组合。也就是说，在上述情况下，输入永远不会是 [5,6,7,8]。

此外，如果输入全为零，函数必须输出第一个组合，即 [1,2,....,k]。

编辑:我正在寻找的是逻辑。可以使用 C/C++ 或 MATLAB 实现。

Answer 1

撇开关于从全 0 开始的最后一个要求，这是一个微不足道的额外检查，算法是:

1. 通过向后搜索，找到最大的 i这样 comb[i]<i+n-k (使用基于 1 的索引；如果您使用的是 C，请进行调整)。如果找不到，则说明您处于最后一个组合。

2. 递增 comb[i]，然后从 j = i+1 开始工作最多 k , 设置 comb[j]至 comb[j-i]+1