Java Array auf Permutation prüfen

[XHotSniperX]

Huhu

ich prüfe ein Array von der Länge n auf Permutation. Der folgende Code hat im schlechtesten Fall eine Komplexität O(n^2) und das ist mühsam.

private static boolean testPermutation(int[] values){
         
        for (int i = 0; i < values.length; i++){
            if (values[i] >= values.length){
                return false;
            }
            for (int j = 0; j < values.length; j++){
                if (values[j] == values[i] && i != j){
                    return false;
                }
            }
        }
        return true;
        
    }

Ich möchte diesen Algorithmus auf O(n) verbessern. Geht das überhaupt?

 

[chief8]

Hier stand Mist...

 

[Troublegum]

Du könntest die Elemente deines Arrays nach und nach in ein TreeSet<Integer> einfügen.
Dann enthält dein TreeSet laut Definition keine Duplikate mehr und wäre schon geordnet. Dann müsstest du nur noch die Länge des TreeSets und das größte Element überprüfen, und du bist fertig.

Das alles würde im Worst-Case O(n*log(n)) Zeit kosten.

 

[Mathematiker]

Was du da machst ist schon ein bisschen unnötig aufwändig. Gehe doch einfach einmal durch alle Elemente und schau immer, ob das nächste größer als das jetzige ist. Wenn dem nicht so ist brichst du ab und wärst fertig.
Das hätte ne Laufzeit im worst case von O(n).

 

[wahli]

Hier wäre mein Ansatz:

Berechne die Fakultät von values.length. Diese muss übereinstimmen mit der Multiplikation der einzelnen Werte.

Die Komplexität wäre dann 2O(n)

Alle Angaben ohne Gewähr!!!

 

[Killkrog]

O(n) ist nicht möglich, außer das Array hat vor dem Test eine bestimmte Struktur, mit Hilfe derer man einen abgestimmten Testalgorithmus schreiben könnte. Woher stammt das Array? Wie ist es aufgebaut? Kannst du seine Erzeugung beeinflussen? Ggf können mit diesen Angaben schnellere Algorithmen entwickelt werden als der, den du oben angegeben hast.

@ Mathe
Setzt ein vorsortiertes Array voraus...

@ Wahli
[0, 1, 2]
Länge = 3, !3 = 1*2*3 = 6
Multiplikation aller Elemente 0*1*2 = 0
0 != 6
Falsch!

 

[Taelis]

Wenn '0' erlaubt ist (bzw. die Permutation als 0..n-1 definiert ist), muss man halt beim Multiplizieren vorher eins draufaddieren und schon funktioniert der Weg über n! wieder...

 

[LeMumpelPumpel]

Ich bin mir ja nicht sicher aber kann man nicht eigentlich nur prüfen ob ein Array eine Permutation eines anderen Arrays ist?

--Mist--
Außerdem gibt die Methode ja nur true zurück wenn das Array die Form {0,1,2,3,4,...,n} hat. Das lässt sich wie gesagt ja deutlich einfacher prüfen (in O(n)).
--Mist--

Trotzdem bleibt die Frage von was das übergebene Array eigentlich eine Permutation sein soll.

 

[Killkrog]

Jungs, es ist ja noch nicht mal bekannt, ob negative Werte vorkommen...

 

[XHotSniperX]

nein negative Werte kommen nicht vor! und ja es ist so, dass es bei 0 anfängt

@Mathematiker:

das Array ist nicht sortiert also geht das nicht

@Killkrog:

ich wähle nur die Länge des Arrays. Das Array ist random gemischt... ich glaube, es geht nur O= log(n)*n

 

[Killkrog]

Trotzdem bleibt die Frage von was das übergebene Array eigentlich eine Permutation sein soll.

Genau das!

 

[XHotSniperX]

von was? von nichts hehe.. wird einfach per Zufall erstellt von 0 bis länge-1

 

[R3ddy]

@Wahli
Das Funktioniert leider nicht.
Bsp: 4!=24=2*2*2*3 aber (2,2,2,3) keine Permutation.


Meine Idee:
Erzeuge dir ein zweites Array gleicher Länge vom Type boolean.
Gehe dein zu prüfendes Array durch und setze den entsprechenden Wert im anderen Array auf true.
Prüfe ob alle Werte im "boolean-Array" true sind.

Wenn ich keinen Denkfehler drin habe sollte das in O(n) gehen.

 

[Kiviuq]

Beschreib am besten mal was du prüfen willst. Eine Permutation ist nur eine Abbildung. [1,2,3] ist z.B. auch eine Permutation von [1,2,3], spricht die Identität ist auch eine Permutation.

 

[Quickbeam2k1]

Also zum prüfen ob es eine Permutation eines anderen Arrays ist: Wie wärs denn mit dein Array und das Vergleichsarray sortieren. Dann komponentenweiser vergleich womit du dann doch bei O(n log n) landen solltest.

@ sniper: Beantworte mal bitte was du genau machen willst: Deine Schleife oben prüft ja nu ob ein Eintrag des Arrays größer als die Array länge ist und nur voneinander verschiedene Einträge hat. Siehe auch den Beitrag von Mumpel

 

[LeMumpelPumpel]

Erzeuge dir ein zweites Array gleicher Länge vom Type boolean.
Gehe dein zu prüfendes Array durch und setze den entsprechenden Wert im anderen Array auf true.
Prüfe ob alle Werte im "boolean-Array" true sind.

Wenn ich keinen Denkfehler drin habe sollte das in O(n) gehen.

So eine Idee hatte ich auch. Wenn wir an das Gleiche gedacht haben funktioniert das aber nur wenn kein Wert im Array mehrmals vorkommt. Dann aber wirklich in O(n).

 

[R3ddy]

Also ich habe den TE so verstanden, das ein Array der Länge n mit beliegen Zahlen gegeben ist. Es soll nun geprüft werden, ob die im Array enthaltenen Zahlen eine Permutation der Zahlen von 0 bis n-1 sind. Also ob alle Zahlen von 0 bis n-1 einmal vorkommen.

@LeMumpelPumpel
Wenn ein Wert mehrmals vorkommt bedeutet dies aber, dass ein anderer Wert nicht vorkommt.

 

[XHotSniperX]

ahh ja das mit boolean array sollte klappen oder? auch wenn man duplikate hat. man muss halt alles vorher auf false setzen.. ist das nicht perfekt?

 

[LeMumpelPumpel]

Du willst doch dann aber durch die Werte im Array auf das Boolean Array zugreifen. Bei doppelten Einträgen würdest du es aber mehrmals auf true setzen. Du könntest dir ob jedes Element in Permutations-Array vorkommt.

Demnach wären das hier Permutationen [1,1,2,3,4] => [1,2,3,4]

 

[djdolla]

Ist das ein Projekt für die Schule? Wenn nein verwende doch ein Hashset, das is jedenfalls schneller als das xfache druchgehn deiner arrays.

for(int i = 0;i<array.length;i++)
{
	if(!hashset.contains(array[i]) && array[i]<=array.lengt)
		hashset.add(array[i];
	else
		return false;
}
return true;

Falls du kein Hashset verwenden darfst solltest du zumindest mit j=i+1 nehmen können.