在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' ]
]

我在c++中为组合创建了一个通用类。 它是这样使用的。

char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
    for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
    cout << ' ';
}

我的库ncr[i]从1返回，而不是从0返回。 这就是为什么数组中有0。 如果你想考虑订单，只需将nCr class改为nPr即可。 用法是相同的。

结果

美国广播公司 ABD 安倍 沛富 ABG ABH 澳洲牧牛犬 王牌 ACF ACG 呵呀 正面 ADF ADG 抗利尿激素 时 AEG AEH 二自由度陀螺仪 AFH 啊 BCD 公元前 供应量 波士顿咨询公司 BCH 12 快速公车提供 BDG BDH 性能试验 求 本· 高炉煤气 BFH 使用BGH CDE 提供 CDG 鼎晖 欧共体语言教学大纲的 CEG 另一 CFG CFH 全息 DEF 度 电气设施 脱硫 干扰 DGH EFG EFH EGH FGH

下面是头文件。

#pragma once
#include <exception>

class NRexception : public std::exception
{
public:
    virtual const char* what() const throw() {
        return "Combination : N, R should be positive integer!!";
    }
};

class Combination
{
public:
    Combination(int n, int r);
    virtual ~Combination() { delete [] ar;}
    int& operator[](unsigned i) {return ar[i];}
    bool next();
    int size() {return r;}
    static int factorial(int n);

protected:
    int* ar;
    int n, r;
};

class nCr : public Combination
{
public: 
    nCr(int n, int r);
    bool next();
    int count() const;
};

class nTr : public Combination
{
public:
    nTr(int n, int r);
    bool next();
    int count() const;
};

class nHr : public nTr
{
public:
    nHr(int n, int r) : nTr(n,r) {}
    bool next();
    int count() const;
};

class nPr : public Combination
{
public:
    nPr(int n, int r);
    virtual ~nPr() {delete [] on;}
    bool next();
    void rewind();
    int count() const;

private:
    bool* on;
    void inc_ar(int i);
};

以及执行。

#include "combi.h"
#include <set>
#include<cmath>

Combination::Combination(int n, int r)
{
    //if(n < 1 || r < 1) throw NRexception();
    ar = new int[r];
    this->n = n;
    this->r = r;
}

int Combination::factorial(int n) 
{
    return n == 1 ? n : n * factorial(n-1);
}

int nPr::count() const
{
    return factorial(n)/factorial(n-r);
}

int nCr::count() const
{
    return factorial(n)/factorial(n-r)/factorial(r);
}

int nTr::count() const
{
    return pow(n, r);
}

int nHr::count() const
{
    return factorial(n+r-1)/factorial(n-1)/factorial(r);
}

nCr::nCr(int n, int r) : Combination(n, r)
{
    if(r == 0) return;
    for(int i=0; i<r-1; i++) ar[i] = i + 1;
    ar[r-1] = r-1;
}

nTr::nTr(int n, int r) : Combination(n, r)
{
    for(int i=0; i<r-1; i++) ar[i] = 1;
    ar[r-1] = 0;
}

bool nCr::next()
{
    if(r == 0) return false;
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n-r+2+i) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++] + 1;
    return true;
}

bool nTr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        ar[i] = 1;
        if(--i == -1) return false;
        ar[i]++;
    }
    return true;
}

bool nHr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++];
    return true;
}

nPr::nPr(int n, int r) : Combination(n, r)
{
    on = new bool[n+2];
    for(int i=0; i<n+2; i++) on[i] = false;
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

void nPr::rewind()
{
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

bool nPr::next()
{   
    inc_ar(r-1);

    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        inc_ar(i);
    }
    while(i < r-1) {
        ar[++i] = 0;
        inc_ar(i);
    }
    return true;
}

void nPr::inc_ar(int i)
{
    on[ar[i]] = false;
    while(on[++ar[i]]);
    if(ar[i] != n+1) on[ar[i]] = true;
}

这个答案怎么样……这将打印所有长度为3的组合…它可以推广到任何长度… 工作代码…

#include<iostream>
#include<string>
using namespace std;

void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
 cout<<dest<<endl;}
else{
  if(!a.empty() && dest.length() < 3 ){
     combination(a.substr(1,a.length()),dest+a[0]);}
  if(!a.empty() && dest.length() <= 3 ){
      combination(a.substr(1,a.length()),dest);}
 }

 }

 int main(){
 string demo("abcd");
 combination(demo,"");
 return 0;
 }

我知道这个问题已经有很多答案了，但我想在JavaScript中添加我自己的贡献，它由两个函数组成——一个生成原始n元素集的所有可能不同的k子集，另一个使用第一个函数生成原始n元素集的幂集。

下面是这两个函数的代码:

//Generate combination subsets from a base set of elements (passed as an array). This function should generate an
//array containing nCr elements, where nCr = n!/[r! (n-r)!].

//Arguments:

//[1] baseSet :     The base set to create the subsets from (e.g., ["a", "b", "c", "d", "e", "f"])
//[2] cnt :         The number of elements each subset is to contain (e.g., 3)

function MakeCombinationSubsets(baseSet, cnt)
{
    var bLen = baseSet.length;
    var indices = [];
    var subSet = [];
    var done = false;
    var result = [];        //Contains all the combination subsets generated
    var done = false;
    var i = 0;
    var idx = 0;
    var tmpIdx = 0;
    var incr = 0;
    var test = 0;
    var newIndex = 0;
    var inBounds = false;
    var tmpIndices = [];
    var checkBounds = false;

    //First, generate an array whose elements are indices into the base set ...

    for (i=0; i<cnt; i++)

        indices.push(i);

    //Now create a clone of this array, to be used in the loop itself ...

        tmpIndices = [];

        tmpIndices = tmpIndices.concat(indices);

    //Now initialise the loop ...

    idx = cnt - 1;      //point to the last element of the indices array
    incr = 0;
    done = false;
    while (!done)
    {
    //Create the current subset ...

        subSet = [];    //Make sure we begin with a completely empty subset before continuing ...

        for (i=0; i<cnt; i++)

            subSet.push(baseSet[tmpIndices[i]]);    //Create the current subset, using items selected from the
                                                    //base set, using the indices array (which will change as we
                                                    //continue scanning) ...

    //Add the subset thus created to the result set ...

        result.push(subSet);

    //Now update the indices used to select the elements of the subset. At the start, idx will point to the
    //rightmost index in the indices array, but the moment that index moves out of bounds with respect to the
    //base set, attention will be shifted to the next left index.

        test = tmpIndices[idx] + 1;

        if (test >= bLen)
        {
        //Here, we're about to move out of bounds with respect to the base set. We therefore need to scan back,
        //and update indices to the left of the current one. Find the leftmost index in the indices array that
        //isn't going to  move out of bounds with respect to the base set ...

            tmpIdx = idx - 1;
            incr = 1;

            inBounds = false;       //Assume at start that the index we're checking in the loop below is out of bounds
            checkBounds = true;

            while (checkBounds)
            {
                if (tmpIdx < 0)
                {
                    checkBounds = false;    //Exit immediately at this point
                }
                else
                {
                    newIndex = tmpIndices[tmpIdx] + 1;
                    test = newIndex + incr;

                    if (test >= bLen)
                    {
                    //Here, incrementing the current selected index will take that index out of bounds, so
                    //we move on to the next index to the left ...

                        tmpIdx--;
                        incr++;
                    }
                    else
                    {
                    //Here, the index will remain in bounds if we increment it, so we
                    //exit the loop and signal that we're in bounds ...

                        inBounds = true;
                        checkBounds = false;

                    //End if/else
                    }

                //End if 
                }               
            //End while
            }
    //At this point, if we'er still in bounds, then we continue generating subsets, but if not, we abort immediately.

            if (!inBounds)
                done = true;
            else
            {
            //Here, we're still in bounds. We need to update the indices accordingly. NOTE: at this point, although a
            //left positioned index in the indices array may still be in bounds, incrementing it to generate indices to
            //the right may take those indices out of bounds. We therefore need to check this as we perform the index
            //updating of the indices array.

                tmpIndices[tmpIdx] = newIndex;

                inBounds = true;
                checking = true;
                i = tmpIdx + 1;

                while (checking)
                {
                    test = tmpIndices[i - 1] + 1;   //Find out if incrementing the left adjacent index takes it out of bounds

                    if (test >= bLen)
                    {
                        inBounds = false;           //If we move out of bounds, exit NOW ...
                        checking = false;
                    }
                    else
                    {
                        tmpIndices[i] = test;       //Otherwise, update the indices array ...

                        i++;                        //Now move on to the next index to the right in the indices array ...

                        checking = (i < cnt);       //And continue until we've exhausted all the indices array elements ...
                    //End if/else
                    }
                //End while
                }
                //At this point, if the above updating of the indices array has moved any of its elements out of bounds,
                //we abort subset construction from this point ...
                if (!inBounds)
                    done = true;
            //End if/else
            }
        }
        else
        {
        //Here, the rightmost index under consideration isn't moving out of bounds with respect to the base set when
        //we increment it, so we simply increment and continue the loop ...
            tmpIndices[idx] = test;
        //End if
        }
    //End while
    }
    return(result);
//End function
}


function MakePowerSet(baseSet)
{
    var bLen = baseSet.length;
    var result = [];
    var i = 0;
    var partialSet = [];

    result.push([]);    //add the empty set to the power set

    for (i=1; i<bLen; i++)
    {
        partialSet = MakeCombinationSubsets(baseSet, i);
        result = result.concat(partialSet);
    //End i loop
    }
    //Now, finally, add the base set itself to the power set to make it complete ...

    partialSet = [];
    partialSet.push(baseSet);
    result = result.concat(partialSet);

    return(result);
    //End function
}

我用集合["a"， "b"， "c"， "d"， "e"， "f"]作为基本集进行了测试，并运行代码以产生以下幂集:

[]
["a"]
["b"]
["c"]
["d"]
["e"]
["f"]
["a","b"]
["a","c"]
["a","d"]
["a","e"]
["a","f"]
["b","c"]
["b","d"]
["b","e"]
["b","f"]
["c","d"]
["c","e"]
["c","f"]
["d","e"]
["d","f"]
["e","f"]
["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"]
["a","b","c","d"]
["a","b","c","e"]
["a","b","c","f"]
["a","b","d","e"]
["a","b","d","f"]
["a","b","e","f"]
["a","c","d","e"]
["a","c","d","f"]
["a","c","e","f"]
["a","d","e","f"]
["b","c","d","e"]
["b","c","d","f"]
["b","c","e","f"]
["b","d","e","f"]
["c","d","e","f"]
["a","b","c","d","e"]
["a","b","c","d","f"]
["a","b","c","e","f"]
["a","b","d","e","f"]
["a","c","d","e","f"]
["b","c","d","e","f"]
["a","b","c","d","e","f"]

只要复制粘贴这两个函数“原样”，你就有了提取n元素集的不同k子集所需的基本知识，并生成该n元素集的幂集(如果你愿意的话)。

我并不是说这很优雅，只是说它在经过大量的测试(并在调试阶段将空气变为蓝色:)之后可以工作。

JavaScript，基于生成器，递归方法:

function *nCk(n,k){ for(var i=n-1;i>=k-1;--i) if(k===1) yield [i]; else for(var temp of nCk(i,k-1)){ temp.unshift(i); yield temp; } } function test(){ try{ var n=parseInt(ninp.value); var k=parseInt(kinp.value); log.innerText=""; var stop=Date.now()+1000; if(k>=1) for(var res of nCk(n,k)) if(Date.now()<stop) log.innerText+=JSON.stringify(res)+" "; else{ log.innerText+="1 second passed, stopping here."; break; } }catch(ex){} } n:<input id="ninp" oninput="test()"> &gt;= k:<input id="kinp" oninput="test()"> &gt;= 1 <div id="log"></div>

通过这种方式(减少i和unshift())，它以递减的顺序生成组合和组合内的元素，有点赏心悦目。 测试在1秒后停止，因此输入奇怪的数字是相对安全的。

现在又出现了祖辈COBOL，一种饱受诟病的语言。

让我们假设一个包含34个元素的数组，每个元素8个字节(完全是任意选择)。其思想是枚举所有可能的4元素组合，并将它们加载到一个数组中。

我们使用4个指标，每个指标代表4个组中的每个位置

数组是这样处理的:

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

我们把idx4从4变到最后。对于每个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.