假设我们有k集合，其中每个集合包含q元素。我想要生成所有可能的集合，其中我们从每个集合中精确选择一个元素。假设这些集合被表示为一个表格，其中每一行是一个集合，其列是它的元素。还假定所有元素被索引逐行这样生成不同集合中各元素的所有可能选项
组1：1 2 3
集2：4 5 6
组3：7 8 9
的事情是， k，q可能会有所不同，所以我不能使用嵌套for循环。我用C++工作，这个结构实际上是std::vector的std::vector的int，但我不是在这里要求代码，只是想法如何做到这一点。
递归
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编码数字系统。而你所需要做的就是遍历所有基数q号码与length <= n。该号码的每个数字都是相应组中的索引。
例如，我们有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;
}
您能否介绍一下非递归代码。 –
@GauravSehgal，在主循环的每一次迭代中，我们只需要在q-ary数字系统中获得'i'的数字，并将它们用作相应集合中的索引。 – DAle
这个假设pow（q，k）适合int，在某些设置和/或平台中可能太小。更好地使用unsigned long来处理i和cnt。另外，在一些嵌入式平台上，pow（）返回的“double”类型可能只有单精度。使用整数乘法计算for循环中的cnt可以节省时间。 –
这个工作吗？
std::vector<std::vector<int>> v;
for(auto& r : v)
for(auto i : r)
// use i
如果您不知道每个集合中的集合的数量和元素的数量，那么您可以按照以下方式生成所有元素的集合。基本上，您可以遍历集合中的所有元素，并将其包含在迄今为止已计算出的以前的剩余产品中。让我知道，如果事情还不清楚
#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));
}
}
}
}
OP不知道会有多少组。 –
@GauravSehgal yep，已更新 – Curious
您可以使用这里回溯产生的所有子集
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)
}
}
一个硬编码的解决办法是
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));
}
* “的事情是，K，Q可能会有所不同，所以我不能嵌套的for循环使用。” *为什么呢？ – CinCout
@CinCout我可能会错过一些东西，但我不知道有什么方法可以根据需要生成尽可能多的嵌套循环。就我而言，我需要k个嵌套循环。请解释。 – mgus
'k'和'q'各不相同，但已知对不对？在这个例子中，你给了，你将总共有27套。我只需要循环运行'q^k'次。有什么问题？ – CinCout