生成具有特定约束的大量组合列表的计算效率高的方法是什么？

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

Answer 2

首先我们可以决定哪个元素将成为我们的对。比如元素个数为3，考虑二进制表示从0到2^3.

现在，我们将从 0 到 2^n 的每个数字组成对，方法是保留数字位置为 1 的元素。像 3=011，它的第一个和第二个位置都有 1，所以我们将第一个和第二个 element.For 6=110 的对，我们将用第二个和第三个元素组成对。因此，我们可以通过 2^n 的复杂度来决定我们将在每一对中取哪个元素，其中 n 是元素的数量。

现在我们知道每对中将包含哪个元素了。例如，对于一对，我们选择了 m 个元素。现在我们需要在每一边划分它们。我们可以通过考虑来自 m 个元素的所有数字的二进制表示来以类似的方式做到这一点。如果m=3,

所以从 0 到 2^m 的每个数字，我们可以组成一对。为了从数字中生成一对，我们将保留第一组中索引在该数字中具有 0 的元素，并将保留在第二组中索引在该数字中具有 1 的元素。 C++代码：

#include<bits/stdc++.h>
using namespace std;


int main()
{
    long long  cnt=0;
    int n;
    cin>>n;
    int object[n];
    for(int i=0; i<n; i++)cin>>object[i];

    for(int i=0; i<(1<<n); i++){
        // From each i, we will decide which element will be in our set.
        int c=0;
        int nu=0;
        int one_pair[n];
        // Now we will calculate , how many elements will be in current pair.
        for(int j=0; j<n; j++)if((i&(1<<j)))one_pair[c++]=object[j];
        if(c>=2){
            // So we have c element in each pair 
            for(int k=1; k<(1<<(c-1)); k++){
                //Now we will divide each of the c element within two sides.
                cout<<"{ {";
                bool fl=0;
                for(int divider=0;divider<c;divider++){
                   if((k&(1<<divider))){
                        if(fl)cout<<",";
                        fl=1;
                        cout<<one_pair[divider];
                   }
                }

                cout<<"}, ";
                cout<<"{";
                fl=0;
                for(int divider=0;divider<c;divider++){
                   if((k&(1<<divider))==0){
                        if(fl)cout<<",";
                        fl=1;
                        cout<<one_pair[divider];
                   }
                }
                cout<<"} }"<<endl;
            }
        }
    }
    return 0;
}

输出：

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

Answer 3

这是一个递归版本，它采用包含多个元素的幂集中的每个组合并运行 "put in one bag or the other" 例程。（这几乎是我第一次尝试用 C++ 编写比琐碎的代码更多的代码，所以我想可能还有改进的余地。）

Powerset:
{{0, 1, 2}, {0, 1}, {0, 2}, {0}, {1, 2}, {1}, {2}, {}}

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

{{0}, {1}}

{{0}, {2}}

{{1}, {2}}

代码（也here）：

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

void print(std::vector<int> const &input){
      std::cout << '{';
      for (int i = 0; i < input.size(); i++) {
        std::cout << input.at(i);
        if (i < input.size() - 1)
          std::cout << ", ";
      }
      std::cout << '}';
}
void printMany(std::vector< std::vector<int> > const &input)
{
    std::cout << '{';
    for (int i = 0; i < input.size(); i++) {
      print(input.at(i));
      if (i < input.size() - 1)
        std::cout << ", ";
    }
    std::cout << '}';
    std::cout << '\n';
}
void printPairs(std::vector< std::vector<int> > const &input)
{
    for (int i = 0; i < input.size(); i+=2) {
      cout << '{';
      print(input.at(i));
      cout << ", ";
      print(input.at(i + 1));
      cout << "}\n";
    }
}

std::vector< std::vector<int> > f(std::vector<int> const &A, int i, const std::vector<int> &left, const std::vector<int> &right) {
  if (i == A.size() - 1 && right.empty())
    return std::vector< std::vector<int> >{left, std::vector<int> {A[i]}};
  if (i == A.size())
    return std::vector< std::vector<int> > {left, right};

  std::vector<int> _left{ left };
  _left.emplace_back(A[i]);
  std::vector< std::vector<int> > result = f(A, i + 1, _left, right);
  std::vector<int> _right{ right };
  _right.emplace_back(A[i]);
  std::vector< std::vector<int> > result1 = f(A, i + 1, left, _right);
  result.insert( result.end(), result1.begin(), result1.end() );
  return result;
}

std::vector< std::vector<int> > powerset(std::vector<int> const &A, const vector<int>& prefix = vector<int>(), int i = 0) {
  if (i == A.size())
    return std::vector< std::vector<int> > {prefix};

  std::vector<int> _prefix(prefix);
  _prefix.emplace_back(A[i]);
  std::vector< std::vector<int> > result = powerset(A, _prefix, i + 1);
  std::vector< std::vector<int> > result1 = powerset(A, prefix, i + 1);
  result.insert( result.end(), result1.begin(), result1.end() );
  return result;
}

int main() {
  std::vector<int> A{0, 1, 2};
  std::vector< std::vector<int> > ps = powerset(A);
  cout << "Powerset:\n";
  printMany(ps);
  cout << "\nResult:\n";
  for (int i=0; i<ps.size(); i++){
    if (ps.at(i).size() > 1){
      std::vector<int> left{ps.at(i)[0]};
      std::vector<int> right;
      printPairs(f(ps.at(i), 1, left, right));
    }
  }
  return 0;
}

生成具有特定约束的大量组合列表的计算效率高的方法是什么？

What is a computationally efficient way to generate a list of a large number of combinations with certain restraints?

algorithm

combinatorics