Kreuzprodukt von Mengen mit Rekursion

Question

Ich schrieb die folgende rekursive Routine, um Kreuzprodukt von zwei Mengen zu berechnen.

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

Ist es möglich, die Rekursion besser, zum Beispiel, um die Schleife in sonst zu entfernen und zu versuchen, in gleicher Funktion zu tun. Ich schaue mir verschiedene Wege an, um das Problem zu lösen.

Edit: Keine Suche nach einer Lösung mit etwas eingebaut. Suchen nach, wie ich Rekursion anders tun kann, und nicht itertools.product.

Answer 1

Verwenden itertools

import itertools 

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

Semantisch ist dies gleichbedeutend mit:

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 

wobei n die Anzahl der Argumente ist, dass Sie zu product passieren.

Answer 2

Die einfachste rekursive Definition des kartesischen Produkts, die ich mir vorstellen kann, sieht so aus. Sie können sehen, dass wie bei Ihnen, das hat eine Schleife - eigentlich zwei Schleifen in einem Listenverständnis eingebettet. Im Gegensatz zu Ihnen, kann damit umgehen zwei oder mehr Sequenzen:

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

Hier ist ein Freilos, um Ihnen einen Eindruck davon, wie es funktioniert. Per Definition ist das kartesische Produkt einer leeren Sequenz (product()) eine Sequenz, die die leere Sequenz enthält. Mit anderen Worten, product() == [[]] - see here für warum.

Nehmen wir jetzt an, wir rufen product([1, 2, 3]) - seqs ist nicht leer, so dass der Rückgabewert das Ergebnis des Listenverständnisses ist. In diesem Fall product(*seqs[1:]) == == product(*[])product() == [[]], so dass die Liste Verständnis entspricht dies:

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

, die für alle von ihnen entspricht:

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

andere Sequenz Hinzufügen, wir haben product([4, 5, 6], [1, 2, 3]). Jetzt sieht das Listenverständnis so aus:

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

Das Muster fährt von dort fort; für jede zusätzliche Sequenz wird jeder der Werte in der Sequenz jedem der Werte in dem kartesischen Produkt der folgenden Sequenzen vorangestellt.