Java Array auf Permutation prüfen

[LeMumpelPumpel]

@djdolla
Was passiert mit doppelten Elementen im Array? Hat ein Array ein doppeltes Element wird bei dir immer False ausgegeben.

 

[R3ddy]

@LeMumpelPumpel
Nein, da das "boolean-Array" genauso lang ist wie das zu prüfende Array wäre der letzte Eintrag false.

@TE
Wenn ich mich nicht täusche werden die Einträge eines Arrays vom Type boolean als false initialisiert. Du musst also nicht erst alles auf false setzen.

 

[LeMumpelPumpel]

@R3ddy
Also würde bei einem doppeltem Arrayeintrag automatisch false ausgegeben auch wenn es sich um eine Permutation handelt. Oder irre ich mich?

 

[djdolla]

Klar wird bei einem doppelten Element false ausgegeben - kann ja dann keine Permutation mehr sein.
Permutationen von {1,2,3}, selbst(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1)

 

[LeMumpelPumpel]

@djdolla
Naja aber (2,2,3) ist eine Permutation von (3,2,2)

 

[R3ddy]

@LeMumpelPumpel
Wenn ein Eintrag doppelt vorkommt kann es sich nicht um eine Permutation der Zahlen von 0 bis n-1 handeln, oder? - zu Spät

Ich denke der TE versteht dies nicht als Permutation, aber das wirst du wohl verstanden haben (Smiley).

 

[LeMumpelPumpel]

War das jetzt klar, dass wirklich jede Zahl nur einmal vorkommt? Wenn das so ist, dann ist das mit dem Boolean-Array die beste Möglichkeit, die mir einfällt. Wenn Zahlen doppelt vorkommen können klappt das dann halt nicht mehr.

 

[XHotSniperX]

also das mit hashset ist natürlich auch eine variante und ich darf verwenden was ich will.. aber das mit array boolean geht doch auch. weil die länge ist identisch also geht das auch mit duplikaten. und man muss einfach vorher immer prüfen, ob der wert grösser ist als die länge-1.. wenn ja automatisch false.

so funktionierts:

    private static boolean testPermutation(int[] values){
    	
    	boolean result = false;
        
    	boolean[] barray = new boolean[values.length];
    	
    	for(int i=0; i<values.length; i++){
    		if(values[i]<values.length)
    			barray[values[i]] = true;
    	}
    	
    	for(int i=0; i<values.length; i++){
    		if(barray[i]==true)
    			result=true;
    		else
    			return false;
    	}
    	return result;
    }

 

[djdolla]

Wenn er nur ein Array hat (wie der Funktionskopf angibt) und auf doppelte Einträge überprüft (was seine Funktion ja macht) Vermute ich dass es um die Eindeutigkeit der Integer Variablen geht
Edit: zu langsam

 

[XHotSniperX]

ach das meintet ihr mit doppelten zahlen.... achsoo. es ist natürlich eine permutation von 0 bis length-1 und erst dann true, wenn alle zahlen einmalig sind und nicht grösser als length-1

 

[Taelis]

Warum zweimal durchgehen?

Sollte das nicht reichen?

private static boolean testPermutation(int[] values) {

	boolean[] barray = new boolean[values.length];

	for (int i = 0; i < values.length; i++) {
		if (barray[values[i]] == true) {
			return false;
		}
		barray[values[i]] = true;
	}
	return true;
}

Ich bin leicht angetrunken und übernehme keine Garantie

 

[XHotSniperX]

hast völlig recht habs auch gesehn hehe... also, wie gesagt, es geht um ein array mit gemischten zahlen (nur einmal vorkommend) wo dann eine zahl im nachhinein geändert wird (nicht negativ) und man dann prüfen muss, ob das eine permutation ist mit allen zahlen zwischen und inklusive 0 bis lenght-1...

so klappts super.. danke euch allen

 

[djdolla]

Bei der Idee von Taelis musst du noch auf die größe von values überprüfen sonst kriest ne schöne Index out of Range Exception.

 

[LeMumpelPumpel]

Jetzt wird doch aber noch weniger getestet. Da du so viele Vorgaben gemacht hast ist die Frage ob man das überhaupt noch testen muss. Der TE sagt ja, dass das Array immer zahlen von 0 bis n-1 enthällt und jede Zahl nur einmal vorkommt. Damit kommt sie auch genau einmal vor.

=> Jedes Array was du übergibst ist per Definition schon eine Permutation

 

[XHotSniperX]

=> Jedes Array was du übergibst ist per Definition schon eine Permutation

Ja genau so ist das. Ich erstelle ein Array, das bereits eine Permutation ist mit nur einmal vorkommenden Zahlen zwischen 0 bis Länge-1. Dann wird auf das Array zugegriffen und vielleicht auch gemischt. Dann muss ich einfach nochmal prüfen, ob es immer noch eine Permutation ist von eben diesen Zahlen von vorhin.

Bei der Idee von Taelis musst du noch auf die größe von values überprüfen sonst kriest ne schöne Index out of Range Exception.

Jep

Gruss Sniper

 

[Quickbeam2k1]

Also Mischen eines Arrays erhält die Permutationseigenschaft. Was können denn sonst noch für Zugriffe stattfinden?