算法:

从1数到2^n。 将每个数字转换为二进制表示。 根据位置，将每个“on”位转换为集合中的元素。

在c#中:

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

为什么它能起作用?

在n元素集的子集和n位序列之间存在双射。

这意味着我们可以通过数数序列来计算出有多少个子集。

例如，下面的四个元素集可以用{0,1}X {0,1} X {0,1} X{0,1}(或2^4)个不同的序列表示。

我们要做的就是从1数到2^n来找到所有的组合。(我们忽略空集。)接下来，将数字转换为二进制表示。然后将集合中的元素替换为“on”位。

如果只需要k个元素的结果，则只在k位为“on”时打印。

(如果你想要所有的子集，而不是k长度的子集，删除cnt/kElement部分。)

(有关证明，请参阅麻省理工学院免费课件计算机科学数学，雷曼等，第11.2.2节。https://ocw.mit.edu/courses/electrical -工程-和-计算机- science/6 - 042 j -数学- -计算机科学-下降- 2010/readings/)

一个简洁的Javascript解决方案:

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

下面是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))

在Python中，利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合，这将占用大量内存，但其优点是初始集合可以是一个复杂的对象。它只会找到唯一的组合。

import copy

def find_combinations( length, set, combinations = None, candidate = None ):
    # recursive function to calculate all unique combinations of unique values
    # from [set], given combinations of [length].  The result is populated
    # into the 'combinations' list.
    #
    if combinations == None:
        combinations = []
    if candidate == None:
        candidate = []

    for item in set:
        if item in candidate:
            # this item already appears in the current combination somewhere.
            # skip it
            continue

        attempt = copy.deepcopy(candidate)
        attempt.append(item)
        # sorting the subset is what gives us completely unique combinations,
        # so that [1, 2, 3] and [1, 3, 2] will be treated as equals
        attempt.sort()

        if len(attempt) < length:
            # the current attempt at finding a new combination is still too
            # short, so add another item to the end of the set
            # yay recursion!
            find_combinations( length, set, combinations, attempt )
        else:
            # the current combination attempt is the right length.  If it
            # already appears in the list of found combinations then we'll
            # skip it.
            if attempt in combinations:
                continue
            else:
                # otherwise, we append it to the list of found combinations
                # and move on.
                combinations.append(attempt)
                continue
    return len(combinations)

你可以这样使用它。传递'result'是可选的，所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。

size = 3
set = [1, 2, 3, 4, 5]
result = []

num = find_combinations( size, set, result ) 
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

您应该从测试数据中得到以下输出:

size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

如果你的集合是这样的，它也会工作得很好:

set = [
    [ 'vanilla', 'cupcake' ],
    [ 'chocolate', 'pudding' ],
    [ 'vanilla', 'pudding' ],
    [ 'chocolate', 'cookie' ],
    [ 'mint', 'cookie' ]
]

我有一个用于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 

Here's some simple code that prints all the C(n,m) combinations. It works by initializing and moving a set of array indices that point to next valid combination. The indices are initialized to point to the lowest m indices (lexicographically the smallest combination). Then on, starting with the m-th index, we try to move the indices forward. if an index has reached its limit, we try the previous index (all the way down to index 1). If we can move an index forward, then we reset all greater indices.

m=(rand()%n)+1; // m will vary from 1 to n

for (i=0;i<n;i++) a[i]=i+1;

// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);

// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination

done=false;
while (!done)
{
    // print combination
    for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
    printf("\n");

    // update combination
    // method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
    // if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
    // if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
    // repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
    j=m-1;
    i=1;
    move_found=false;
    while ((j>=0) && !move_found)
    {
        if (p[j]<(n-i)) 
        {
            move_found=true;
            p[j]++; // point p[j] to next index
            for (k=j+1;k<m;k++)
            {
                p[k]=p[j]+(k-j);
            }
        }
        else
        {
            j--;
            i++;
        }
    }
    if (!move_found) done=true;
}