c++ - N为大n和k选择k

我将n个元素存储在一个数组中，并且在n(n个选择k)上有k个可能的子集。
我必须在长度为n的数组中找到k个元素的所有可能组合，并针对每个集合(长度为k)，对所选元素进行一些计算。

我写了一个递归算法(在C++中)，可以很好地工作，但对于大量算法，它会崩溃而耗尽堆空间。

我该如何解决该问题？如何计算n和k大的所有n个集合？
有C++库可以帮助我吗？

我知道这是一个np问题，但是我会写最好的代码以便计算最大数目。

除了变得不可行之外，最大的数字(n和k)大约是多少？

我只要求最好的算法，而不要求不可行的空间/工作。

这是我的代码

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v)
{
    static int count = 0;
    cout << "combination no " << (++count) << ": [ ";
    for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
        cout << "] " << endl;
}

void go(int offset, int k)
{
    if (k == 0) {
        pretty_print(combination);
        return;
    }
    for (int i = offset; i <= people.size() - k; ++i) {
        combination.push_back(people[i]);
        go(i+1, k-1);
        combination.pop_back();
    }
}

int main() {
    int n = #, k = #;

    for (int i = 0; i < n; ++i) { people.push_back(i+1); }
        go(0, k);

    return 0;
}

最佳答案

这是非递归算法:

const int n = ###;
const int k = ###;

int currentCombination[k];
for (int i=0; i<k; i++)
    currentCombination[i]=i;
currentCombination[k-1] = k-1-1; // fill initial combination is real first combination -1 for last number, as we will increase it in loop

do
{
    if (currentCombination[k-1] == (n-1) ) // if last number is just before overwhelm
    {
        int i = k-1-1;
        while (currentCombination[i] == (n-k+i))
            i--;

        currentCombination[i]++;

        for (int j=(i+1); j<k; j++)
            currentCombination[j] = currentCombination[i]+j-i;
    }
    else
        currentCombination[k-1]++;

    for (int i=0; i<k; i++)
        _tprintf(_T("%d "), currentCombination[i]);
    _tprintf(_T("\n"));

} while (! ((currentCombination[0] == (n-1-k+1)) && (currentCombination[k-1] == (n-1))) );

关于c++ - N为大n和k选择k，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19327847/