简短快速的c#实现

public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
    return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));                
}      

public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
    var result = new List<int[]>();

    var lastIndex = subSetLenght - 1;
    var dif = setLenght - subSetLenght;
    var prevSubSet = new int[subSetLenght];
    var lastSubSet = new int[subSetLenght];
    for (int i = 0; i < subSetLenght; i++)
    {
        prevSubSet[i] = i;
        lastSubSet[i] = i + dif;
    }

    while(true)
    {
        //add subSet ad result set
        var n = new int[subSetLenght];
        for (int i = 0; i < subSetLenght; i++)
            n[i] = prevSubSet[i];

        result.Add(n);

        if (prevSubSet[0] >= lastSubSet[0])
            break;

        //start at index 1 because index 0 is checked and breaking in the current loop
        int j = 1;
        for (; j < subSetLenght; j++)
        {
            if (prevSubSet[j] >= lastSubSet[j])
            {
                prevSubSet[j - 1]++;

                for (int p = j; p < subSetLenght; p++)
                    prevSubSet[p] = prevSubSet[p - 1] + 1;

                break;
            }
        }

        if (j > lastIndex)
            prevSubSet[lastIndex]++;
    }

    return result;
}

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

我知道这个问题已经有很多答案了，但我想在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元素集的幂集(如果你愿意的话)。

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

PowerShell解决方案:

function Get-NChooseK
{
    <#
    .SYNOPSIS
    Returns all the possible combinations by choosing K items at a time from N possible items.

    .DESCRIPTION
    Returns all the possible combinations by choosing K items at a time from N possible items.
    The combinations returned do not consider the order of items as important i.e. 123 is considered to be the same combination as 231, etc.

    .PARAMETER ArrayN
    The array of items to choose from.

    .PARAMETER ChooseK
    The number of items to choose.

    .PARAMETER AllK
    Includes combinations for all lesser values of K above zero i.e. 1 to K.

    .PARAMETER Prefix
    String that will prefix each line of the output.

    .EXAMPLE
    PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 3
    123

    .EXAMPLE
    PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 3 -AllK
    1
    2
    3
    12
    13
    23
    123

    .EXAMPLE
    PS C:\> Get-NChooseK -ArrayN '1','2','3' -ChooseK 2 -Prefix 'Combo: '
    Combo: 12
    Combo: 13
    Combo: 23

    .NOTES
    Author : nmbell
    #>

    # Use cmdlet binding
    [CmdletBinding()]

    # Declare parameters
    Param
    (

        [String[]]
        $ArrayN

    ,   [Int]
        $ChooseK

    ,   [Switch]
        $AllK

    ,   [String]
        $Prefix = ''

    )

    BEGIN
    {
    }

    PROCESS
    {
        # Validate the inputs
        $ArrayN = $ArrayN | Sort-Object -Unique

        If ($ChooseK -gt $ArrayN.Length)
        {
            Write-Error "Can't choose $ChooseK items when only $($ArrayN.Length) are available." -ErrorAction Stop
        }

        # Control the output
        $firstK = If ($AllK) { 1 } Else { $ChooseK }

        # Get combinations
        $firstK..$ChooseK | ForEach-Object {

            $thisK = $_

            $ArrayN[0..($ArrayN.Length-($thisK--))] | ForEach-Object {
                If ($thisK -eq 0)
                {
                    Write-Output ($Prefix+$_)
                }
                Else
                {
                    Get-NChooseK -Array ($ArrayN[($ArrayN.IndexOf($_)+1)..($ArrayN.Length-1)]) -Choose $thisK -AllK:$false -Prefix ($Prefix+$_)
                }
            }

        }
    }

    END
    {
    }

}

例如:

PS C:\>Get-NChooseK -ArrayN 'A','B','C','D','E' -ChooseK 3
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE

最近在IronScripter网站上发布了一个类似于这个问题的挑战，在那里你可以找到我的链接和其他一些解决方案。

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

这是一个为nCk生成组合的递归程序。假设集合中的元素从1到n

#include<stdio.h>
#include<stdlib.h>

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if(loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf("\n");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if(ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d\n",count);
}