7

2 つのセットの外積を計算するために、次の再帰ルーチンを作成しました。

def combine(input1,input2,output):
    if len(input2)==0:
        return output
    else:
       for num in input1:
           output.append((num,input2[0]))
       combine(input1,input2[1:],output)

input1=[1 2 5]
input2=[2 3]
output=[(1,2), (1,3), (2,2),(2,3),(5,2),(5,3)]

たとえば、else でループを削除し、同じ関数で実行しようとするなど、再帰を改善することは可能ですか。問題を解決するさまざまな方法を検討しています。

編集：何かが組み込まれたソリューションを探していません。itertools.productを使用せずに、再帰を別の方法で行う方法を探しています。

4

2 に答える 2

9

私が考えることができるデカルト積の最も単純な再帰的定義は次のようになります。あなたと同じように、これにはループがあります。実際には、リスト内包表記に 2 つのループが埋め込まれています。あなたのものとは異なり、これは 2 つ以上のシーケンスを処理できます。

def product(*seqs):
    if not seqs:
        return [[]]
    else:
        return [[x] + p for x in seqs[0] for p in product(*seqs[1:])]

これがどのように機能するかを理解するためのウォークスルーです。定義により、空のシーケンスのデカルト積 ( product()) は、空のシーケンスを含むシーケンスです。つまり、product()== [[]]--理由についてはこちらを参照してください。

product([1, 2, 3])--seqsが空ではないので、戻り値はリスト内包表記の結果であるとしましょう。この場合、product(*seqs[1:])== product(*[])== product()==[[]]であるため、リスト内包表記は次と同等です。

[[x] + p for x in seqs[0] for p in [[]] ]

これはこれらすべてと同等です:

[[x] + [] for x in seqs[0]]
[[x] for x in seqs[0]]
[[1], [2], [3]]

別のシーケンスを追加すると、 が得られproduct([4, 5, 6], [1, 2, 3])ます。リスト内包表記は次のようになります。

[[x] + p for x in [4, 5, 6] for p in product(*seqs[1:])]
[[x] + p for x in [4, 5, 6] for p in [[1], [2], [3]]]
[[4, 1], [4, 2], [4, 3], [5, 1], [5, 2], [5, 3], [6, 1], [6, 2], [6, 3]]

そこからパターンが続きます。追加のシーケンスごとに、シーケンス内の各値が、次のシーケンスのデカルト積内の各値の前に追加されます。

于 2013-02-27T00:34:03.453 に答える
2

itertools を使用する

import itertools

print list(itertools.product(input1, input2))

意味的には、これは次と同等です。

for i_1 in input_1:
    for i_2 in input_2:
        for i_3 in input_3:
            ...
                for i_n in input_n:
                    #do something with i_1, i_2, i_3, ..., i_n

n は に渡す引数の数ですproduct。

于 2013-02-26T21:35:12.750 に答える