Random ohne Dublette

[alzaimar]

Wenn man schon vom 'Ziehen' spricht, dann könnte man das doch auch genau so implementieren: Ich habe einen Topf mit N Zahlen (1..N) und ziehe jedesmal eine zufällige Zahl heraus. Klar, nach jedem Ziehen enthält der Topf eine Zahl weniger.

Delphi-Quellcode:

Function Zupfeln (Var Zahlen : TCardinalList) : Cardinal;
Var
  i : Cardinal;

Begin
  i := Random (Zahlen.Count);
  Result := Zahlen[i];
  Zahlen.Delete(i);
End;

Also, was das Umsetzen einer Vorgabe anbelangt, würde ich das für optimal und elegant halten. Aber ich will mich -um Gottes willen- nicht mit Euch anlegen, sondern nur eine Portion berliner Senf (a.k.a. Mostrich) dazugeben.

Ach ja, kommt mir nicht im schlechter Performance, bitte.

[negaH]

@Marabu,

tja, wieso meinst du das ich die Worte "trivial" und "brute force" als negative Worte benutzt habe. Das zeigt das du dich durch meine persönliche Meinung angegriffen fühlst, das musst du doch garnicht 1.) hatte ich es nie vor und deshalb wählte ich auch diese Worte, du interpretierst sie negativ 2.) ist meine Meinung eine persönliche, quasi Geschmacksfrage, was ich auch deutlich betonte.

Wahr ist:

1.) für 6 zu ziehende eindeutige Zahlen benötigt man 5 mal den Aufruf von Random(), du hast Recht damit.
2.) beim Mischen benötigt man minimal 6 Speicher für 6 Zahlen, und das pro Ziehung = 6 mal.
3.) die bedingten Wahrscheinlichkeiten sind unterschiedlich zwischen den Verfahren, das dürfte dem Fragesteller aber wurscht sein, solange sie funktioniert
4.) für jeden Unwissenden stellt die für ihn beste Lösung eine Lösung dar die er durch "Brute Force" herausfand dar. Die Triviale Lösung ist diejenige die bei einem gewissen Wissensstand die logisch am einfachsten zu erreichende Lösung ist. Nun, Mischfunktionen sind algorithmisch linear und einfach gestrickt -> Speicher für 6 Zahlen allozieren und initialisieren, mit welchem Inhalt ist dabei egal -> Speicher per Zufall mischen -> Speicher sequientiell auslesen, welche Richtung ist egal. Also nichts sonderlich elegantes, sondern eine sehr stabile, einfach nachvollziehbare und sehr flexible Lösung, trivial halt weil sie nur wenig Grundwissen benötigt.

Sogesehen habe ich deine Lösung niemals als schlecht bezeichnet, sondern einfach nur angezweifelt das sie auch elegant ist Wobei ich gleich dazu bemerkte das Eleganz eine Geschmacksfrage ist. Willst du dich wirklich über Geschmack streiten bzw. aufregen ?

Zitat:

Die Mischer-Methode ist deshalb nicht elegant weil sie aus meiner Sicht
1.) bei 6 Zahlen minimal 12 mal Random() aufruft.

Das bezog sich garnicht auf deine Lösung, sondern auf die ganz simplen Mischermethoden/Vorschläge wie "erzeuge 6 mal jeweils 2 zufällige Indizes und vertausche die Elemente an diesen Indizees" (nachzulesen in diesem Thread).

Gruß Hagen

PS: meine Wortwahl ist also schon sehr gezielt gewesen. Lies meine Beiträge nochmal durch unter der Sichtweise das ich "elegant" anzweifle und "trivial"/brute force" nicht als negativ besetzte Worte sondern als "Aufwandsanalyse im Wissen" betrachte, durch. Nur du hast sie eben als negativ interpretiert, Warum?
Und achte mal darauf ob ich "die" oder "deine" Mischermethode schrieb !

[alzaimar]

Zitat von negaH:

... trivial halt, weil sie nur wenig Grundwissen benötigt....

Wenn man trivial mit einfach gleichsetzt, dann...

Zitat von Erhard Blanck:

Schade, daß das Wort "einfach" so einen simplen Beigeschmack hat.

und

Zitat von Heimito von Doderer:

Ganze Sachen sind immer einfach wie die Wahrheit selbst. Nur die halben Sachen sind kompliziert.

Ich persönlich bevorzuge einfache Lösungen -speziell in der Informatik-, eine Maxime, die mir mein Vater nicht oft genug vorhält: "Keep it simple".

Nun hat das Triviale aber die Bedeutung, das es das Offensichtliche darstellt, das einem überall begegnet. Und dann ist es offensichtlich nicht trivial, bei der Frage nach 'Zufallszahlenreihen ohne Wiederholung' auf eine zufällige Permutation zu kommen: Dazu ist doch Einiges an Grundwissen nötig. Es handelt sich jedoch um die einfachste Lösung, die dann eben auch die Eleganteste ist.

Verfolgt doch diese und ähnliche Threads in diesem und anderen Programmierforen zu dem Thema: Die richtige Anwort (Permutation) wird durch die Bank von erfahrenen, also mit Grundwissen ausgestatteten Leuten gepostet. Die triviale (also offensichtliche) Lösung ist nämliche die, einfach so lange zu würfeln, bis eine Zahl kommt, die vorher noch nicht kam.

Schönes Wochenende und Gruße aus Berlin.

[negaH]

Siehst du und da unterscheidet sich mein Meinung was elegant ist erheblich von deiner.

Ausgehend von der Forderung das wir eine Urne von 6 Zahlen haben, 1 bis 6 und daraus per Zufall nun alle 6 Zahlen ziehen ergeben sich reale Erfordernisse.

1.) es ist eine zufällige Permutation
2.) es ergeben sich exakte Wahrscheinlichkeiten für jede gezogene Zahl

Elegant ist es nun exakt diese Rahmenbedingungen einzuhalten und eventuell ohne die vorherige Erzeugung der Urne auskommen zu können.
Trivial ist es diese Urne zu allozieren und daraus die 6 Zahlen per Zufall zu ziehen.
An der Realität vorbei ist es

a.) solange per Zufall eine Zahl zu erzeugen bis wir eine ziehen die wir noch nicht hatten -> verfälschte bedingte Wahrscheinlichkeiten die nocht der Realität entspricht
b.) die Urne falsch zu mischen, zb. eben 6 mal jeweils 2 Zufallsindizes erzeugen und dann diese zu vertauschen -> verfälschte bedingte Wahrscheinlichkeiten

Extrembeispiel:

Wir wollen aus 10 Milliarden Zahlen nur 3 eindeutige Zahlen ziehen. Elegent ist es die maximale Größe der Urne auf diese 3 Zahlen beschränken zu können. Unelegant ist es ein Array mit 10 Milliarden Zahlen anzulegen und dann 10 Milliarden mal diese per Zufall zu mischen.

Elegant ist also eine Lösung als Funktion die für alle möglichen Anwendungsfälle effizient funktioneren kann, auch wenn es in einem konkreten Fall nicht sofort als Vorraussetzung für diese Funktion als erfoderlich gilt. Denn so hat man eine BlackBox einmalig programmiert die wiederverwendet werden kann ohne das man sie anpassen muß.

Das ist meine Definition von elegant aus Sicht einer Einschätzung der Qualität einer Funktion, neben den Aspekten der Performance, Komplexität und Einfachheit.
"Keep it simple" ist auch eine meiner Devisen, aber nicht auf Teufel komm raus, also Kompromißbasiert (ich meine du denkst da ähnlich). Völlig falsch ist es aber sich nicht an die Rahmenbedingungen zu halten oder jedesmal eine Denkarbeit von Neuem machen zu wollen. Dann lieber beim ersten mal 25% mehr Zeit investiert und gleich was gutes erdacht.

Gruß Hagen

PS: übrigens erfüllt meine obige Funktion "Lotto" eben auch diese Anforderungen. Man kann mit ihr aus 10 Milliarden Zahlen 3 eindeutige und zufällige erzeugen und dabei die begingten Wahrscheinlichkeiten der Realität auch einhalten.Man kann aber auch ganz simpel nur 6 Zahlen aus 6 ziehen ohne das dabei die Peformance oder der Platzverbrauch schlechter wäre als bei den trivialen Lösungen.