从 n 中返回 k 个元素的所有组合的算法 [英] Algorithm to return all combinations of k elements from n

问题描述

我想编写一个函数，该函数将一组字母作为参数，并选择其中的一些字母.

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

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

返回数组(或单词)，每个数组(或单词)由 3 个字母组成.

解决方案

最大化 ，其中 .

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

(* 这会在取 [k] 个元素时找到 [set] 列表的 [x] 组合 *)让combination_maccaffery 设置k x =(* 最大化函数——最大化 a，即 aCb *)(* 返回最大的 c，其中 c []|我 ->让 max = 最大化 n i x in最大 :: 迭代 n (x - (选择最大 i)) (i-1)在如果 x <0 然后失败并显示错误"别的let idxs = iterate (List.length set) x k inList.map (List.nth set) (List.sort(-) idxs)

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

以下两种算法用于教学目的.它们实现了迭代器和(更通用的)文件夹整体组合.它们尽可能快，复杂度为 O(ⁿC_k).内存消耗受k约束.

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

let iter_combs n k f =让rec iter v s j =如果 j = k 则 f velse for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in迭代器 [] 0 0

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

let fold_combs n k f x =让 rec 循环 i s c x =如果我＜n 那么循环 (i+1) s c @@让 c = i::c and s = s + 1 and i = i + 1 in如果 s 

I want to write a function that takes an array of letters as an argument and a number of those letters to select.

Say you provide an array of 8 letters and want to select 3 letters from that. Then you should get:

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

Arrays (or words) in return consisting of 3 letters each.

解决方案

Art of Computer Programming Volume 4: Fascicle 3 has a ton of these that might fit your particular situation better than how I describe.

Gray Codes

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.

Some of the original papers describing gray codes:

1. Some Hamilton Paths and a Minimal Change Algorithm
2. Adjacent Interchange Combination Generation Algorithm

Here are some other papers covering the topic:

1. An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm (PDF, with code in Pascal)
2. Combination Generators
3. Survey of Combinatorial Gray Codes (PostScript)
4. An Algorithm for Gray Codes

Chase's Twiddle (algorithm)

Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects' (1970)

The algorithm in C...

Index of Combinations in Lexicographical Order (Buckles Algorithm 515)

You can also reference a combination by its index (in lexicographical order). Realizing that the index should be some amount of change from right to left based on the index we can construct something that should recover a combination.

So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change but accounts for more change since it's in the second place (proportional to the number of elements in the original set).

The method I've described is a deconstruction, as it seems, from set to the index, we need to do the reverse – which is much trickier. This is how Buckles solves the problem. I wrote some C to compute them, with minor changes – I used the index of the sets rather than a number range to represent the set, so we are always working from 0...n. Note:

1. Since combinations are unordered, {1,3,2} = {1,2,3} --we order them to be lexicographical.
2. This method has an implicit 0 to start the set for the first difference.

Index of Combinations in Lexicographical Order (McCaffrey)

There is another way:, its concept is easier to grasp and program but it's without the optimizations of Buckles. Fortunately, it also does not produce duplicate combinations:

The set that maximizes , where .

For an example: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). So, the 27th lexicographical combination of four things is: {1,2,5,6}, those are the indexes of whatever set you want to look at. Example below (OCaml), requires choose function, left to reader:

(* 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)

A small and simple combinations iterator

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.

We will start with the iterator, which will call a user provided function for each combination

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

A more general version will call the user provided function along with the state variable, starting from the initial state. Since we need to pass the state between different states we won't use the for-loop, but instead, use recursion,

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

这篇关于从 n 中返回 k 个元素的所有组合的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！