使用遞歸的集合的交叉積

Question

我寫了下面的遞歸例程來計算兩個集合的交叉乘積。

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)) 

語義這相當於：

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參數的個數。

Answer 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]] 

模式從那裏繼續;對於每個附加序列，將序列中的每個值都預置於以下序列的笛卡爾乘積中的每個值。