假設我們有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