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

2023-12-11

我想编写一个函数，它接受一个字母数组作为参数，并选择其中的一些字母。

假设您提供一个包含 8 个字母的数组，并希望从中选择 3 个字母。那么你应该得到：

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

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

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

格雷码

An issue that you will come across is of course memory and pretty quickly, you'll have problems by 20 elements in your set -- ²⁰C₃ = 1140. And if you want to iterate over the set it's best to use a modified gray code algorithm so you aren't holding all of them in memory. These generate the next combination from the previous and avoid repetitions. There are many of these for different uses. Do we want to maximize the differences between successive combinations? minimize? et cetera.

一些描述格雷码的原始论文：

一些汉密尔顿路径和最小变化算法
相邻立交组合生成算法

以下是涉及该主题的其他一些论文：

Eades、Hickey、Read相邻互换组合生成算法的高效实现（PDF，带有 Pascal 代码）
组合发电机
组合格雷码综述（后记）
格雷码算法

蔡斯的旋转（算法）

菲利普·J·蔡斯，`算法 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,3,2} = {1,2,3}——我们按字典顺序对它们进行排序。
此方法有一个隐式 0 来启动第一个差异的集合。

字典顺序组合索引 (McCaffrey)

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

The set that maximizes , where .

举个例子：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)

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

The following two algorithms are provided for didactic purposes. They implement an iterator and (a more general) folder overall combinations. They are as fast as possible, having the complexity O(ⁿC_k). The memory consumption is bound by 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

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

combinations