www.mikrocontroller.net

Forum: Compiler & IDEs Wie am effizientesten Zufallszahlen ohne Doubletten?


Autor: Markus M. (adrock)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Markus M. (adrock)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: horst (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.