小编典典

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

algorithm

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

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

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

返回由3个字母组成的数组(或单词)。


阅读 18

收藏
2020-07-31

共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
```

2020-07-31

回答这个问题

Nothing to preview