CODEWITHSUNDEEP
c++algorithmsetcartesian-product
mgus
mgus

Reputation: 808

Generate all possible choices of elements each from a distinct set

Suppose that we have k sets each of which contains q elements. I want to generate all possible sets in which we select exactly 1 element from each set. Assume that the sets are represented as a table where each row is a set and its columns are its elements. Also assume that all elements are indexed row-wise like this

Set 1: 1 2 3

Set 2: 4 5 6

Set 3: 7 8 9

The thing is that k,q may vary so I cannot use nested for loops. I work in C++ and this structure is actually a std::vector of std::vector of int, but I am not asking for code here, just an idea on how to do this.

Upvotes: 0

Views: 174

Answers (5)

Jarod42
Jarod42

Reputation: 217478

A hard coded solution would be

for (int a1 : v[0]) {
  for (int a2 : v[1]) {
    for (int a3 : v[2]) {
      for (int a4 : v[3]) {
        for (int a5 : v[4]) {
            do_job(a1, a2, a3, a4, a5);
        }
      }
    }
  }
}

To make it generic, you may do:

bool increase(const std::vector<std::set<int>>& v,
              std::vector<std::set<int>::iterator>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] == v[index].end()) {
            it[index] = v[index].begin();
        } else {
            return true;
        }
    }
    return false;
}

template <typename F>
void iterate(const std::vector<std::set<int>>& v, F&& do_job)
{
    std::vector<std::set<int>::iterator> its;
    its.reserve(v.size());
    for (auto& s : v) {
        its.push_back(s.begin());
    }

    do {
        do_job(its);
    } while (increase(v, its));
}

Demo

Upvotes: 1

DAle
DAle

Reputation: 9117

Recursive

using sets = vector<vector<int>>;

void rec(int index, const sets& s, vector<int>& v) {
    for (int next : s[index]) {
        v[index] = next;
        if (index + 1 == s.size()) {
            output(v);
        } else {
            rec(index+1, s, v);
        }
    }
}

int main() {
    sets s = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int q = s[0].size();
    vector<int> v(q);
    rec(0, s, v);
    return 0;
}

Non recursive

The main idea is that every choice can be encoded by a number in base-q numeral system. And all you need to do is to iterate through all base-q numbers with length <= n. Every digit of the number is an index in the corresponding set.

For example, we have 2 sets with 3 numbers. You need to iterate through {00, 01, 02, 10, 11, 12, 20, 21, 22}. 

using sets = vector<vector<int>>;

void non_rec(const sets& s) {
    int q = s[0].size();
    int k = s.size();
    vector<int> v(q);
    int cnt = (int)pow(q, k);

    for (int i = 0; i < cnt; ++i) {
        int tmp = i;
        for (int j = 0; j < k; ++j) {
            v[j] = s[j][tmp % q];
            tmp /= q;
        }
        output(v);
    }
}

int main() {
    sets s = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    non_rec(s);
    return 0;
}

http://ideone.com/V58I7W

Upvotes: 2

Gaurav Sehgal
Gaurav Sehgal

Reputation: 7542

You can use backtracking here to generate all subsets

  void func(vector<vector<int> > arr,int row,vector<int> &temp,vector<vector<int> > &ans)
  {
    if(row>=arr.size())
    {
        ans.push_back(temp);    //You have generated one of the answers.store it
        return;
    }
    for(int i=0;i<arr[row].size();i++)
    {
        temp.push_back(arr[row][i]);  //Pick an element from current set
        func(arr,row+1,temp,ans);     //recurse for next set
        temp.pop_back();              //Remove from current set to include next element from this set(for loop)
    }
  }

Working code: http://ideone.com/RvHMNT

Upvotes: 0

Curious
Curious

Reputation: 21510

If you are unaware of the number of sets and of the number of elements in each set, then you can generate the set of all elements you want the following way. Basically, you can loop over all the elements of a set and include that in the previous remaining product of whatever had been computed so far. Let me know if something is still unclear

#include <iostream>
#include <set>
#include <tuple>
#include <vector>

using std::cout;
using std::endl;

void append_results(const std::set<int>& set,
                    std::vector<std::vector<int>>& results);

int main() {

    auto sets = std::vector<std::set<int>>{
        std::set<int>{1, 2, 3},
        std::set<int>{4, 5, 6},
        std::set<int>{7, 8, 9}
    };

    auto results = std::vector<std::vector<int>>{};

    for (const auto& set : sets) {
        append_results(set, results);
    }

    for (const auto& result : results) {
        for (auto integer : result) {
            cout << integer << " ";
        }
        cout << endl;
    }

    return 0;
}

void append_results(const std::set<int>& set,
                    std::vector<std::vector<int>>& results) {

    if (results.empty()) {
        for (auto integer : set) {
            results.push_back(std::vector<int>{integer});
        }
    } else {
        auto old_results = results;
        results.clear();
        for (auto integer : set) {
            for (auto old_result : old_results) {
                old_result.push_back(integer);
                results.push_back(std::move(old_result));
            }
        }
    }
}

Upvotes: 0

Passer By
Passer By

Reputation: 21160

This does the job?

std::vector<std::vector<int>> v;
for(auto& r : v)
    for(auto i : r)
        // use i

Upvotes: 0

Related Questions