Rekursive Progammierung von Permutationen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
volter2
User
Beiträge: 2
Registriert: Samstag 21. Juli 2018, 20:50

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!
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@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.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

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
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
volter2
User
Beiträge: 2
Registriert: Samstag 21. Juli 2018, 20:50

Vielen Dank für Eure Hilfe, das habe ich nun verstanden :-)
Antworten