由于没有提到编程语言，我假设列表也是可以的。下面是一个OCaml版本，适用于短列表(非尾递归)。给定一个包含任意类型元素的列表l和一个整数n，如果我们假设结果列表中元素的顺序被忽略，它将返回一个包含l的n个元素的所有可能列表的列表，即list ['a';'b']与['b';'a']相同，并且将报告一次。因此，结果列表的大小将是((list。长度l)选择n)。

递归的直观原理如下:取列表的头，然后进行两次递归调用:

递归调用1 (RC1):到列表的尾部，但选择n-1个元素 递归调用2 (RC2):到列表的尾部，但选择n个元素

要组合递归结果，list-乘(请使用奇数名称)列表的头部与RC1的结果，然后附加(@)RC2的结果。List-multiply是如下操作lmul:

a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]

Lmul在下面的代码中实现

List.map (fun x -> h::x)

当列表的大小等于您想要选择的元素数量时，递归将终止，在这种情况下，您只需返回列表本身。

下面是OCaml中实现上述算法的四行代码:

    let rec choose l n = match l, (List.length l) with                                 
    | _, lsize  when n==lsize  -> [l]                                
    | h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)   
    | [], _ -> []    

我的实现在c/c++

#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int opt = -1, min_len = 0, max_len = 0;
    char ofile[256], fchar[2], tchar[2];
    ofile[0] = 0;
    fchar[0] = 0;
    tchar[0] = 0;
    while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
    {
            switch(opt)
            {
                    case 'o':
                    strncpy(ofile, optarg, 255);
                    break;
                    case 'f':
                    strncpy(fchar, optarg, 1);
                    break;
                    case 't':
                    strncpy(tchar, optarg, 1);
                    break;
                    case 'l':
                    min_len = atoi(optarg);
                    break;
                    case 'L':
                    max_len = atoi(optarg);
                    break;
                    default:
                    printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
            }
    }
if(max_len < 1)
{
    printf("error, length must be more than 0\n");
    return 1;
}
if(min_len > max_len)
{
    printf("error, max length must be greater or equal min_length\n");
    return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
    printf("error, invalid range specified\n");
    return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
    printf("failed to open input file with error: %s\n", strerror(errno));
    return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
    char buf[cur_len];
    for(int i = 0; i < cur_len; i++)
        buf[i] = fchar[0];
    fwrite(buf, cur_len, 1, out);
    fwrite("\n", 1, 1, out);
    while(buf[0] != (tchar[0]+1))
    {
        while(buf[cur_len-1] < tchar[0])
        {
            (int)buf[cur_len-1]++;
            fwrite(buf, cur_len, 1, out);
            fwrite("\n", 1, 1, out);
        }
        if(cur_len < 2)
            break;
        if(buf[0] == tchar[0])
        {
            bool stop = true;
            for(int i = 1; i < cur_len; i++)
            {
                if(buf[i] != tchar[0])
                {
                    stop = false;
                    break;
                }
            }
            if(stop)
                break;
        }
        int u = cur_len-2;
        for(; u>=0 && buf[u] >= tchar[0]; u--)
            ;
        (int)buf[u]++;
        for(int i = u+1; i < cur_len; i++)
            buf[i] = fchar[0];
        fwrite(buf, cur_len, 1, out);
        fwrite("\n", 1, 1, out);
    }
    cur_len++;
}
fclose(out);
return 0;
}

这里我的实现在c++，它写所有的组合到指定的文件，但行为可以改变，我在生成各种字典，它接受最小和最大长度和字符范围，目前只有ANSI支持，它足以满足我的需求

下面是我最近用Java写的一段代码，它计算并返回从“outOf”元素中“num”元素的所有组合。

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}

假设你的字母数组是这样的:"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://stackoverflow.com/a/127898/2628125，但更抽象，适用于任何大小的指针。

另一个具有组合索引惰性生成的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

下面是Clojure版本，它使用了我在OCaml实现答案中描述的相同算法:

(defn select
  ([items]
     (select items 0 (inc (count items))))
  ([items n1 n2]
     (reduce concat
             (map #(select % items)
                  (range n1 (inc n2)))))
  ([n items]
     (let [
           lmul (fn [a list-of-lists-of-bs]
                     (map #(cons a %) list-of-lists-of-bs))
           ]
       (if (= n (count items))
         (list items)
         (if (empty? items)
           items
           (concat
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

它提供了三种调用方法:

(a)按问题要求，选出n项:

  user=> (count (select 3 "abcdefgh"))
  56

(b) n1至n2个选定项目:

user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))

(c)在0至所选项目的集合大小之间:

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))