Permutation in Python - Vorlage

Question

Ich möchte Funktion für jede mögliche Permutation eines Arrays erstellen. Ich habe einen Code geschrieben und ich weiß nicht, was damit nicht stimmt. Es gibt mir erste Möglichkeit = [1,2,3], aber dann scheitert es mit Fehler: Original [i] aus dem Index, aber es sollte original [1] sein, die gleich 2 ist. Vielleicht del löscht auch vom Original aber das würde macht keinen Sinn für mich.

Vielen Dank in advace.

array = [1,2,3] 
out = [] 

def permutacja(original,perm): 
    if(len(original) == 0): 
     print(perm) 
     return perm 

    temp = original 
    for i in range(0,len(original)): 
     perm.append(original[i]) 
     del temp[0] 
     permutacja(temp,perm) 
     del perm[len(perm)-1] 

permutacja(array,out) 

Answer 1

Python Standard-Bibliothek-Modul itertools bieten itertools.permutations die Permutationen ergibt:

>>> import itertools 
>>> for xs in itertools.permutations([1,2,3]): 
...  print(xs) 
... 
(1, 2, 3) 
(1, 3, 2) 
(2, 1, 3) 
(2, 3, 1) 
(3, 1, 2) 
(3, 2, 1) 

Answer 2

Sie besser itertools für diesen Einsatz, da diese gut optimiert und getestet Routinen. Dennoch, wenn Sie es selbst implementieren wollen, gibt es einige Dinge, die verbessert werden können/korrigiert:

• Sie return ein Wert, aber nur in der letzten rekursiven Schritt müssen Sie propagieren sie zurück;
• Sie eine Referenz auf die Liste, die Sie im laufenden Betrieb erstellen zurück, als Ergebnis werden Sie immer die gleiche Liste zurückgeben;
• Sie immer del Ete die erste Element, nicht die, die Sie ausgewählt haben; und
• Sie tun nicht wiederherstellen das Element nach dem Löschen.

def permutacja(original,perm): 
    if(len(original) == 0): 
     print(perm) 
     yield perm.copy() # emit instead of return for proagation 
    else: 
     temp = original 
     for i in range(0,len(original)): 
      perm.append(original[i]) 
      temp = original[:i]+original[i+1:] #remove the i-th 
      for result in permutacja(temp,perm): 
       yield result # propagate back 
      del perm[len(perm)-1] 
      # because we copy original, no need to restore 

Einige additonal Verbesserungen:

• Verwendung .pop() statt del auf dem letzten Element; und
• Sie einfach if original anstelle eines Vergleichs auf len(..) verwenden:

def permutacja(original,perm): 
    if original: 
     print(perm) 
     yield perm.copy() 
    else: 
     temp = original 
     for i in range(0,len(original)): 
      perm.append(original[i]) 
      temp = original[:i]+original[i+1:] #remove the i-th 
      for result in permutacja(temp,perm): 
       yield result # propagate back 
      perm.pop() 
      # because we copy original, no need to restore