Überprüfen auf Permutation

[Sweetsister]

Hallo 🙂

ich habe ein kleines Problem. Ich sitze vor einer Ü-Aufgabe, bei der ich u.a. bei einem gegebenen Array prüfen soll, ob das eine Permutation ist.

Nun dachte ich daran, dass eine Permutation dann eine Permutation ist, wenn es keine Elemente doppelt gibt.

Also würde ich das gegebene Array darauf überprüfen wollen, aber sehe eine umständliche Lösung vor mir.

Mir würde das so vorschweben:

Nimm das Array, speichere das erste Element in einer Hilfsvariablen und schau, ob in dem restlichen Array ein Element gleich ist. Wenn nein, dann speichere das zweite Element auf der Hilfsvariablen und mache das wieder mit dem Array.
Aber das ist nicht wirklich sinnig, oder? Allein die Laufzeit, das wird für ein größeres Array ja riesig.

Wie kann man das denn eleganter lösen?

Grübelnde Grüße
Sandra

 

[Marco13]

Das Kriterium stimmt so IMHO nicht. Der Array [1,1,1] ist eine Permutation vom Array [1,1,1]. Genaugenommen gibt es da etliche Permutationen, die zwar alle gleich sind, aber eben doch nur Permutationen. Umgangssprachlich könnte man sagen: Es ist eine Permutation, wenn es die gleichen Elemente enthält (in der gleichen oder einer anderen Reihenfolge).

 

[kay73]

Wenn sich die Array Elemente sortieren lassen: Array sortieren und für jedes Element prüfen, ob das nächste gleich dem aktuellen ist. Laufzeit O(n log n) fürs Sortieren und O(n) für das Vergleichen.

Im allgemeinen Fall kannst Du auch ein HashSet mitschleppen, jedes getroffene Element auf Existenz im Hash prüfen bzw speichern. So kannst Du auf Kosten des Platzes die Suche beschleunigen.

 

[Marco13]

... und... was würde man damit genau überprüfen? ???:L Doch nur ob alle Elemente gleich sind...? (Dann braucht man auch nicht zu sortieren 😀 )

 

[kay73]

... und... was würde man damit genau überprüfen? ???:L Doch nur ob alle Elemente gleich sind...? (Dann braucht man auch nicht zu sortieren 😀 )

Der Sinn der Sache ist natürlich, beim ersten Duplikat

false

zurück zu geben. Alles vorausgesetzt, die merkwürdige "Definition" von Permutation stimmt...