リストアイテムの組み合わせを見つける

Question

アイテムを持つinputListsがn個あります。 ここでは、元のinputLists（各inputListの1つの項目を取る）の項目のすべての組み合わせを含むresultLists（長さn）を計算します。

私はここに例を提供すべきだと思う（N = 3）：

inputList1: [item1, item2, item3] 
inputList2: [item4] 
inputList3: [item5, item6] 

resultList1: [item1, item4, item5] 
resultList2: [item1, item4, item6] 
resultList3: [item2, item4, item5] 
resultList4: [item2, item4, item6] 
resultList5: [item3, item4, item5] 
resultList6: [item3, item4, item6] 

私は愚かなのようなものを感じているが、私は（C++）を実装する方法が分からない機能がために、これらの結果を作成します任意のnおよび任意のinputListの長さ。私は何らかの再帰を使用すべきだと思うが、どういうことかわからない。
アイデア

Answer 1

擬似コードで一般的な考え方、：

vector<item> List1, List2, List3; 
// fill the lists 

vector<item> v; 
vector<vector<item>> results; 

for each item i in List1 
{ 
    v.push_back(i) 
    for each item j in List2 
    { 
     v.push_back(j); 
     for each item k in List3 
     { 
      v.push_back(k); 
      results.push_back(v); 
      v.pop_back(); 
     } 
     v.pop_back(); 
    } 
    v.pop_back(); 
} 

リストの可変数でこれを行うには、私は再帰的なアプローチで行くと思います。各forループは、再帰関数呼び出しに置き換えられます。この関数は、inputListのリスト、結果リスト、および中間結果（上記の例ではv）をパラメータとして格納するコンテナを受け入れる必要があります。

希望に役立ちます。

Answer 2

イテレータはあなたの友人です。ゼロサイズのリストまたは同類のようなエラーチェックやコーナーケースを気にせずに2つの擬似コードのバージョン：

struct cartesian_product_iterator { 
    int indexes[n] initialized to zeroes 
    operator++() { 
     a = 0 
     indexes[a]++; 
     while a < n and indexes[a] >= list[a].size() 
      indexes[a] = 0 
      a++; 
    } 
    operator *() { 
     list<?> ret; 
     for a in 0..n-1: 
      ret.push_back(list[a][indexes[a]]); 
     return ret; 
    } 
    past_the_end_iterator() { indexes[n-1] = list[n-1].size(); } 
} 

あなたはindexes配列は、複数の拠点への整数のちょうど分解であることに気づくかもしれません。

struct cartesian_product_iterator_2 { 
    unsigned_or_arbitrarly_big_int a_large_number = 0; 
    operator ++() { a_large_number++; } 
    operator *() { 
     list<?> ret; 
     unsigned_or_arbitrarly_big_int to_decompose = a_large_number; 
     for a in 0..n-1: 
      index = to_decompose % list[a].size(); 
      to_decompose /= list[a].size(); 
      ret.push_back(list[a][index]); 
     } 
     return ret; 
    } 
    past_the_end_iterator() { 
     a_large_number = 1; 
     for each l in list: 
      a_large_number *= l.size(); 
    } 
} 

どちらが最良であるか、またはより速いかについては、私は実際には考えていません。