Permutation

[Guest]

Hi, ich möchte folgende Aufgabe lösen, aber komme irgendwie auf keinen gescheiten Ansatz.

Gegeben ist eine permutierte Folge der natürlichen Zahlen von 1 bis n in einem Feld der Größe n. Diese Zahlen sollen nach folgendem Algorithmus getauscht werden:

* Die Zahl k auf Position 1 wandert an ihre richtige Position im Feld (also die Position k).
* Um dort Platz zu machen, rutschen alle anderen Zahlen auf den Positionen 2 bis k eine Stelle nach links.
* Das Verfahren bricht ab, wenn sich durch diesen Algorithmus die Reihenfolge der Zahlen nicht mehr ändert.

Beispiel:

4 5 3 1 2 // 4 wandert auf Position 4, (5, 3, 1) wandern nach links
5 3 1 4 2 // 5 wandert auf Position 5, (3, 1, 4, 2) wandern nach links
3 1 4 2 5 // 3 wandert auf Position 3, (1, 4) wandern nach links
1 4 3 2 5 // 1 wandert auf Position 1, keine Änderung, Ende

Schreiben Sie ein Java-Programm mit folgenden Methoden:

* Erzeugen einer zufälligen Permutation der Zahlen von 1 bis n in einem Feld
* Implementierung des obigen Algorithmus.


Wäre nett, wenn mir jemand auf die Sprünge hilft.

 

[Landei]

Wenn du die Permutation hast (und dafür gibt es TONNEN von Beispielcode im Internet), geht es so weiter:

int[] einArray = dasArrayAusMeinerPermutationsFunktion();

nullte Zahl (die wandern soll) merken:

int wanderZahl = einArray[0];

von Position 0 bis Position (Wanderzahl minus 2) die Zahl von der nächsten Position holen:

for(int i = 0; i < wanderZahl - 1; i++) {
  einArray[i] = //überleg mal ein wenig was hier hin kommt
}

wanderZahl an der richtigen Stelle setzen:

einArray[wanderZahl - 1] = wanderZahl;