下面的递归算法从有序集中选取所有k元素组合:

选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。

对集合中的每一个i进行上述迭代。

为了避免重复，您必须选择比i大的其余元素。这样[3,5]将只被选中一次，即[3]与[5]结合，而不是两次(该条件消除了[5]+[3])。没有这个条件，你得到的是变化而不是组合。

最近在IronScripter网站上有一个PowerShell挑战，需要一个n- choice -k的解决方案。我在那里发布了一个解决方案，但这里有一个更通用的版本。

AllK开关用于控制输出是长度为ChooseK的组合，还是长度为1到ChooseK的组合。 Prefix参数实际上是输出字符串的累加器，但其效果是为初始调用传递的值实际上会为每一行输出添加前缀。

function Get-NChooseK
{

    [CmdletBinding()]

    Param
    (

        [String[]]
        $ArrayN

    ,   [Int]
        $ChooseK

    ,   [Switch]
        $AllK

    ,   [String]
        $Prefix = ''

    )

    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+$_)
                }
            }

        }
    }

}

例如:

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

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;
    }
}

这是我用c++写的命题

我尽可能少地限制迭代器类型，所以这个解决方案假设只有前向迭代器，它可以是const_iterator。这应该适用于任何标准容器。在参数没有意义的情况下，它抛出std:: invalid_argument

#include <vector>
#include <stdexcept>

template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
    if(begin == end && combination_size > 0u)
        throw std::invalid_argument("empty set and positive combination size!");
    std::vector<std::vector<Fci> > result; // empty set of combinations
    if(combination_size == 0u) return result; // there is exactly one combination of
                                              // size 0 - emty set
    std::vector<Fci> current_combination;
    current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
                                                        // in my vector to store
                                                        // the end sentinel there.
                                                        // The code is cleaner thanks to that
    for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
    {
        current_combination.push_back(begin); // Construction of the first combination
    }
    // Since I assume the itarators support only incrementing, I have to iterate over
    // the set to get its size, which is expensive. Here I had to itrate anyway to  
    // produce the first cobination, so I use the loop to also check the size.
    if(current_combination.size() < combination_size)
        throw std::invalid_argument("combination size > set size!");
    result.push_back(current_combination); // Store the first combination in the results set
    current_combination.push_back(end); // Here I add mentioned earlier sentinel to
                                        // simplyfy rest of the code. If I did it 
                                        // earlier, previous statement would get ugly.
    while(true)
    {
        unsigned int i = combination_size;
        Fci tmp;                            // Thanks to the sentinel I can find first
        do                                  // iterator to change, simply by scaning
        {                                   // from right to left and looking for the
            tmp = current_combination[--i]; // first "bubble". The fact, that it's 
            ++tmp;                          // a forward iterator makes it ugly but I
        }                                   // can't help it.
        while(i > 0u && tmp == current_combination[i + 1u]);

        // Here is probably my most obfuscated expression.
        // Loop above looks for a "bubble". If there is no "bubble", that means, that
        // current_combination is the last combination, Expression in the if statement
        // below evaluates to true and the function exits returning result.
        // If the "bubble" is found however, the ststement below has a sideeffect of 
        // incrementing the first iterator to the left of the "bubble".
        if(++current_combination[i] == current_combination[i + 1u])
            return result;
        // Rest of the code sets posiotons of the rest of the iterstors
        // (if there are any), that are to the right of the incremented one,
        // to form next combination

        while(++i < combination_size)
        {
            current_combination[i] = current_combination[i - 1u];
            ++current_combination[i];
        }
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
        result.push_back(std::vector<Fci>(current_combination.begin(),
                                          current_combination.end() - 1));
    }
}

#include <stdio.h>

unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
    unsigned int finished = 0;
    unsigned int changed = 0;
    unsigned int i;

    if (k > 0) {
        for (i = k - 1; !finished && !changed; i--) {
            if (ar[i] < (n - 1) - (k - 1) + i) {
                /* Increment this element */
                ar[i]++;
                if (i < k - 1) {
                    /* Turn the elements after it into a linear sequence */
                    unsigned int j;
                    for (j = i + 1; j < k; j++) {
                        ar[j] = ar[j - 1] + 1;
                    }
                }
                changed = 1;
            }
            finished = i == 0;
        }
        if (!changed) {
            /* Reset to first combination */
            for (i = 0; i < k; i++) {
                ar[i] = i;
            }
        }
    }
    return changed;
}

typedef void(*printfn)(const void *, FILE *);

void print_set(const unsigned int *ar, size_t len, const void **elements,
    const char *brackets, printfn print, FILE *fptr)
{
    unsigned int i;
    fputc(brackets[0], fptr);
    for (i = 0; i < len; i++) {
        print(elements[ar[i]], fptr);
        if (i < len - 1) {
            fputs(", ", fptr);
        }
    }
    fputc(brackets[1], fptr);
}

int main(void)
{
    unsigned int numbers[] = { 0, 1, 2 };
    char *elements[] = { "a", "b", "c", "d", "e" };
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    do {
        print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
        putchar('\n');
    } while (next_combination(numbers, n, k));
    getchar();
    return 0;
}

为此，我在SQL Server 2005中创建了一个解决方案，并将其发布在我的网站上:http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

下面是一个例子来说明用法:

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

结果:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)