algorithm - 按需算法返回 n 中 k 元素的连续组合

Question

This post展示了如何编写一种算法，一次吐出 n 中 k 元素的所有组合，避免排列。但是如何编写一种算法，按需给出下一个组合(显然，无需预先计算和存储它们)？它将使用有序的符号集 n 和整数 k 进行初始化，然后调用以返回下一个组合。

伪代码或良好的英语叙述对我的目的来说是很好的——除了 Perl 和 C 以及一点 Java 之外，我并不流利。

Answer 1

原文

(跳到下面的更新)

---

1. 让我们假设 n元素是整数 1..n .
2. 代表每个 k -按递增顺序组合(此表示消除了 k -组合内的排列。)
3. 现在考虑 k 组合(n 个元素)之间的字典顺序。换句话说，{i_1..i_k} < {j_1..j_k}如果存在索引 t这样
   • i_s = j_s对于所有 s < t和
   • i_t < j_t .
4. 如果{i_1..i_k}是 k -组合，定义next{i_1..i_k}成为下一个元素 w.r.t.字典顺序。

这里是如何计算next{i_1..i_k} :

• 找到最大的索引 r这样 i_r + 1 < i_{r+1}
• 如果没有索引满足这个条件并且i_k < n , 设置 r := k
• 如果以上条件都不满足，则没有下一个(k组合等于{n-k+1, n-k+2,... ,n})
• 如果r满足第一个条件，设置next成为{i_1, ..., i_{r-1}, i_r + 1, i_{r+1}, ..., i_k}
• 如果r = k (第二个条件)，设置next := {i_1, ..., i_{k-1}, i_k + 1}.

---

更新(非常感谢@rici 改进了解决方案)

1. 让我们假设 n元素是整数 1..n .
2. 代表每个 k -按递增顺序组合(此表示消除了 k -组合内的排列。)
3. 现在考虑 k 组合(n 个元素)之间的字典顺序。换句话说，{i_1..i_k} < {j_1..j_k}如果存在索引 t这样
   • i_s = j_s对于所有 s < t和
   • i_t < j_t .
4. 如果{i_1..i_k}是 k -组合，定义next{i_1..i_k}成为下一个元素 w.r.t.字典顺序。
5. 请注意，此订单中最小的 k -组合是{1..k}和最大的{n-k+1, n-k+2,... ,n} .

这里是如何计算next{i_1..i_k}

• 找到最大的索引 r这样 i_r可以增加 1 .
• 增加索引 r 处的值并使用从 i_r + 2 开始的连续值重置以下元素.
• 重复直到没有位置可以增加。

更准确地说:

• 如果i_k < n , 递增 i_k通过 1 (即，将 i_k 替换为 i_k + 1 )
• 如果i_k = n , 找到最大的索引 r这样 i_r + 1 < i_{r+1} .然后增加 i_r通过 1并将以下位置重置为 {i_r + 2, i_r + 3, ..., i_r + k + 1 - r}
• 重复直到到达 {n-k+1, n-k+2,... ,n}

请注意该算法的递归特性:每次递增最低有效位置时，尾部都会重置为以刚刚递增的值开始的字典序最小序列。

---

Smalltalk 代码

SequenceableCollection >> #nextChoiceFrom: n
    | next k r ar |
    k := self size.
    (self at: 1) = (n - k + 1) ifTrue: [^nil].
    next := self shallowCopy.
    r := (self at: k) = n
      ifTrue: [(1 to: k-1) findLast: [:i | (self at: i) + 1 < (self at: i+1)]]
      ifFalse: [k].
    ar := self at: r.
    r to: k do: [:i | 
      ar := ar + 1.
      next at: i put: ar].
    ^next