Wie am effizientesten Zufallszahlen ohne Doubletten?

[Markus M. (adrock)]

Hallo,

für eine kleine Spielerei schreibe ich in zwei Arrays x und 
y-Koordinaten (Bereich 0..11) die durch rand()%12 erzeugt werden.

Die max. Anzahl der Einträge im Array ist fest definiert.

Ich möchte nun verhindern, dass zwei Einträge mit den gleichen 
Koordinaten existieren. Natürlich kann ich beim ermitteln von neuen 
Koordinaten immer das ganze Feld durchsuchen, ob es diese schon gibt und 
ggf. neue Zufallszahlen generieren.

Das ist allerdings nicht gerade effizient (Suchschleife...).

Gibt es da einen intelligenteren Ansatz?

Ciao...
Markus

[Simon K. (simon)]

Du füllst ein Array mit Zahlen von 0 bis n-1 (Wobei n die Anzahl der 
Array Einträge ist).
Dann erzeugst du mit dem Zufallsgenerator auch Zahlenpaare von 0 bis n-1 
und vertauschst immer die jeweiligen Elemente im Array miteinander.

Auch als Shuffling bekannt.
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[Markus M. (adrock)]

Hi,

ja das ist eine Idee, würde in meinem Fall für ein 12x12 
Koordinatensystem dann ein Feld mit 144 Einträgen bedeuten, oder?

Ciao...
Markus

[(prx) A. K. (prx)]

Markus M. schrieb:

> Ich möchte nun verhindern, dass zwei Einträge mit den gleichen
> Koordinaten existieren.

Was dem Zufall schonmal etwas die Zähne zieht und die entstehende 
Sequenz als begrenzt zufällig erkennbar macht.

[Mark B. (markbrandis)]

A. K. schrieb:
> Was dem Zufall schonmal etwas die Zähne zieht und die entstehende
> Sequenz als begrenzt zufällig erkennbar macht.

Nicht wenn man für die Aufgabenstellung eine Menge von Punkten benötigt, 
von denen keine zwei identisch sind. Was ja durchaus eine sinnvolle 
Forderung sein kann. Zufällig ist dann einfach die Verteilung der Punkte 
in der Ebene.

[horst (Gast)]

> Was dem Zufall schonmal etwas die Zähne zieht und die entstehende
> Sequenz als begrenzt zufällig erkennbar macht.

Berühmtes Beispiel aus der Schule:
Ziehung von Zahlen aus dem Hut mit und ohne Zurücklegen.