# Permutation



## Guest (8. Dez 2008)

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 (9. Dez 2008)

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;
```


----------

