从不同的集合中生成所有可能的元素选择

Question

假设我们有 k 个集合，每个集合包含 q 个元素。我想生成所有可能的集合，其中我们 select 每个集合中恰好有 1 个元素。假设集合表示为 table，其中每一行都是一个集合，其列是其元素。还假设所有元素都像这样按行索引

组 1: 1 2 3

第 2 组：4 5 6

第 3 组：7 8 9

问题是 k,q 可能会有所不同，所以我不能使用嵌套的 for 循环。我在 C++ 中工作，这个结构实际上是 std::vector of std::vector of int 的 std::vector，但我不是在这里要求代码，只是关于如何执行此操作的想法。

Answer 1

这样做有用吗？

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

Answer 2

如果您不知道集合的数量和每个集合中元素的数量，那么您可以通过以下方式生成您想要的所有元素的集合。基本上，您可以遍历一个集合的所有元素，并将其包含在到目前为止已计算的任何剩余产品中。如果还有什么不清楚的地方，请告诉我

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

Answer 3

递归

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

非递归

主要思想是每个选择都可以用基数 q 数字系统中的数字编码。您需要做的就是用 length <= n 遍历所有以 q 为基数的数字。数字的每一位都是相应集合中的索引。

例如，我们有 2 组 3 个号码。您需要遍历 {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

Answer 4

你可以在这里使用回溯来生成所有的子集

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

工作代码：http://ideone.com/RvHMNT

Answer 5

硬编码解决方案是

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

要使其通用，您可以这样做：

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

从不同的集合中生成所有可能的元素选择

Generate all possible choices of elements each from a distinct set

c++

algorithm

set

cartesian-product