https://gist.github.com/3118596

JavaScript有一个实现。它有函数来获得k组合和任意对象数组的所有组合。例子:

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

这是一个c++解决方案，我提出使用递归和位移位。它也可以在C语言中工作。

void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

你可以在这里找到这是如何工作的解释。

c#简单算法。 (我发布它是因为我试图使用你们上传的那个，但由于某种原因我无法编译它——扩展一个类?所以我自己写了一个，以防别人遇到和我一样的问题)。 顺便说一下，除了基本的编程，我对c#没什么兴趣，但是这个工作得很好。

public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
        {
            List<List<int>> lSubsets = new List<List<int>>();
            GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
            return lSubsets;
        }

public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
        {
            if (lCurrSet.Count == k)
            {
                lSubsets.Add(lCurrSet);
                return;
            }

            if (i >= lInputSet.Count)
                return;

            List<int> lWith = new List<int>(lCurrSet);
            List<int> lWithout = new List<int>(lCurrSet);
            lWith.Add(lInputSet[i++]);

            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
        }

GetSubsetsOfSizeK(set of type List<int>， integer k)

您可以修改它以遍历您正在处理的任何内容。

好运！

最近在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

下面是一个使用宏的Lisp方法。这适用于Common Lisp，也适用于其他Lisp方言。

下面的代码创建了'n'个嵌套循环，并为列表lst中的'n'个元素的每个组合执行任意代码块(存储在body变量中)。变量var指向一个包含用于循环的变量的列表。

(defmacro do-combinations ((var lst num) &body body)
  (loop with syms = (loop repeat num collect (gensym))
        for i on syms
        for k = `(loop for ,(car i) on (cdr ,(cadr i))
                         do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
                then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
        finally (return k)))

让我们看看…

(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))

(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
 (LOOP FOR #:G3216 ON (CDR #:G3217) DO
  (LOOP FOR #:G3215 ON (CDR #:G3216) DO
   (LOOP FOR #:G3214 ON (CDR #:G3215) DO
    (LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
     (PROGN (PPRINT (MAPCAR #'CAR P))))))))

(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))

(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...

由于默认情况下不存储组合，因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。

作为迭代器对象实现的MetaTrader MQL4非常快速的组合。

代码很容易理解。

我对很多算法进行了基准测试，这个算法真的非常快——大约比大多数next_combination()函数快3倍。

class CombinationsIterator { private: int input_array[]; // 1 2 3 4 5 int index_array[]; // i j k int m_elements; // N int m_indices; // K public: CombinationsIterator(int &src_data[], int k) { m_indices = k; m_elements = ArraySize(src_data); ArrayCopy(input_array, src_data); ArrayResize(index_array, m_indices); // create initial combination (0..k-1) for (int i = 0; i < m_indices; i++) { index_array[i] = i; } } // https://stackoverflow.com/questions/5076695 // bool next_combination(int &item[], int k, int N) bool advance() { int N = m_elements; for (int i = m_indices - 1; i >= 0; --i) { if (index_array[i] < --N) { ++index_array[i]; for (int j = i + 1; j < m_indices; ++j) { index_array[j] = index_array[j - 1] + 1; } return true; } } return false; } void getItems(int &items[]) { // fill items[] from input array for (int i = 0; i < m_indices; i++) { items[i] = input_array[index_array[i]]; } } };

测试上述迭代器类的驱动程序:

//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // driver program to test above class #define N 5 #define K 3 void OnStart() { int myset[N] = {1, 2, 3, 4, 5}; int items[K]; CombinationsIterator comboIt(myset, K); do { comboIt.getItems(items); printf("%s", ArrayToString(items)); } while (comboIt.advance()); }

输出: 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