从n返回k个元素的所有组合的算法

Question

我想编写一个函数，该函数以字母数组作为参数，并选择多个字母。

假设您提供8个字母的数组，并希望从中选择3个字母。然后您将获得：

8! / ((8 - 3)! * 3!) = 56

返回由3个字母组成的数组（或单词）。

Answer 1

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

蔡斯的小提琴（算法）

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

在C算法 …

词典顺序的组合索引（Buckles算法515）

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

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

我描述的方法似乎是一种解构，从设置到索引，我们需要做相反的事情–这要复杂得多。这就是扣具解决问题的方式。我写了一些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