Générer tous les choix possibles d'éléments à partir d'un ensemble distinct

Question

Supposons que nous ayons k ensembles dont chacun contient q éléments. Je veux générer tous les ensembles possibles dans lesquels nous sélectionnons exactement 1 élément de chaque ensemble. Supposons que les ensembles sont représentés sous la forme d'une table où chaque ligne est un ensemble et ses colonnes sont ses éléments. Supposons également que tous les éléments sont indexés rangée par rangée de ce type

Set 1: 1 2 3

Set 2: 4 5 6

Set 3: 7 8 9

Le fait est que k, q peut varier, donc je ne peux pas utiliser les boucles imbriquées. Je travaille en C++ et cette structure est en fait std::vector de std::vector de int, mais je ne demande pas de code ici, juste une idée sur la façon de le faire.

Answer 1

récursive

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 récursif

L'idée principale est que chaque choix peut être codé par un nombre base- q système numérique Et tout ce que vous devez faire est de parcourir tous les numéros de base avec length <= n. Chaque chiffre du nombre est un index dans l'ensemble correspondant.

Par exemple, nous avons 2 ensembles avec 3 nombres. Vous devez parcourir par {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 2

Cela fait le travail?

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

Answer 3

Si vous n'êtes pas au courant du nombre d'ensembles et du nombre d'éléments dans chaque jeu, vous pouvez générer l'ensemble de tous les éléments que vous voulez de la manière suivante. Fondamentalement, vous pouvez faire une boucle sur tous les éléments d'un ensemble et l'inclure dans le précédent produit restant de tout ce qui a été calculé jusqu'ici. Faites-moi savoir si quelque chose ne sait pas encore

#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 4

Vous pouvez utiliser backtracking ici pour générer tous les sous-ensembles

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

Code de travail: http://ideone.com/RvHMNT

Answer 5

Une solution codée en dur serait

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

Pour le rendre générique, vous pouvez le faire:

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