1

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

我编写了一个递归算法（在 C++ 中），它工作得很好，但是对于大量它会崩溃，因为堆空间不足。

我该如何解决这个问题？如何计算所有 n 的集合，为大 n 和 k 选择 k？是否有任何 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;
}
4

4 回答 4

2

这是非递归算法：

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))) );
于 2013-10-11T23:09:18.263 回答
1

您的递归算法可能会破坏堆栈。如果你使它成为非递归的，那会有所帮助，但如果你的情况真的是 100 选择 10，它可能不会解决问题。你有两个问题。世界上很少有计算机拥有超过 17 TB 的内存。经历 17 万亿次以上的迭代来生成所有组合将花费太长时间。你需要重新考虑这个问题，或者提出一个更合理的 N 选择 K 案例，或者只处理组合的某个子集。

您可能最多不希望处理超过 10 亿或两个组合 - 即使这样也需要一些时间。这意味着大约 41 个选择 10 到大约 44 个选择 10。减少 N 或 K 将有所帮助。尝试编辑您的问题并发布您要解决的问题以及您认为需要完成所有组合的原因。可能有一种方法可以在不经过所有组合的情况下解决它。

如果事实证明您确实需要检查所有这些组合，那么也许您应该考虑使用诸如遗传算法或模拟退火之类的搜索技术。这两种爬山搜索技术都提供了在相对较短的时间内搜索大空间以获得接近最优解的能力，但都不能保证找到最优解。

于 2013-10-11T23:00:34.020 回答
0

您可以使用next_permutation()inalgorithm.h生成所有可能的组合。

这是一些示例代码：

bool is_chosen(n, false);
fill(is_chosen.begin() + n - k, is_chosen.end(), true); 
do
{
    for(int i = 0; i < n; i++)
    {
        if(is_chosen[i])
            cout << some_array[i] << " ";
    }
    cout << endl;
} while( next_permutation(is_chosen.begin(), is_chosen.end()) );

不要忘记包含算法。

于 2013-10-12T00:51:48.080 回答
0

正如我在评论中所说，目前尚不清楚您真正想要什么。

  1. 如果您想计算（n 选择 k）相对较小的值，例如n,k < 100 左右，您可能需要使用递归方法，使用帕斯卡三角形。

  2. 如果n,k很大（例如n=1000000, k=500000），您可能会对使用 Sterlings 阶乘公式的近似结果感到满意： ( n choose k ) = exp(loggamma(n)-loggamma(k)-loggamma(n-k))，loggamma(x)通过 Sterling 公式计算。

  3. 如果您想要 ( n 选择 k ) 用于所有或许多k但相同的n，您可以简单地迭代k并使用 ( n 选择 k+1 ) = (( n 选择 k )*( nk ))/( k+1）。

于 2013-10-12T10:29:03.853 回答