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

Question

We have a set of objects indexed by integers and need to generate a list of pairs of possible combinations of these objects (of any length up to the number of objects) with a constraint. The constraint is that if one combination in a pair contains an object, then the other combination in that pair cannot also contain that object.

As an example, if we have only 3 objects { 0, 1, 2}, the list should look like

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

What is a computationally efficient way of generating this list for as many as 20 objects in C++?

Answer 1

Here's a recursive version that takes each combination in the powerset with more than one element and runs a "put in one bag or the other" routine. (It's pretty much my first time trying to code anything more than trivial in C++ so I imagine there may be room for improvement.)

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}}

Code (also 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;
}

Answer 2

Firstly we can decide which element will be in our pairs. For example, if the number of element is 3, consider the binary representation from 0 to 2^3.

0=000
1=001
2=010
3=011
4=100
5=101
6=110
7=111

Now, we will make the pair from each number from 0 to 2^n by keeping the elements in which position the number has 1. Like 3=011, its first and second position have 1, so we will make a pair with first and second element.For 6=110,we will make the pair with second and third element. So, we can decide which element we will take in our each pair through 2^n complexity, where n is the number of element.

Now we know which element will be in each pair. For example, let for one pair we selected m elements. Now we need to divide them within each side. We can do it like the similar way by considering binary representation of all numbers from m elements. If m=3,

    0=000
    1=001
    2=010
    3=011
    4=100
    5=101
    6=110
    7=111

So from each number from 0 to 2^m, we can make a pair. For making a pair from a number , we will keep the elements in first set which index has 0 in that number and will keep in the second set which index has 1 in that number. C++ code:

#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;
}

Output:

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

Answer 3

In each pair, every object is either not used, or it's in the left set, or it's in the right set.

If you have N objects, you can easily iterate through the 3^N possibilities, skipping the ones that result in empty sets:

#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;
}

If unsigned is 32 bits, this will work for up to 20 objects. Note that it will print about 3.5 billion pairs in that case, though.

Try it here: https://ideone.com/KIeas7