Übung 10_1

[MartinX3]

Aufgabe 1 [Programmierung – nicht einzureichen]

Schreiben Sie eine Klasse Felder mit einer Klassenmethode permutationen, die ein int-Array a als Argument annimmt. Die Methode soll rekursiv alle möglichen Permutationen (Vertauschungen der Elemente) von a produzieren.

Geben Sie jede Permutation mittels Arrays.toString auf einer Zeile auf dem Bildschirm aus.

Hinweise:

• Sie benötigen eine rekursive Hilfsmethode und eine öffentliche Einstiegsmethode.

• Rekursives Vorgehen zur Erzeugung aller Permutationen:

  • Übergeben Sie an die Hilfsmethode außer dem Array auch ein Argument pos, das angibt,
    bis zu welcher Position des Arrays Sie die Elemente vertauschen wollen. Zu Beginn ist dies
    die letzte Position des Arrays.

  • Gehen Sie der Reihe nach von pos bis zur ersten Position rückwärts über das Array und
    führen Sie jeweils die folgenden Schritte aus:

    • Tauschen Sie das Element an der aktuellen Position mit dem an Position pos.

    • Erzeugen Sie nun rekursiv alle Permutationen der Elemente bis zur Position vor pos.

    • Tauschen Sie nachher das Element an der Position pos zurück an die ursprüngliche Stelle.

  • Wenn es nichts zu vertauschen gibt (wann ist das der Fall?), ist der aktuelle Zustand des Arrays eine neue Permutation.

• Verwenden Sie eine Hilfsmethode void swap(int[] a, int i, int j), die die Elemente an
  den gegebenen Positionen von a vertauscht.

optionale Erweiterung: Geben Sie die Permutationen nicht auf dem Bildschirm aus, sondern in
einem Array (von Arrays, die die Permutationen darstellen) als Ergebnis zurück.

Hinweise dazu:

• Für eine Folge von n Elementen gibt es n! unterschiedliche Permutationen. Verwenden Sie eine
  der vielen Implementierungen der Fakultätsfunktion, um das Ergebnisfeld entsprechend groß
  anzulegen.

• In der Einstiegsmethode ist das Ergebnisfeld einmalig anzulegen und zusammen mit der nächsten
  darin zu belegenden Position ebenfalls an die rekursive Hilfsmethode zu übergeben.

• Bei den rekursiven Aufrufen müssen Sie bedenken, dass pro Aufruf pos! Permutationen generiert
  wurden, Sie also entsprechend im Ergebnisfeld weiterrücken müssen.

• Legen Sie, wenn sie eine neue Permutation gefunden haben, eine Kopie(!) des Arrays im Ergebnisfeld ab.

optionale Erweiterung: Falls ein Element mehrfach in dem Array vorkommt, entstehen identische
Permutationen, wenn lediglich diese gleichwertigen Elemente untereinander ausgetauscht werden. Passen Sie die Lösung an, so dass solche Doppelungen vermieden werden.

Hinweis dazu: Bevor Sie ein Element aus dem Array an die derzeit letzte Position tauschen, prüfen
Sie, ob dasselbe Element nicht schon weiter vorn im Array steht, also bereits berücksichtigt worden
ist. Falls doch, ignorieren Sie dieses Vorkommen des Elements und fahren mit dem nächsten fort.