Muster in Pfad von Kombinationen ohne Wiederholungen

  • Guten Tag,


    ich sitze vor folgender Aufgabe:






    Ich habe schon Ideen für die Lösung, aber keine Idee konnte ich bis zum Ende erfolgreich durchdenken.
    Man könnte die Zahlen von 1-n in ein Stack oder in eine ArrayList (beides in Java vorzufinden) oder Sonstiges dergleichen in einer anderen Programmiersprache reinschreiben. Nun könnte man mit der 2. niedrigsten Zahl beginnen und darauf direkt die niedrigste Zahl folgen lassen, damit man schonmal ein Down bekommt. Hier würde ich dementsprechend die Zahl 2 dann die Zahl 1 benutzen und nach deren Benutzung diese aus der ArrayList löschen, sodass die 3 an Index 0 springt.Im nächsten Schritt will man ja wieder ein Up bekommen, somit braucht man als nächstes eine größere Zahl als die vorhergehende Zahl. Dafür würde ich dann die Zahl an Index 0 benutzen, was in unserem Fall die 3 wäre. Diese beiden Up und Down Schritte werden so lange wiederholt, bis keine Zahlen mehr in der ArrayList sind. Das gibt mir auch schonmal erfolgreich die erste richtige Zahl, die auch der Professor errechnet hat.


    Jetzt weiß ich jedoch nicht wie man weitermacht. Vermutlich irgendwie mit Rekursion etc. Aber ich bin in dem Gebiet Algorithmen noch viel zu unerfahren um da jetzt von alleine drauf zu kommen.


    Ich habe allerdings schon ein funktionierendes Java Programm geschrieben, dass mir erst alle Kombinationen errechnet und dann nur die ausgibt, die dem Filter entsprechen. Jedoch ist das nicht sehr effizient. Ich würde das ganze gerne schon mit Hilfe dynamischer Programmierung hinbekommen.


    Über jegliche Unterstützung bin ich sehr dankbar!


    Viele Grüße!

  • Hallo,


    eine Rekursion wäre hier sehr sinnvoll, das stimmt. Überlege dir zuerst am besten eine Rekursion welche dir alle Permutationen ausgibt, unabhängig von der Einschränkung.
    Dafür empfehle ich eine Methode der ein Array[n] und einen Integer, ich nennen ihn mal "swap", übergeben wird.



    Beim ersten Aufruf bekommt sie ein Array mit {1, 2, 3, 4, 5, 6, 7, ... , n} und swap 0.
    Die Methode hat nun eine for Schleife von Index i bis Array.length. Hier vertauscht du in jedem durchlauf Array[i] mit Array[swap] und rufst die Methode mit dem vertauschtem Array und swap + 1 neu auf.


    Da es eine rekursive Methode ist, sollest du sobald sie aufgerufen wird, zuerst überprüfen ob du nicht schon fertig bist, also falls dein swap == Array.length ist, kannst du das Ergebnis ausgeben.


    Dadurch ergeben sich n! Aufrufe mit allen Permutationen, wenn du jetzt welche ausschließen willst, musst du die rekursiven Aufrufe einschränken.
    Falls nach dem Vertauschen ein Array mit {1, 2 .... } oder {2, 1, 3, 5 ... } entsteht, ruft sich die Methode nicht nochmal selbst auf.
    Damit brichst du ab, sobald die DUDU Einschränkung das erste mal nicht eingehalten wird (effizient) und die Ausgabe für diesen Rekursions Zweig wird nie erreicht.


    Ich würde das in diese Fälle unterteilen
    1) swap = 0 ... hier kann man abbrechen falls Array[0] == 1
    2) swap = 1 ... hier kann man abbrechen falls Array[0] < Array[1]
    3) swap > 1 ... hier kann man mit Array[swap], Array[swap - 1] und Array[swap - 2] arbeiten und das DUDU der letzten 3 Zahlen überprüfen


    LG