algorithm - 什么是计算有效的方法来生成具有某些限制的大量组合列表？

Question

我们有一组由整数索引的对象，需要生成这些对象的可能组合对的列表(任意长度，最多可达对象数量)并具有约束。约束是，如果一对组合中的一个组合包含一个对象，则该对中的另一个组合不能也包含该对象。

例如，如果我们只有 3 个对象 { 0, 1, 2}，则列表应如下所示

{ {0}, {1} }
{ {0}, {2} }
{ {1}, {2} }
{ {0,1}, {2} }
{ {0}, {1,2} }
{ {0,2}, {1} }

在 C++ 中为多达 20 个对象生成此列表的计算效率高的方法是什么？

Answer 1

在每一对中，每个对象要么未使用，要么位于左集中，要么位于右集中。

如果您有 N 个对象，您可以轻松迭代 3^N 种可能性，跳过导致空集的对象:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    unsigned N = 5; //number of objects
    vector<unsigned> left, right;

    for (unsigned index=0 ;; ++index) {
        left.clear();
        right.clear();

        //treat the index as a number in base 3
        //each digit determines the fate of one object
        unsigned digits=index;
        for (int obj=1; obj<=N; ++obj) {
            unsigned pos=digits%3;
            digits /= 3;
            if (pos == 1)
                left.push_back(obj);
            else if (pos == 2)
                right.push_back(obj);
        }

        if (digits) {
            //done all possibilities
            break;
        }

        if (left.empty() || right.empty()) {
            // don't want empty left or right
            continue;
        }

        //got one -- print it
        cout << "{ {" <<left[0];
        for (size_t i=1; i<left.size(); ++i)
            cout << "," << left[i];
        cout << "}, {" <<right[0];
        for (size_t i=1; i<right.size(); ++i)
            cout << "," << right[i];
        cout << "} }" << endl;
    }
    return 0;
}

如果 unsigned 是 32 位，则最多适用于 20 个对象。请注意，在这种情况下，它将打印大约 3.5 亿对。

在这里试试:https://ideone.com/KIeas7