Permutation Rekusiv

[Sduni]

Hi @ All...

Hab mal wieder nen Problem ???:L

import java.util.*;
import java.util.LinkedList;

public class Permutation{
	
	public List<String> liste = new LinkedList<String>();
	public int a;

	public void permute(int[] ar){
		if(ar.length==0) return;
		String str = "";
		for(int i = 0; i < ar.length; i++){
			str = str + ar[i];
		}
		liste.add(str);
		//System.out.println(liste.get(0));
		for(int i = 0; i < ar.length; i++){
			ar[i] = a;
			ar[i] = ar[ar.length-1];
			ar[ar.length-1] = a;
			String str2 = "";
			for(int n = 0; n < ar.length; n++){
				str2 = str2 + ar[i];
			}
			for(int j = 0; j < liste.size(); j++){
				if(liste.get(i).equals(str2)) return;
				else permute(ar);
			}
		}
	}
	
	public static void main(String[] args){
		int[] array = {1,2,3};
		Permutation perm = new Permutation();
		perm.permute(array);
		String out = "";
		for(int i = 0; i < perm.liste.size(); i++){
			out = out + " - " + perm.liste.get(i);
		}
		System.out.println(out);
	}
	
}

und dort bekomm ich den Laufzeitfehler

PS C:\Users\Sduni\Documents\TU-Berlin Naturwissenschaften In der Informationsgesellschaft\09-10 WS\Meine Projecte\Permutation> java Permutation
java.exe : Exception in thread "main" java.lang.StackOverflowError
Bei Zeile:1 Zeichen:5
+ java <<<< Permutation
+ CategoryInfo : NotSpecified: (Exception in th...ckOverflowError:String) [], RemoteException
+ FullyQualifiedErrorId : NativeCommandError

at java.util.LinkedList$Entry.<init>(Unknown Source)

at java.util.LinkedList.addBefore(Unknown Source)
at java.util.LinkedList.add(Unknown Source)
at Permutation.permute(Permutation.java:15)
at Permutation.permute(Permutation.java:27)
at Permutation.permute(Permutation.java:27)
at Permutation.permute(Permutation.java:27)
at Permutation.permute(Permutation.java:27)
at Permutation.permute(Permutation.java:27)
....

Warum dieses?

 

[Final_Striker]

ich denke mal die abbruchbedingung wird nicht ausgeführt.

ar[i] = a;
ar[i] = ar[ar.length-1];

was soll das eigentlich bringen?

 

[Tomate_Salat]

nein wird ausgeführt, jag den code mal durch den Debugger und da fallen mir besonders diese Zeilen auf:

for(int n = 0; n < ar.length; n++){
                str2 = str2 + ar[i];
            }
            for(int j = 0; j < liste.size(); j++){
                if(liste.get(i).equals(str2)) return;
                else permute(ar);
            }

ungetestet:
ich denke du solltest hier nicht immer [c]i[/c] benutzen:
[java=22]
for(int n = 0; n < ar.length; n++){
str2 = str2 + ar[n];
}
for(int j = 0; j < liste.size(); j++){
if(liste.get(j).equals(str2)) return;
else permute(ar);
}
[/code]

denke das Problem taucht hier auf:

for(int j = 0; j < liste.size(); j++){
                if(liste.get(i).equals(str2)) return;
                else permute(ar);
            }

da [c]i[/c] möglicherweise zu groß wird.

Mfg

Tomate_Salat

Edit: nein...das Problem ist anscheinend doch ein anderes: Dein Programm verabschieded sich anscheinend in eine Endlosschleife und iwann versagt dann deine Liste.

 

[Sduni]

permute(123)-> permute(321) -> zurück
permute(312) -> permute(213)-> zurück
permute(231) -> permute(132)->zurück
->zurück
->zurück
->zurück
fertig

Alle Permutationen vorhanden! die Abruchbedingung soll der Vergleich der Strings sein. Würde ja gerne die Arrays vergleichen, aber da gab es Probleme mit der List.

@Last
Mit dem i hast du allerdings auch Recht. Sollte j sein

 

[Tomate_Salat]

Aber dein Programm liefert bei mir was anderes zurück:
permute(123) -> permute(320)

btw: wenn du die schleifen nicht änderst wie ich es getan habe, bekommst du beim ersten durchlauf in str2 den wert [c]"333"[/c]. Änderst du sie ab, bekommst du in str2 [c]"320"[/c]

 

[Sduni]

omg

public void permute(int[] ar){
		if(ar.length==0) return;
		String str = "";
		for(int m = 0; m < ar.length; m++){
			str = str + ar[m];
		}
		liste.add(str);
		//System.out.println(liste.get(0));
		for(int i = 0; i < ar.length; i++){
			a = ar[i];
			ar[i] = ar[ar.length-1];
			ar[ar.length-1] = a;
			String str2 = "";
			for(int n = 0; n < ar.length; n++){
				str2 = str2 + ar[n];
			}
			for(int j = 0; j < liste.size(); j++){
				if(liste.get(j).equals(str2)) return;
				else continue;
			}
			permute(ar);
		}
	}
	
	public static void main(String[] args){
		int[] array = {1,2,3};
		Permutation perm = new Permutation();
		perm.permute(array);
		String out = "";
		for(int i = 0; i < perm.liste.size(); i++){
			out = out + " - " + perm.liste.get(i);
		}
		System.out.println(out);
	}

jetzt bekomm ich 4 permutationen. zwei zu wenig... ;(

sieht so aus, als ob er die erste for Schleife nicht bei alle durchläuft. Ich bins mal durchgegangen. Bei 231 hört er auf, müsste aber eg. permute(213) machen und diese hinzufügen, bei i=1.