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

在Haskell中的简单递归算法

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

首先我们定义一个特殊情况，即选择零个元素。它会产生一个唯一的结果，即一个空列表（即包含一个空列表的列表）。

对于n > 0，x 遍历列表中的每个元素，xs 是 x 后面的所有元素。

rest 使用对 combinations 的递归调用从 xs 中选择了 n - 1 个元素。函数的最终结果是一个列表，其中每个元素都是 x : rest (即一个以 x 为头部，rest 为尾部的列表)，对于每个不同的 x 和 rest 值都要创建这样一个列表。

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

当然，由于 Haskell 是惰性求值的，因此列表会在需要时逐渐生成，因此您可以部分地计算指数级大的组合。

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

这里来了COBOL老爷子，这门遭受了很多诟病的语言。

假设有一个包含34个元素，每个元素为8字节的数组（纯属随意选择）。我们的想法是列举出所有可能的四元组并将其加载到一个数组中。

我们使用4个索引，分别对应四个位置。

数组的处理过程如下：

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

我们从4变化到数组的末尾来遍历idx4。对于每个idx4，我们获得一个四元组的独特组合。当idx4到达数组的末尾时，我们将idx3增加1并将idx4设置为idx3 + 1。然后我们再次运行idx4到结尾。我们按照这种方式进行，分别增加idx3，idx2和idx1的位置，直到idx1的位置距离数组的末尾小于4。这就完成了算法。

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

首次迭代：

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

一个 COBOL 的例子：

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

---

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

另一个带有组合索引惰性生成的 C# 版本。此版本维护一个单一的索引数组，用于定义所有值列表和当前组合值之间的映射关系，即在整个运行时期间不断使用 O(k) 的附加空间。该代码以 O(k) 时间生成单个组合，包括第一个组合。

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

测试代码：

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

输出：

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

如果您能使用SQL语法——比如，如果您正在使用LINQ来访问结构或数组的字段，或直接访问一个名为“Alphabet”的表并且该表只有一个字符字段“Letter”，那么您可以使用以下代码进行调整：

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

这将返回所有3个字母的组合，不管"Alphabet"表中有多少个字母（可以是3个、8个、10个、27个等等）。
如果你想要的是所有排列，而不仅仅是组合 （即你希望"ACB"和"ABC"被视为不同的，而不是只出现一次），只需删除最后一行（即AND语句）就可以了。
编辑后：重新阅读问题后，我意识到需要的是通用算法，不仅仅是选择3个项目的特定情况。Adam Hughes的回答是完整的，遗憾的是我不能（还）为其投票。这个答案很简单，但只适用于你想要恰好3个项目的情况。

以下是一个优雅的、通用的Scala实现，正如99 Scala Problems中所描述的那样。

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}

我在项目欧拉中使用了一种排列算法，使用Python编写：

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

如果

n<len(l) 

您需要的所有组合都应该不重复，您需要吗？

这是一个生成器，您可以在类似以下的内容中使用它：

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb 

假设你的字母数组看起来像这样：“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
...

function initializePointers($cnt) {
    $pointers = [];

    for($i=0; $i<$cnt; $i++) {
        $pointers[] = $i;
    }

    return $pointers;     
}

function incrementPointers(&$pointers, &$arrLength) {
    for($i=0; $i<count($pointers); $i++) {
        $currentPointerIndex = count($pointers) - $i - 1;
        $currentPointer = $pointers[$currentPointerIndex];

        if($currentPointer < $arrLength - $i - 1) {
           ++$pointers[$currentPointerIndex];

           for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
                $pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
           }

           return true;
        }
    }

    return false;
}

function getDataByPointers(&$arr, &$pointers) {
    $data = [];

    for($i=0; $i<count($pointers); $i++) {
        $data[] = $arr[$pointers[$i]];
    }

    return $data;
}

function getCombinations($arr, $cnt)
{
    $len = count($arr);
    $result = [];
    $pointers = initializePointers($cnt);

    do {
        $result[] = getDataByPointers($arr, $pointers);
    } while(incrementPointers($pointers, count($arr)));

    return $result;
}

$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);

基于https://dev59.com/9nVC5IYBdhLWcg3w-mVO#127898，但更加抽象，适用于任何指针大小。

https://gist.github.com/3118596

有一个针对JavaScript的实现。它具有获取数组中任意对象的k组合和所有组合的函数。例子：

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

这里有一个用C#编写的惰性求值版本的算法：

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

And test part: 和测试部分：

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

希望这能对你有所帮助！

---

另一个版本，它强制所有前k个先出现，然后是所有前k+1个组合，然后是所有前k+2个等等... 这意味着如果你有排序数组，最重要的在顶部，它会逐渐扩展到下一个 - 只有在必须这样做时才会这样做。

private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
    if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
        return true;

    if (num[k - 1] + 1 == n)
        return false;

    ++num[k - 1];
    for (int i = 0; i < k - 1; ++i)
        num[i] = i;

    return true;
}

例如，如果您在k=3，n=5上运行第一种方法（“nextCombination”），您将得到以下结果：

0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4

但是如果你运行

int[] nums = new int[k];
for (int i = 0; i < k; ++i)
    nums[i] = i;
do
{
    Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));

您会得到以下内容（为了清晰起见，我添加了空行）：

0 1 2

0 1 3
0 2 3
1 2 3

0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4

它仅在必要时添加“4”，并且在添加“4”之后，仅在必要时（在执行01、02、12之后）再次添加“3”。

一个简短的 Python 代码，生成索引位置。

def yield_combos(n,k):
    # n is set size, k is combo size

    i = 0
    a = [0]*k

    while i > -1:
        for j in range(i+1, k):
            a[j] = a[j-1]+1
        i=j
        yield a
        while a[i] == i + n - k:
            i -= 1
        a[i] += 1