Генерация всех возможных вариантов элементов каждого из отдельного набора
Предположим, что у нас есть k наборы, каждый из которых содержит q элементы. Я хочу сгенерировать все возможные наборы, в которых мы выбираем ровно 1 элемент из каждого набора. Предположим, что наборы представлены в виде таблицы, где каждая строка является набором, а ее столбцы являются ее элементами. Также предположим, что все элементы индексируются построчно, как это
Комплект 1: 1 2 3
Комплект 2: 4 5 6
Комплект 3: 7 8 9
Дело в том, что k, q могут варьироваться, поэтому я не могу использовать вложенные циклы. Я работаю в 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;
}
Другие решения
Жестко закодированное решение будет
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));
}
Это делает работу?
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));
}
}
}
}
Вы можете использовать обратный трекинг здесь для генерации всех подмножеств
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
detector