Rekursive Progammierung von Permutationen

[volter2]

Hallo,

Ich möchte Permutationen der Zahlen (1,2), (1,2,3), … rekursiv ausgeben.

Über YouTube (https://www.youtube.com/watch?v=XQ46IEOxaGc) habe ich eine Lösung nachprogrammiert:

Code: Alles auswählen

def permutationen(liste):
    if len(liste) <= 1:
        return [liste]
    else:
        return [[liste[i]] + P for i in range(len(liste)) for P in permutationen(liste[:i] + liste[i+1:])]

print(permutationen([1,2]))

Funktioniert, Ausgabe [[1, 2], [2, 1]] wie gewünscht.


Danach wollte ich es für Anfänger etwas verständlicher programmieren:

Code: Alles auswählen

def permutationen1(liste):
    if len(liste) <= 1:
        return [liste]
    else:
        for i in range(len(liste)):
            for P in permutationen1(liste[:i] + liste[i+1:]):
                return [[liste[i]] + P]

print(permutationen1([1,2]))

liefert nur die Ausgabe [[1, 2]]!?

Ich sehe leider den Fehler nicht, bzw. den Unterschied zur ersten Version.


Vielen Dank im Voraus!

[__blackjack__]

@volter2: Das hat eigentlich nichts mit Rekursion zu tun. Du hast die „list comprehension“ (LC) falsch in ``for``-Schleifen übersetzt. So eine LC erzeugt ja eine Liste. Das tust Du in den ``for``-Schleifen aber nicht. Du müsstest da mit einer leeren Liste starten und in den Schleifen Elemente hinzufügen, und danach erst die so erstellte Liste mit ``return`` zurückgeben. Schau Dir das zum Beispiel im Tutorial in der Python-Dokumentation noch mal an.

[ThomasL]

so zum Beispiel
Finde dieses Tutorial http://treyhunner.com/2015/12/python-li ... -in-color/ ganz gut.

Code: Alles auswählen

def permutationen(liste):
    if len(liste) <= 1:
        return [liste]
    else:
        return [ [liste[i]] + P
                 for i in range(len(liste))
                 for P in permutationen(liste[:i] + liste[i+1:])]

print(permutationen([1,2,3]))

def permutationen2(liste):
    if len(liste) <= 1:
        return [liste]
    else:
        perm = []
        for i in range(len(liste)):
            for P in permutationen(liste[:i] + liste[i+1:]):
                perm.append([liste[i]] + P)
        return perm

print( permutationen([1,2,3]) == permutationen2([1,2,3]) )

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
True

[volter2]

Vielen Dank für Eure Hilfe, das habe ich nun verstanden