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

问题描述

我想编写一个函数，它的字母数组作为参数和一些这些字母的选择。

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

假设你提供的8个字母的排列，并要选择从3个字母。然后，你应该：

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

阵列（或词）的回报，包括3个字母每

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

推荐答案

艺术计算机编程卷4：3分册有一吨的这些，可能更适合你的特殊情况不是我该怎么形容

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

这是你会遇到的一个问题，当然是内存和pretty的快，你会在您所设定的20个元素有问题 - ²⁰ C _{3 = 1140如果你想遍历集合，最好使用修改过的灰色code算法，这样你就不会拿着所有的人都在内存中。有许多这样的，对于不同的用途，根据元素的距离。难道我们要最大限度地连续应用之间的区别是什么？最小化？等等。}

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. There are many of these, and for different uses, based on the distance of elements. Do we want to maximize the differences between successive applications? minimize? et cetera.

部分的原始论文描述灰色codeS：

Some of the original papers describing gray codes:

1. 一些哈密尔顿路径和变化最小算法
2. <一个href="http://portal.acm.org/citation.cfm?id=49203&jmp=indexterms&coll=GUIDE&dl=GUIDE&CFID=81503149&CFTOKEN=96444237">Adjacent交换组合生成算法

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

下面是一些其他的文件，内容涵盖主题：

Here are some other papers covering the topic:

1. 一种高效的参加者填写，希基的实施，了解邻近立交组合生成算法（PDF，与code帕斯卡）
2. 组合发电机
3. 的组合灰色codeS 调查中（PostScript）
4. 算法的灰度codeS

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

菲利普Ĵ大通，`算法382：M的组合出N个对象（1970年）

Chase's Twiddle (algorithm)

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

在C算法 ...

您还可以通过它的索引引用的组合（以字典顺序），实现该指标应该从正确的变化一定量至左的基础上的指数。

You can also reference a combination by it's index (in lexicographical order), realizing that the index should be some amount of change from right to left based on the index.

因此​​，我们有一个集合{1,2,3,4,5,6} ...当我们希望三个元件{1,2,3}，我们可以说，该元件之间的差别是一个整体，在订购。 {1,2,4}有一个变化，是字典序数2。所以在最后的地方占的词典式排序一个改变'改变'的数量。第二，有一个改变{1,3,4}有一个变化，但占更多的变化，因为它是排在第二位。

So, we have a set {1,2,3,4,5,6}... when we want three elements {1,2,3} we can say that the difference between the elements is one and in order. {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.

我所描述的方法是一种解构，因为它似乎，从设定为索引，我们需要做的，可呈现是非常棘手的相反。这是怎么扣解决了这个问题。我写了一些 C至计算它们，与其他小的变化 - 我用套的索引而不是一个数字范围内重新present设定的，所以我们总是从0工作... N。 注：

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 other minor changes --I used the index of the sets rather then a number range to represent the set, so we are always working from 0...n. Note:

1. 由于组合是无序的，{1,3,2} = {1,2,3} - 我们责令其是辞书。
2. 这个方法有一个隐0开始设定为第一差值。

有另一种方式：，它的概念是比较容易把握和程序，但它是不扣的优化。幸运的是，它不会产生重复的组合：

Index of Combinations in Lexicographical Order (McCaffrey)

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

集合，$ x_k ... X_1 \中\ mathbb {N} $，最大限度地提高$ I = C（X_1，K）+ C（X_2，K-1）+ ... C（x_k，1） $，其中$ C（N，R）= {N \选择R} $。

The set, $x_k...x_1 \in \mathbb{N}$ that maximizes $i = C(x_1,k) + C(x_2,k-1) + ... C(x_k,1)$, where $C(n,r) = {n \choose r}$.

有关的例子：$ 27 = C（6,4）+ C（5,3）+ C（2,2）+ C（1,1）$。所以，四样东西27日辞书组合是：{1,2,5,6}，这些都是任何设置你想要看的指标。下面的示例（ocaml的），需要选函数，留给读者：

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)

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