c++组合论

Question

我需要一段C++代码来生成所有可能的组合(n,k)，其中n--输入数组中的整数。k--位置数。

比如输入：

n = [1 2 3];
k = 2;

输出。

A3 =

     1     1
     1     2
     1     3
     2     1
     2     2
     2     3
     3     1
     3     2
     3     3

谢谢，我需要一个C++代码来生成所有可能的组合(n,k)，其中n-输入数组中的整数。

Answer 1

参见我的答案。

PHP取所有组合

这是PHP；但概念（递归等）应该很容易 "翻译"......。

Answer 2

使用 标准库:

do {
    for(int i = 0; i < k; i++){
        std::cout << n[i];
    }
    std::cout << '\n';
} while (std::next_permutation(n, n + k));

Answer 3

这基本上是以n-1为基数进行计数（其中每一位数字都移位1），可以试试下面的方法。

编辑： vector 而不是 new[], delete[]

#include <vector>

void generatePerms(int n, int k)
{
    vector<int> perms(k, 1);

    //iterate through all permutations
    bool done;
    do {
        //Do something with the current permutation, for example print it:
        for (int i = 0; i < k-1; i++)
            cout << perms[i] << ", ";
        cout << perms[k-1] << endl;

        /*
         * Increment last digit first - if it's to big, reset to 1 and
         * carry one (increment next digit), which may also carry one etc.
         *
         * If all digits caused a carry, then the permutation was n, n, ..., n,
         * which means, that we can stop.
         */
        done = true;
        for (int i = k-1; i >= 0; i--) {
            if (++perms[i] > n) {
                perms[i] = 1;
                continue;
            } else {
                done = false; //not all digits caused carry
                break;
            }
        }
    } while (!done);
}