13

この質問は、与えられた数のベクトルのデカルト積を計算する方法を尋ねます。ベクトルの数は事前にわかっていてかなり少ないため、ネストされたforループを使用して解を簡単に取得できます。

ここで、選択した言語で、ベクトルのベクトル（またはリストのリスト、セットのセットなど）が与えられたとします。

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

デカルト積を計算するように求められた場合、それは

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

再帰を続行します。たとえば、quick＆dirty pythonでは、

def cartesianProduct(aListOfLists):
    if not aListOfLists:
        yield []
    else:
        for item in aListOfLists[0]:
            for product in cartesianProduct(aListOfLists[1:]):
                yield [item] + product

それを繰り返し計算する簡単な方法はありますか？

（注：答えはPythonである必要はありません。とにかく、この質問のように、Pythonではitertoolsの方がうまく機能することを認識しています。）

4

4 に答える 4

21

1）0に初期化された、それぞれのリストにインデックスのリストを作成します。

indexes = [0,0,0,0,0,0]

2）各リスト（この場合は最初のリスト）から適切な要素を生成します。

3）最後のインデックスを1つ増やします。

4）最後のインデックスが最後のリストの長さと等しい場合は、それをゼロにリセットして1を実行します。キャリーがなくなるまでこれを繰り返します。

5）インデックスが[0,0,0,0,0,0]に戻るまで、手順2に戻ります。

各桁のベースが異なる可能性があることを除いて、カウントの仕組みと似ています。

上記のアルゴリズムのPythonでの実装は次のとおりです。

def cartesian_product(aListOfList):
    indexes = [0] * len(aListOfList)
    while True:
        yield [l[i] for l,i in zip(aListOfList, indexes)]
        j = len(indexes) - 1
        while True:
            indexes[j] += 1
            if indexes[j] < len(aListOfList[j]): break
            indexes[j] = 0
            j -= 1
            if j < 0: return

モジュロトリックを使用して実装する別の方法は次のとおりです。

def cartesian_product(aListOfList):
    i = 0
    while True:
        result = []
        j = i
        for l in aListOfList:
             result.append(l[j % len(l)])
             j /= len(l)
        if j > 0: return
        yield result
        i += 1

これにより、例とは少し異なる順序で結果が出力されることに注意してください。これは、リストを逆の順序で繰り返すことで修正できます。

于 2010-03-10T18:14:24.887 に答える
3

言語に依存しない解決策を求めたので、これはbashの解決策ですが、反復的、再帰的、それは何と呼ぶことができますか？それは単なる表記です：

echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13

多分十分に面白い。

1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ...
于 2011-03-03T06:25:33.603 に答える
2

0から\Pi a_i_lengthすべてに対して繰り返しますi。

for ( int i = 0; i < product; i++ ) {
    // N is the number of lists
    int now = i;
    for ( int j = 0; j < N; j++ ) {
        // This is actually the index, you can get the value easily.
        current_list[j] = now % master_list[j].length;

        // shifts digit (integer division)
        now /= master_list[j].length;  
    }
}

これを書くための簡単な方法もいくつかあるので、同じ作業を2回行う必要はありません。

于 2010-03-10T18:20:35.037 に答える
1

スタックを手動で管理する必要があります。基本的に、再帰が行うことを自分で行います。再帰は各再帰呼び出しに関するデータをスタックに置くので、同じことをするだけです。

Let L[i] = elements in vector i
k = 0;
st[] = a pseudo-stack initialized with 0
N = number of vectors 
while ( k > -1 )
{
  if ( k == N ) // solution, print st and --k

  if ( st[k] < L[k].count )
  {
    ++st[k]
    ++k
  }
  else
  {
    st[k] = 0;
    --k;
  }
}

テストされていませんが、アイデアは機能します。うまくいけば、私は何も見逃していませんでした。

編集：まあ、遅すぎると思います。これは基本的にカウントと同じですが、別の見方をします。

于 2010-03-10T18:31:12.770 に答える