短快C实现

#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
}

要查看它有多快，请使用这段代码并测试它

#include <time.h>
#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int c = 0; int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       /* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
       if (i == p - 1) c++;
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
  printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}

使用cmd.exe (windows)测试:

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in          5.781 second(s)

c:\Program Files\lcc\projects>

祝你有愉快的一天。

这是一个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);
}

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

递归，一个很简单的答案，combo，在Free Pascal中。

    procedure combinata (n, k :integer; producer :oneintproc);

        procedure combo (ndx, nbr, len, lnd :integer);
        begin
            for nbr := nbr to len do begin
                productarray[ndx] := nbr;
                if len < lnd then
                    combo(ndx+1,nbr+1,len+1,lnd)
                else
                    producer(k);
            end;
        end;

    begin
        combo (0, 0, n-k, n-1);
    end;

“producer”处理为每个组合生成的产品数组。

下面是c++中的迭代算法，它不使用STL，也不使用递归，也不使用条件嵌套循环。这样更快，它不执行任何元素交换，也不会给堆栈带来递归负担，还可以通过分别用mallloc()、free()和printf()替换new、delete和std::cout轻松地移植到ANSI C。

如果你想用不同或更长的字母显示元素，那么改变*字母参数以指向不同于"abcdefg"的字符串。

void OutputArrayChar(unsigned int* ka, size_t n, const char *alphabet) {
    for (int i = 0; i < n; i++)
        std::cout << alphabet[ka[i]] << ",";
    std::cout << endl;
}
    

void GenCombinations(const unsigned int N, const unsigned int K, const char *alphabet) {
    unsigned int *ka = new unsigned int [K];  //dynamically allocate an array of UINTs
    unsigned int ki = K-1;                    //Point ki to the last elemet of the array
    ka[ki] = N-1;                             //Prime the last elemet of the array.
    
    while (true) {
        unsigned int tmp = ka[ki];  //Optimization to prevent reading ka[ki] repeatedly

        while (ki)                  //Fill to the left with consecutive descending values (blue squares)
            ka[--ki] = --tmp;
        OutputArrayChar(ka, K, alphabet);
    
        while (--ka[ki] == ki) {    //Decrement and check if the resulting value equals the index (bright green squares)
            OutputArrayChar(ka, K, alphabet);
            if (++ki == K) {      //Exit condition (all of the values in the array are flush to the left)
                delete[] ka;
                return;
            }                   
        }
    }
}
    

int main(int argc, char *argv[])
{
    GenCombinations(7, 4, "abcdefg");
    return 0;
}

重要提示:字母参数*必须指向至少N个字符的字符串。你也可以传递一个在其他地方定义的字符串地址。

组合:从“7选4”中选择。

下面是我的JavaScript解决方案，通过使用reduce/map，它消除了几乎所有变量，功能更强大

function combinations(arr, size) { var len = arr.length; if (size > len) return []; if (!size) return [[]]; if (size == len) return [arr]; return arr.reduce(function (acc, val, i) { var res = combinations(arr.slice(i + 1), size - 1) .map(function (comb) { return [val].concat(comb); }); return acc.concat(res); }, []); } var combs = combinations([1,2,3,4,5,6,7,8],3); combs.map(function (comb) { document.body.innerHTML += comb.toString() + '<br />'; }); document.body.innerHTML += '<br /> Total combinations = ' + combs.length;

不需要进行集合操作。这个问题几乎和循环K个嵌套循环一样，但你必须小心索引和边界(忽略Java和OOP的东西):

 public class CombinationsGen {
    private final int n;
    private final int k;
    private int[] buf;

    public CombinationsGen(int n, int k) {
        this.n = n;
        this.k = k;
    }

    public void combine(Consumer<int[]> consumer) {
        buf = new int[k];
        rec(0, 0, consumer);
    }

    private void rec(int index, int next, Consumer<int[]> consumer) {
        int max = n - index;

        if (index == k - 1) {
            for (int i = 0; i < max && next < n; i++) {
                buf[index] = next;
                next++;
                consumer.accept(buf);
            }
        } else {
            for (int i = 0; i < max && next + index < n; i++) {
                buf[index] = next;
                next++;
                rec(index + 1, next, consumer);
            }
        }
    }
}

像这样使用:

 CombinationsGen gen = new CombinationsGen(5, 2);

 AtomicInteger total = new AtomicInteger();
 gen.combine(arr -> {
     System.out.println(Arrays.toString(arr));
     total.incrementAndGet();
 });
 System.out.println(total);

获得预期的结果:

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10

最后，将索引映射到您可能拥有的任何数据集。