再帰を使用したセットのクロス積

Question

次の再帰ルーチンを使用して、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)] 

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

編集：何か内蔵のソリューションを探していません。どのように再帰を行うかを探して、itertools.productを使用しないでください。

Answer 1

使用itertools

import itertools 

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

意味的にこれはと同等です：

nはあなたが productに渡す引数の数である

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 

。

Answer 2

デカルト製品の最も単純な再帰的定義は、このように見えると思います。あなたのように、これはループを持っています - 実際には、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() == [[]] - see hereです。

ここで、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]] 

パターンはそこから続きます。各追加シーケンスについて、シーケンス内の各値は、以下のシーケンスのデカルト積における各値に付加される。