Permutation +java < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:27 So 15.03.2009 | | Autor: | inuma |
Hallo,
ich versuche jetzt seit ein paar tagen eine einfach Permutaion von n gliedern hin zu kriegen, aber ich schaffe es einfach nicht.
Ich muss es mit Java lösen.
Meine gednake war mit for-schleifen zu arbeiten, aber ich habe das problem, dass ich bei n = 4 vier forschleifen brauche und bei n=5 dann wiederrum 5.
Mein plan war es eigentlich, dass ich forschleifen nehme und alle möglichen Kombinationen ausgeben lasse.
n =4
1111
1112
1113
1114
....
4444
und ihm dann schauen lassen, dass keine der zahlen doppelt ist.
if (n1 != n2 != n3 != n4)
{
ausgabe der Zahl
}
Aber ich komme auf keine wirklich gute Lösung, da ich am Ende immer mehr forschleifen brauche oder aber ein Array mit Variablen (also array n1, array n2, array n3...)
Alos wenn mir irgendwer helfen kann, wäre ich dem sehr dankbar
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:52 So 15.03.2009 | | Autor: | rainerS |
Hallo!
> Hallo,
>
> ich versuche jetzt seit ein paar tagen eine einfach
> Permutaion von n gliedern hin zu kriegen, aber ich schaffe
> es einfach nicht.
>
> Ich muss es mit Java lösen.
>
> Meine gednake war mit for-schleifen zu arbeiten, aber ich
> habe das problem, dass ich bei n = 4 vier forschleifen
> brauche und bei n=5 dann wiederrum 5.
>
> Mein plan war es eigentlich, dass ich forschleifen nehme
> und alle möglichen Kombinationen ausgeben lasse.
>
> n =4
>
> 1111
> 1112
> 1113
> 1114
> ....
> 4444
>
> und ihm dann schauen lassen, dass keine der zahlen doppelt
> ist.
>
> if (n1 != n2 != n3 != n4)
> {
> ausgabe der Zahl
> }
>
> Aber ich komme auf keine wirklich gute Lösung, da ich am
> Ende immer mehr forschleifen brauche oder aber ein Array
> mit Variablen (also array n1, array n2, array n3...)
Ich glaube, es ist einfacher, das Problem rekursiv anzugehen. Zum Beispiel bekommst du alle Permutationen von [mm] $\{1,2,3,4\}$, [/mm] indem du folgende 4 Fälle abarbeitest:
1 gefolgt von allen Permutationen von [mm] $\{2,3,4\}$
[/mm]
2 gefolgt von allen Permutationen von [mm] $\{1,3,4\}$
[/mm]
3 gefolgt von allen Permutationen von [mm] $\{1,2,4\}$
[/mm]
4 gefolgt von allen Permutationen von [mm] $\{1,2,3\}$
[/mm]
Dann hast du eine for-Schleife, musst dafür jedesmal alle Permutationen dreier Zahlen bestimmen. Das kannst du wiederum tun, indem du dir eine der Zahlen herausgreifst und alle Permutationen der verbleibenden 2 Zahlen bestimmst.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:58 So 15.03.2009 | | Autor: | inuma |
Hallo,
ich hätte jetzt folgenden Ansatz:
Ich würde ein Array erstellen mit allen Möglichen Zahlen erstellen. Und ein Methode "Perm", die die Permutation machen soll.
Alles ist rekusiv aufgebaut. Hoffe ich.
In der Methode perm zieht er sich eine Zahl aus dem Array raus und müsste dann überprüfen wie viele Zahlen noch drin sind, wenn es mehr als 2 sind, dann muss er eine nächste zahl rausziehen. das tut er solange bis es nur noch 2 Zahlen zum permutieren gibt. Er nimmt einmal alle Zahlen in einer Reihe
1234 (Array hat noch {34})
und dann vertauscht er die letzen beiden
1243 (Array hat noch {34})
dann geht er wieder in den schritt zuvor und fügt die 2 dem Array hinzu {234} und wähle die nächste Arrayzahl (hier 3) als 2 Glied der Permutation.
1324
Auch jetzt wird wiedervertauscht
das geht so weiter bis wieder 4 Zahlen im Array sind
{1234} und auch hier wird nun die nächste Zahl als erste Zahl benutzt
als 2 usw.
Wie bringe ich das aber nun in einem Quellcode unter?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:12 So 15.03.2009 | | Autor: | rainerS |
Hallo!
> Hallo,
>
> ich hätte jetzt folgenden Ansatz:
>
> Ich würde ein Array erstellen mit allen Möglichen Zahlen
> erstellen. Und ein Methode "Perm", die die Permutation
> machen soll.
>
> Alles ist rekusiv aufgebaut. Hoffe ich.
>
> In der Methode perm zieht er sich eine Zahl aus dem Array
> raus und müsste dann überprüfen wie viele Zahlen noch drin
> sind, wenn es mehr als 2 sind, dann muss er eine nächste
> zahl rausziehen. das tut er solange bis es nur noch 2
> Zahlen zum permutieren gibt. Er nimmt einmal alle Zahlen in
> einer Reihe
>
> 1234 (Array hat noch {34})
>
> und dann vertauscht er die letzen beiden
>
> 1243 (Array hat noch {34})
>
> dann geht er wieder in den schritt zuvor und fügt die 2 dem
> Array hinzu {234} und wähle die nächste Arrayzahl (hier 3)
> als 2 Glied der Permutation.
>
> 1324
>
> Auch jetzt wird wiedervertauscht
> das geht so weiter bis wieder 4 Zahlen im Array sind
>
> {1234} und auch hier wird nun die nächste Zahl als erste
> Zahl benutzt
>
> als 2 usw.
>
> Wie bringe ich das aber nun in einem Quellcode unter?
Ich glaube, du hast das Prinzip der Rekursion noch nicht verstanden. Du brauchst eine Methode perm, die sich selbst rekursiv aufruft und die Liste aller Permutationen zurückgibt. Etwa so:
| 1: | int[][] perm(int[] zahlen) {
| | 2: |
| | 3: | if (zahlen.length == 1) {
| | 4: | // weniger als zwei Zahlen
| | 5: | int[][] resultat = new int[1][];
| | 6: | resultat[0] = zahlen;
| | 7: | return resultat;
| | 8: | } else {
| | 9: | // mehr als 1 Zahl
| | 10: | for (int i=0; i < zahlen.length; i++) {
| | 11: | int erstezahl = zahlen[i];
| | 12: | //entferne diese Zahl aus dem arrayzahlen
| | 13: | // das ergebnis sei das array zahlen1
| | 14: | // Wenn zahlen die elemente [1,2,3,4] enthält
| | 15: | // so ist beim ersten Durchlauf der for-Schleife erstezahl=1
| | 16: | // und zahlen1=[2,3,4]
| | 17: | // beim zweiten Durchlauf: erstezahl=2 und zahlen1=[1,3,4]
| | 18: | // usw.
| | 19: | // berechne alle permutationen von zahlen1
| | 20: | int[][] resultat_rekursiv = perm(zahlen1);
| | 21: | // setze das ergebnis zusammen
| | 22: | //,,
| | 23: | }
| | 24: | // fasse alle teilergebnisse zusammen und gib das ergebnis zurück.
| | 25: | }
| | 26: | }
|
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:31 So 15.03.2009 | | Autor: | inuma |
Hallo Rainer,
als aller erstes Vielen Dank bis hierhin
ich denke, dass ich langsam anfange es besser zu begreifen.
ok hier noch mal so Fragen
1: int[][] perm(int[] zahlen) { Warum steht da int[][], ist das ein Doppeltes Array, also aus 2 Gliedern?
2:
3: if (zahlen.length == 1) {
4: // weniger als zwei Zahlen
5: int[][] resultat = new int[1][]; Warum ist eines der Arrays immer 1
6: resultat[0] = zahlen;
7: return resultat; Er gibt also am ende ein Zahl zurück...
8: } else {
9: // mehr als 1 Zahl
10: for (int i=0; i < zahlen.length; i++) {
11: int erstezahl = zahlen[i];
12: //entferne diese Zahl aus dem arrayzahlen Ähh, könntest du mir sagen wie am Zahlen aus einem Array entfernt
13: // das ergebnis sei das array zahlen1 Erschaft man hier neue Arrays?
14: // Wenn zahlen die elemente [1,2,3,4] enthält
15: // so ist beim ersten Durchlauf der for-Schleife erstezahl=1
16: // und zahlen1=[2,3,4]
17: // beim zweiten Durchlauf: erstezahl=2 und zahlen1=[1,3,4]
18: // usw.
19: // berechne alle permutationen von zahlen1 Das bezieht sich auf die Zeile 20, oder nicht?
20: int[][] resultat_rekursiv = perm(zahlen1);
21: // setze das ergebnis zusammen
22: //,,
23: }
24: // fasse alle teilergebnisse zusammen und gib das ergebnis zurück. Noch eins wo werden die Teilergebnisse gespeichert?
25: }
26: }
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:25 Mo 16.03.2009 | | Autor: | rainerS |
Hallo!
> ok hier noch mal so Fragen
>
> Warum steht da int[][],
> ist das ein Doppeltes Array, also aus 2 Gliedern?
Das ist ein Array, dessen Elemente Arrays sind. Die Methode gibt die Liste der Permutationen zurück, jede Permutation ist als Array dargestellt.
> Warum ist eines der
> Arrays immer 1
Nur eine Zahl --> nur eine Permutation
> Er gibt also am
> ende ein Zahl zurück...
Nein, ein Array, dessen Elemente Permutationen sind. Da es sich hier um den einfachsten Fall handelt, hat es nur ein Element, nämlich ein Array mit einem Element.
> könntest du mir sagen wie am Zahlen aus einem Array
> entfernt
Die einfachste Möglichkeit ist, ein neues Array anzulegen und umzukopieren. Alternativ kannst du auch Java Collections benutzen, aber davon würde ich abraten, solange du damit keine weitere Erfahrung hast.
> bezieht sich auf die Zeile 20, oder nicht?
Ja.
> Noch eins wo werden die Teilergebnisse
> gespeichert?
Die musst du in geeigneten Variablen zwischenspeichern. Du könntest dazu statt eines Arrays auch ein Variable vom Typ Arraylist verwenden und am Schluss mit der toArray-Methode in ein Array umwandeln. Arraylist hat den Vorteil, dass du die Anzahl der Elemente bei Bedarf vergrößern kannst, ohne diese umzukopieren.
Viele Grüße
Rainer
|
|
|
|
