计算机编程艺术第 4 卷：分册
3有很多这些内容可能比我描述的更适合您的特定情况。

格雷码

您将遇到的一个问题当然是内存，而且很快，您的集合中的 20 个元素就会出现问题 - 20 C 3 =
1140。如果您想遍历集合，最好使用修改后的灰色代码算法，因此您不会将所有这些都保存在内存中。这些从前一个组合生成下一个组合并避免重复。其中有许多用于不同的用途。我们想最大化连续组合之间的差异吗？最小化？等等。

Chase’s Twiddle (算法)

Phillip J Chase，“算法 382：N 个对象中 M
个的组合”（1970 年）

C中的算法…

按字典顺序排列的组合索引（Buckles 算法 515）

您还可以通过索引（按字典顺序）引用组合。意识到索引应该是基于索引从右到左的一些变化，我们可以构造一些应该恢复组合的东西。

所以，我们有一个集合 {1,2,3,4,5,6}… 我们想要三个元素。假设 {1,2,3} 我们可以说元素之间的差异是一个且有序且最小。{1,2,4}
有一个变化，按字典顺序排列为 2。因此，最后一个位置的“变化”数说明了字典顺序的一个变化。第二位，有一个变化 {1,3,4}
有一个变化，但由于它位于第二位（与原始集合中的元素数量成正比），所以变化更多。

我描述的方法是一种解构，看起来，从集合到索引，我们需要做相反的——这要复杂得多。这就是Buckles解决问题的方法。我写了一些C
来计算它们，稍作改动——我使用集合的索引而不是数字范围来表示集合，所以我们总是从 0…n 开始工作。笔记：

1. 由于组合是无序的，{1,3,2} = {1,2,3}——我们按字典顺序排列它们。
2. 此方法有一个隐含的 0 来启动第一个差异的集合。

按字典顺序排列的组合索引 (McCaffrey)

还有另一种方式：它的概念更容易掌握和编程，但没有 Buckles 的优化。幸运的是，它也不会产生重复的组合：

最大化的集合，其中。

举个例子：27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)。所以，第 27
个字典组合的四件事是：{1,2,5,6}，这些是您想要查看的任何集合的索引。下面的示例（OCaml），需要choose函数，留给读者：

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

一个小而简单的组合迭代器

出于教学目的，提供了以下两种算法。他们实现了迭代器和（更通用的）文件夹整体组合。它们尽可能快，复杂度为 O( n C k )。内存消耗受k.

我们将从迭代器开始，它将为每个组合调用用户提供的函数

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

更通用的版本将调用用户提供的函数以及状态变量，从初始状态开始。由于我们需要在不同状态之间传递状态，我们不会使用 for 循环，而是使用递归，

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x