1

アイテムを含むn個のinputListがあります。次に、元のinputLists内のアイテムのすべての組み合わせを含むresultLists（長さn）を計算します（各inputListの1つのアイテムを取得します）。

ここに例を示す必要があると思います（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]

私はちょっとばかげていると感じていますが、任意のnと任意のinputListの長さに対してこれらの結果を作成する関数（C ++）を実装する方法がわかりません。ある種の再帰を使うべきだと思いますが、その方法がわかりません。
何か案は？

4

2 に答える 2

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上記の例) を格納するコンテナーをパラメーターとして受け入れる必要があります。

それが役立つことを願っています。

于 2012-05-08T15:44:59.633 に答える
0

イテレータはここでの友達です。エラーチェックやゼロサイズのリストなどのコーナーケースを気にしない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配列は整数を複数の基数に分解したものにすぎないことに気付くかもしれません。これは2番目の解決策につながります：

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

どちらがベスト/速いかについては、私にはよくわかりません。

于 2012-05-08T16:07:34.093 に答える