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

Question

我想编写一个函数，该函数接受字母数组作为参数以及要选择的这些字母的数量。

比如你提供了一个由8个字母组成的数组，并希望从中选择3个字母。那么你应该得到：

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

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

- IQue

---

编程语言有偏好吗？ - Jonathan Tran

你希望如何处理重复的字母？ - wcm

在PHP中，以下代码应该可以解决问题：https://dev59.com/D2855IYBdhLWcg3wilCD#8880362 - Kemal Dağ

@wcm 我在这里找不到处理重复字母的解决方案。我回答了一个需要重复（并需要C ++）的问题：https://dev59.com/ll0a5IYBdhLWcg3wxbHm - Jonathan Mee

这里有一篇简明的文章，提供了一个看起来很高效的C#实现：https://msdn.microsoft.com/zh-cn/library/aa289166(v=vs.71).aspx - Angelo

Answer 1

《计算机程序设计艺术》第4卷：分册3中有很多可能比我描述的更适合你特定情况的内容。

格雷码

当然，你会遇到一个问题，那就是内存。在你的集合中，当元素数量达到20个时，很快就会出现问题——²⁰C₃ = 1140。如果你想遍历整个集合，最好使用一种修改过的格雷码算法，这样你就不需要将所有组合都保存在内存中。这些算法可以从前一个组合生成下一个组合，并避免重复。针对不同的用途，有很多种格雷码算法可供选择。我们是想最大化连续组合之间的差异吗？还是最小化？等等。

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

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

1. 一些哈密顿路径和最小变换算法 2. 相邻交换组合生成算法 希望对您有所帮助。

1. 一个高效的Eades, Hickey, Read相邻交换组合生成算法的实现（带有Pascal代码的PDF文件）
2. 组合生成器
3. 组合格雷码综述（PostScript格式）
4. 格雷码算法

Chase的Twiddle算法

Phillip J Chase, 《{{link5:算法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. 由于组合是无序的，{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(ⁿ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

- nlucaroni

---

是的，它会 Thomas。它对数组中的数据是不可知的。如果需要的话，您可以始终首先过滤掉重复项，或选择另一个算法。 - nlucaroni

很棒的回答。您能否为每个算法提供运行时间和内存分析摘要？ - uncaught_exceptions

相当不错的回答。20C3是1140，感叹号在这里很容易让人混淆成阶乘，而阶乘并没有进入找到组合的公式中。因此，我将删除感叹号。 - CashCow

Chase的算法比其他算法更加复杂，但它有一个额外的好处，即每个连续的组合与前一个仅相差一个元素。如果可以利用前一个组合的部分工作来加快对每个组合执行的工作，则这可能非常有用。 - Eyal

很遗憾，很多引用都被设置了付费墙。是否有可能包含非付费链接或者包含可引用的片段呢？ - Terrance

Answer 2

在C#中：

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

使用方法：

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

结果：

123
124
125
134
135
145
234
235
245
345

- user230950

---

这个解决方案对于“小”集合效果良好，但对于更大的集合会使用一些内存。 - Artur Carvalho

虽然与此无关，但这段代码非常有趣/易读，我想知道哪个版本的C#有这些结构/方法？（我只用过C# v1.0，而且不是很多）。 - LBarret

绝对优雅，但IEnumerable将被枚举很多次。如果这是由一些重要操作支持的... - Drew Noakes

因为它是一个扩展方法，所以您的使用代码可以这样写：var result = new[] { 1, 2, 3, 4, 5 }.Combinations(3);。 - Dave Cousineau

你能提供使用递归循环的精确非 Linq 版本来查询吗？ - irfandar

Answer 3

Java简短解决方案：

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

结果将会是

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

- user935714

---

这似乎是O(n^3)的对吧? 我想知道有没有更快的算法来完成这个任务。 - LZH

我正在使用20选10进行工作，这似乎对我来说足够快（少于1秒）。 - demongolem

@NanoHead，你错了。这是不重复的组合。 而你的情况是有重复的。 - Jakub S.

这段代码应该更容易在网络上找到... 这正是我正在寻找的！ - Manuel S.

我喜欢这段代码！！谢谢！！我只想知道，如果我想要将3个元素分组而不是4个，那么时间复杂度会变成O(n^4)吗？ - Nicolas

Answer 4

我可以介绍一下我用Python写的递归解法吗？

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

使用示例：

>>> len(list(choose_iter("abcdefgh",3)))
56

我喜欢它的简洁性。

- Claudiu

---

使用len(tuple(itertools.combinations('abcdefgh',3)))在Python中可以用更少的代码实现相同的功能。 - hgus1294

@hgus1294 的确如此，但那将是作弊。Op 请求的是算法，而不是与特定编程语言相关的“魔法”方法。 - MestreLion

严格来说，第一个循环范围不应该是for i in xrange(len(elements) - length + 1):吗？虽然在Python中超出切片索引会被优雅地处理，但这才是正确的算法。 - Stephan Dollberg

Answer 5

假设您的字母数组看起来像这样：“ABCDEFGH”。您有三个索引（i，j，k），指示您将使用哪些字母来构成当前单词。您从以下位置开始：

A B C D E F G H
^ ^ ^
i j k

首先你变化 k，所以下一步看起来像这样:

A B C D E F G H
^ ^   ^
i j   k

如果您到达了末尾，那么您会继续变化 j，然后再次变化 k。

A B C D E F G H
^   ^ ^
i   j k
A B C D E F G H
^   ^   ^
i   j   k

一旦 j 达到 G，也开始变化 i。

A B C D E F G H
  ^ ^ ^
  i j k
A B C D E F G H
  ^ ^   ^
  i j   k
...

用代码写出来类似于这样：

void print_combinations(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

- quinmars

---

这种方法的问题在于，它把参数3硬编码到了代码中。（如果想选择4个字符呢？）据我理解，这里提供了要选择的字符数组和数量。当然，解决这个问题的一种方法是用递归来代替明确嵌套的循环。 - joel.neely

@Dr.PersonPersonII，为什么三角形与OP有任何关联？ - MestreLion

你可以用任意参数将这个解决方案转换成递归的形式。 - Rok Kralj

@RokKralj，我们如何将这个解决方案转化为带任意参数的递归解决方案？我觉得这是不可能的。 - Aaron McDaid

如何做的简洁易懂的直观解释。 - Yonatan Simson

Answer 6

以下递归算法从有序集合中选择所有 k 元素组合：

• 选择您的组合的第一个元素 i
• 将 i 与从大于 i 的元素集合中递归选择的每个 k-1 元素组合相结合。

对集合中的每个 i 执行上述迭代。

必须确保选择的其余元素比 i 更大，以避免重复。这样，[3,5] 将只被选一次，作为 [3] 与 [5] 组合而成，而不是两次（该条件消除了 [5] + [3]）。如果没有此条件，则会得到变化而不是组合。

- Rafał Dowgird

---

很好的英文描述了许多答案使用的算法。 - MestreLion

以上第二个也很有用，特别是它帮助我理解了用户935714提出的解决方案。两者都非常优秀。 - jacoblambert

Answer 7

Python中的简短示例：

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

为了解释，下面用一个例子来描述递归方法：

例子：A B C D E
所有长度为3的组合如下：

• A与其余部分（B C D E）中的所有长度为2的组合
• B与其余部分（C D E）中的所有长度为2的组合
• C与其余部分（D E）中的所有长度为2的组合

- Rick Giuly

Answer 8

在C++中，以下例程将生成范围[first，last)之间长度为distance（first，k）的所有组合：

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

它可以像这样使用：

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

这将打印出以下内容：

123
124
125
134
135
145
234
235
245
345

- Matthieu N.

---

在这种情况下，begin和end是什么？如果传递给此函数的所有变量都是按值传递的，它如何实际返回某些内容？ - Sergej Andrejev

@Sergej Andrejev：将“being”和“begin”替换为“s.begin()”，将“end”替换为“s.end()”。该代码紧密遵循STL的“next_permutation”算法，在此处有更详细的描述：http://marknelson.us/2002/03/01/next-permutation/。 - Anthony Labarre

发生了什么事？ i1 = last; --i1; i1 = k; - Manoj R

Answer 9

我发现这个帖子很有用，想给出一个JavaScript解决方案，可以将其插入到Firebug中。根据您的JS引擎，如果起始字符串很大，可能需要一些时间。

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

输出应该如下：

abc
ab
ac
a
bc
b
c

- Adam

---

@NanoHead 这并没有错。输出已经显示了“ac”，而“ca”与“ac”是相同的组合。你所说的是在数学中的排列，在排列中，“ac”不等于“ca”。 - Jakob Jenkov

这不是从n个元素中选取k个元素的组合。 - shinzou

Answer 10

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

- Adam Hughes

---

不错的解决方案。我在回答最近的这个问题时参考了它：https://dev59.com/nVLTa4cB1Zd3GeqPdL5Y - wageoghe

这个函数唯一的问题就是递归。虽然在运行在PC上的软件通常没有问题，但如果你正在使用资源更为有限的平台（例如嵌入式系统），那么你就没那么幸运了。 - Padu Merloti

它还将分配许多列表并执行大量工作，将数组项复制到每个新数组中。在我看来，这些列表在整个枚举完成之前不会被收集。 - Niall Connaughton

那很棒。你是找到了一个算法还是从头开始写的？ - paparazzo