下面是我最近用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);
    }
}

我有一个用于project euler的排列算法，用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

If

n<len(l) 

你应该有所有你需要的组合，没有重复，你需要吗?

它是一个生成器，所以你可以这样使用它:

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

我们可以用比特的概念来做这个。假设我们有一个字符串“abc”，我们想要所有长度为2的元素的组合(即“ab”，“ac”，“bc”)。

我们可以在1到2^n(排他性)的数字中找到集合位。这里是1到7，只要我们设置了bits = 2，我们就可以从string中输出相应的值。

例如:

1 - 001 二零零一 3011 ->印刷ab (str[0]， str[1]) 四到一百。 5 - 101 ->打印ac (str[0]， str[2]) 6 - 110 ->印刷ab (str[1]， str[2]) 7 - 111。

代码示例:

public class StringCombinationK {   
    static void combk(String s , int k){
        int n = s.length();
        int num = 1<<n;
        int j=0;
        int count=0;

        for(int i=0;i<num;i++){
            if (countSet(i)==k){
                setBits(i,j,s);
                count++;
                System.out.println();
            }
        }

        System.out.println(count);
    }

    static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
        if(i==0){
            return;
        }

        if(i%2==1){
            System.out.print(s.charAt(j));                  
        }

        setBits(i/2,j+1,s);
    }

    static int countSet(int i){ //count number of set bits
        if( i==0){
            return 0;
        }

        return (i%2==0? 0:1) + countSet(i/2);
    }

    public static void main(String[] arhs){
        String s = "abcdefgh";
        int k=3;
        combk(s,k);
    }
}

下面是我的Scala解决方案:

def combinations[A](s: List[A], k: Int): List[List[A]] = 
  if (k > s.length) Nil
  else if (k == 1) s.map(List(_))
  else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)

这里你有一个用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));
        }
    }

及测试部分:

    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”之后，它只在必须添加时再添加“3”(在执行01、02、12之后)。

我的实现在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支持，它足以满足我的需求