# Permutation ohne Rekursion



## nadoria (16. Nov 2008)

Hallo an alle,

ich muss diese Aufgabe lösen, aber mir fällt leider kein (funktionierender) Algorithmus ein. Es sollen verschachtelte while-Schleifen genutzt werden.. (bin aber auch für andere Lösungsansätze dankbar..) (Keine Rekursion, keine Listen, nur Arrays bzw ein Array..)



Hier die Aufgabe:

Permutationen
Schreiben Sie eine Java-Klasse Permutation mit einer Methode permute, die ein int-Array der Länge n als Eingabe hat und alle Permutationen der Zahlen im Array ausgibt.
Als Permutationen einer Menge bezeichnet man Vertauschungen der einzelnen Elemente. Beispiel:
public class PermutationTest {
public static void main(String[] args) {
int[] k = {1,2,3};
Permutation.permute(k);
}
}
Die main-Methode soll alle Kombinationen von Vertauschungen der Zahlen 1,2 und 3 auf den Bildschirm ausgeben:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Testen Sie Ihr Programm mit den Werten {1,2,3} und {1,2,3,4}.
Hinweis: Für ein Array x enthät x.length die Länge des Arrays x.


----------



## SlaterB (17. Nov 2008)

denkbar wäre eine Variante mit nur einer while-Schleife und mehreren Zustands-Hilfsvariablen + -Arrays, die quasi die Rekursion nachbauen,

wenn du die Rekursion noch nicht kennst, dann solltest du die zuerst ausprobieren, auch wenn du sie später nicht verwenden darfst (was diese Unlogik zeigt), 
hilft beim Verständnis,

dann also eine große while(true)-Schleife,
ein Array (act) so groß wie k, in dem die aktuell verwendeten Elemente markiert werden,
eine int-Variable für den aktuellen Zustand

der Zustand ist anfangs 0 und wird pro Schleifendurchlauf um 1 erhöht,

im ersten Durchlauf also Zustand 1, das heißt dass es um das erste Element geht, 
das act-Array zeigt an, dass noch alle Zahlen zur Auswahl stehen,
also wird jetzt das erste Element aus k für Position 1 ausgewählt
und dies in act vermerkt,

nächste Runde, Zustand 2, 2 wird ausgewählt,
nächste Runde, Zustand 3, 3 wird ausgewählt,

nächste Runde, Zustand 4, das bedeutet hier das Ende der Auswahl, act enthält 1, 2, 3, eine erste gültige Kombination

Zustand wird nun nicht mehr erhöht, sondern auf 3 reduziert,

in der nächsten Runde haben wir nun erstmals einen der Auswahlzustände (1 bis 3),
bei dem act schon Werte enthält, Wert 3 wurde an Position 3 schon verwendet,
da es keine höheren Werte gibt ist hier schon Schluss, es geht zurück Zustand 2, 

(*)
in Zustand 2 (nächster Schleifendurchlauf) sagt act, dass zuletzt die 2 für diese Postition ausgewählt war,
nun ist ja noch die 3 möglich, aber nur, wenn nicht die 3 schon an Position 1 steht,
dafür haben wir auch das act-Array, das versichert uns, dass die 3 aktuell noch nicht gewählt wurde (Zustand 3 wurde inzwischen ganz gelöscht),
also wird nun Wert 3 an Position 2 geschrieben, act aktualisiert,
es geht weiter zu Zustand 3, dort wird die noch freie 2 ausgewählt,
Zustand 4, wieder 3 und wieder zu 2 zurück,

nun ist man wieder fast in der Situation (*) einen Absatz zuvor,
der Unterschied ist nur, dass das act-Array nun die Information enthält, dass für Position 2 schon der maximale Wert 3 verwendet wurde,
deshalb wird hier die Bearbeitung für Zustand 2 nicht fortgesetzt, es geht zurück zu 1,

usw.

wichtig ist noch, dass beim Zurücksetzen des Zustandes die act-Tabellen für die höheren Zustände ganz zurückgesetzt wird,

ich habe extra teilweise nur angedeutet, wie welche Informationen zu erhalten und abzufragen sind,
frage mich nicht nach noch mehr Details, das sollst schließlich du programmieren 
schon viel zu viel verraten

allerdings ist das auch ein sehr komplexes Verfahren, eigentlich zu schwer für so eine einfach klingende Aufgabe,

vielleicht gibts noch mehr Ideen

----------

eine noch von mir, diesmal nur ganz grob:

man fängt mit dem höchsten Element an, der 3 und bildet alle möglichen Kombinationen, also nur die eine mit 3 

dann nimmt man die 2 dazu, 
setzt die 2 vorne fest und verbindet sie mit allen bisherigen Kombinationen
-> 2 3

und dann nimmt man alle diese neuen Kombinationen und dreht sie durch
dadurch wird aus 2 3 auch zusätzlich 3 2,
'durchdrehen' heißt, das erste Element des Array wegzunehmen und hinten anzuhängen
das ist jetzt noch nicht deutlich, wird aber bald deutlicher,

jedenfalls erhält man 2 3 und 3 2


als nächstes kommt die 1, 1 vorne fest und mit allen bisherigen Kombos kombinieren
->
1 2 3
1 3 2

nun noch durchdrehen, aus 1 2 3 wird noch 2 3 1 und 3 1 2
aus 1 3 2 wird noch 3 2 1 sowie 2 1 3

macht insgesamt die 6 Kombinationen


----------



## Leroy42 (17. Nov 2008)

@SlaterB

Wie lange hast du denn für diesen Post gebraucht?  :shock: 

(  )


----------



## SlaterB (17. Nov 2008)

psst, Arbeitszeit

(edit: nein, da fehlt kein a)


----------



## nadoria (17. Nov 2008)

SlaterB hat gesagt.:
			
		

> denkbar wäre eine Variante mit nur einer while-Schleife und mehreren Zustands-Hilfsvariablen + -Arrays, die quasi die Rekursion nachbauen,
> 
> wenn du die Rekursion noch nicht kennst, dann solltest du die zuerst ausprobieren, auch wenn du sie später nicht verwenden darfst (was diese Unlogik zeigt),
> hilft beim Verständnis,
> ...





Hallo SlaterB!

Vielen Dank für deine Antwort! (Hatte schon die Hoffnung aufgegeben, dass jemand ne Idee hat..)

Jetzt muss ich nur noch meine bescheidenen Java-Kenntnisse abrufen, um einen deiner Algorithmen zu realisieren 

Gruß,

n.


----------

