(C++) Zufallszahlenalgorithmus gesucht

[*Markus]

Hallo,

mein Ziel ist es, ein Array zu umzusortieren, dass die Werte, die in meinem Beispiel gleich der Indexnummer sind, willkürlich angeordnet sind.
Ich könnte natürlich solange Zufallszahlen generieren lassen, abprüfen, ob die Zahl bereits vorkam, und diese noch nicht vorgekommene Zahl dann in ein neues Array schreiben, aber das erscheint mir ziemlich ineffizient zu sein. Außerdem könnte es theoretisch ja möglich sein, dass ich bis in alle Ewigkeit genau die letzten Zufallszahlen suche, und diese nie generiert werden, da die Wahrscheinlichkeit, diese Zahl zu finden, mit der steigenden Anzahl der bereits gesetzten Zahlen immer geringer wird. Je größer das Array ist, desto geringer ist auch die Chance, die noch nicht vorgekommenen Zahlen zu finden.
Die beste Idee wäre natürlich Zahlen aus einer Zahlenmenge zufällig auszuwählen, aber wie könnte ich das in C++ realisieren? Zufallszahlengeneratoren wie srand() decken ja nur einen Von-bis-Wert ab und können Zahlen in dieser Von-bis-Zahlenreihe nicht einfach auslassen.
Meine beste Idee wäre, die übrig gebliebenen, noch nicht vorgekommenen Werte bei jedem "Durchlauf" in ein Array zu schreiben, das genauso groß ist, wie die Menge der restlichen Zahlen ist, und eine Zufallssuche mit dem Wertebereich 0-ARRAYLÄNGE auf dieses Array loszulassen. Gibt es noch einen besseren Weg?

Markus

[Skeeve]

Da ich kein C++ Programmierer bin, beschreibe ich Dir nur mal, wie ich das mache.
1. Fülle ein Array mit allen erlaubten Zahlen.
   for (i= max+1; max--; ) {
       array[i]= i;
   }
2. suche Dir aus 0 - max eine zufallszahl und tausche diese mit
   der Zahl nin max-1
3. Wiederhole das mit 0 - (max-1) ...
   for (i= max+1; max--;) {
       j= rand(i);
       x= array[i];
       array[i]= array[j];
       array[j]= x;
   }
Danach sind die Zahlen ziemlich zufällig verteilt. Das Verfahren ist ungefähr so, als würdest Du aus einem sortierten Kartenstapel, nach und nach zufällig Karten ziehen und sie übereinander stapeln. Das ergebnis ist ein zufällig sortierter stapel.

Ich hoffe, das hilft Dir weiter.

[*Markus]

Hallo,

Ich hoffe, das hilft Dir weiter.

Ja, diese Möglichkeit scheint ressourcenschonend und wirkungsvoll zu sein, danke.

Markus

[wahsaga]

hi,

mein Ziel ist es, ein Array zu umzusortieren, dass die Werte, die in meinem Beispiel gleich der Indexnummer sind, willkürlich angeordnet sind.

http://www.fredosaurus.com/notes-cpp/misc/random-shuffle.html beschreibt ein Methode, die alle Arrayelemente einmal mit einem zufällig ausgewählten tauscht.
Die Qualität dieser shuffle-Funktion wäre ggf. noch zu untersuchen.

gruß,
wahsaga

[Daniel Thoma]

Hallo wahsaga,

Zufälliges Tauschen ist keine gute Idee. Damit erreicht man nicht, dass jede Kombination gleich wahrscheinlich ist.
Das Verfahren das Skeeve beschreibt ist hingegen auch nicht komplizierter und optimal.

Grüße

Daniel