Zufallenzahlen sollen nicht doppelt vorkommen



  • Hallo Leute,

    ich habe erst kürzer mit der (c++) Programmierung begonnen und hänge mal wieder an einer Kleinigkeit.

    Ich soll ein Programm schreiben, dass die Lottozahlen ausgibt.
    Mein Programm speichert also 6 Zufallszahlen in einem Array.
    Allerdings kommt es vor, dass auf 2 verschiedenen Speicherplätzen die selbe Zahl gespeichert wird, was ja bei einem Lottoschein nicht vorkommen sollte.

    Habe folgendes Programmstück geschrieben, was dem entgegenwirken soll, aber es funktioniert trotzdem nicht und ich finde meinen Fehler nicht.
    Kann mir jemand helfen??

    for (n=0; n<6; n=n+1)
    {
    l[n] = rand()%49 + 1;
    while (m<n) // Vergleich mit vorhandenen Lottozahlen
    {
    if (l[n] != l[m])
    {m=m+1; continue;}
    else // neue Zufallszahl und while-Schleife von vorn beginnen
    { l[n] = rand()%49 + 1;
    m = 0; continue;}
    }
    }

    Vielen Dank im Voraus!!
    Liebe Grüße von einem C++ - Anfänger 😃



  • Verändere deine Logik: statt x mal zu würfeln, fülle einen container mit allen zahlen von 1 bis 49, verändere die elemente des containers zufällig und gib die ersten 6 (oder irgendwelche elemente) aus.

    Stichworte: std::vector, std::random_shuffle



  • Mathe2107 schrieb:

    for (n=0; n<6; n=n+1)
    {
     l[n] = rand()%49 + 1;    
          while (m<n)          // Vergleich mit vorhandenen Lottozahlen
          {
              if (l[n] != l[m])
                {m=m+1; continue;}
              else        // neue Zufallszahl und while-Schleife von vorn beginnen
                { l[n] = rand()%49 + 1; 
                  m = 0; continue;}        
          }
    }
    

    m wird nicht initialisiert.

    asdfasdfg schrieb:

    Stichworte: std::vector, std::random_shuffle

    Ja, fertige Funktionen sind immer gut um was bei Hausaufgaben zu lernen.



  • In der theorie terminiert dein algorithmus aber nicht (auch wenn rand garantiert gleichverteilte zahlen zurückgibt)

    warum nicht so?

    unsigned arr[49];
    for(unsigned i=0; i!=49; ++i)
        arr[i]=i+1;
    
    for(unsigned i = 0; i != 49; ++i)
        arr[i] = arr[std::rand()%49];
    
    std::cout << arr[0]<<","<< /*...*/ arr[5];
    


  • Mathe2107 schrieb:

    Hallo Leute,

    ich habe erst kürzer mit der (c++) Programmierung begonnen und hänge mal wieder an einer Kleinigkeit.

    Ich soll ein Programm schreiben, dass die Lottozahlen ausgibt.
    Mein Programm speichert also 6 Zufallszahlen in einem Array.
    Allerdings kommt es vor, dass auf 2 verschiedenen Speicherplätzen die selbe Zahl gespeichert wird, was ja bei einem Lottoschein nicht vorkommen sollte.

    Habe folgendes Programmstück geschrieben, was dem entgegenwirken soll, aber es funktioniert trotzdem nicht und ich finde meinen Fehler nicht.
    Kann mir jemand helfen??

    for (n=0; n<6; n=n+1)
    {
    l[n] = rand()%49 + 1;
    while (m<n) // Vergleich mit vorhandenen Lottozahlen
    {
    if (l[n] != l[m])
    {m=m+1; continue;}
    else // neue Zufallszahl und while-Schleife von vorn beginnen
    { l[n] = rand()%49 + 1;
    m = 0; continue;}
    }
    }

    Vielen Dank im Voraus!!
    Liebe Grüße von einem C++ - Anfänger 😃

    Lass mich raten es ist eine Prüfungsaufgabe, oder ? 🙂

    Gruss 1330h@xx0r



  • asdfgadsdf schrieb:

    warum nicht so?

    unsigned arr[49];
    for(unsigned i=0; i!=49; ++i)
        arr[i]=i+1;
    
    for(unsigned i = 0; i != 49; ++i)
        arr[i] = arr[std::rand()%49];
    
    std::cout << arr[0]<<","<< /*...*/ arr[5];
    

    Weil das das Problem nicht löst. z.B. kann die Sequenz std::rand()%49 ja auch 32 34 12 2 5 6 6 34 12 ... sein. Du musst schon die Elemente vertauschen und nicht nur überschreiben.



  • Ein sehr guter Algo um Zufallszahlen schnell und speicherschonend zu berechnen:

    Man erstellt ein Array mit Größe der zu ziehenden Zahlen (im folgenden: N). Nun zieht man eine Zahl zwischen 1 und N und speichert sie ins erste Feld. Als nächsten zieht man eine Zahl von 1 bis N-1. Ist diese gezogene Zahl größer/gleich der ersten Zahl, dann addiert man 1 und speichert die Zahl ins zweite Feld. Nun zieht man eine Zahl von 1 bis N-2. Ist sie wieder größer/gleich als die Erste addiert man wieder 1. Ist sie danach auch noch größer als die Zweite addiert man nochmal 1. Diese Zahl kommt nun ins dritte Feld. Dieses Schema führt man so lange fort bis man N Zahlen hat.



  • Antoras schrieb:

    Ein sehr guter Algo um Zufallszahlen schnell und speicherschonend zu berechnen:

    Man erstellt ein Array mit Größe der zu ziehenden Zahlen (im folgenden: N). Nun zieht man eine Zahl zwischen 1 und N und speichert sie ins erste Feld. Als nächsten zieht man eine Zahl von 1 bis N-1. Ist diese gezogene Zahl größer/gleich der ersten Zahl, dann addiert man 1 und speichert die Zahl ins zweite Feld. Nun zieht man eine Zahl von 1 bis N-2. Ist sie wieder größer/gleich als die Erste addiert man wieder 1. Ist sie danach auch noch größer als die Zweite addiert man nochmal 1. Diese Zahl kommt nun ins dritte Feld. Dieses Schema führt man so lange fort bis man N Zahlen hat.

    Also ich bin schon etwas müde, aber die Verteilung der Wert hängt hier doch klar vom ersten gezogenen Wert ab. Und was wenn ich beim ersten Schritt gleich N ziehe? Und wirklich gut skalieren kann das auch nicht. Ein random shuffle ist O(n). Was dieser Algo tut will ich jetzt nicht ausrechnen müssen.



  • Ein Shuffle ist deutlich ineffizienter. Wir haben nämlich zwei Parameter: n für die Größe des Zahlenbereichs und k für die Anzahl der zu ziehenden Zahlen. Ein Shuffle ist O(n) und n Speicherverbrauch. Der genannte Algo hingegen ist O(k) und k Speicherverbrauch. Und es ist irrelevant ob k schon am Anfang gezogen wird oder nicht, da n mit jedem Durchlauf um 1 subtrahiert wird. n könnte also nicht nochmal gezogen werden. Die gezogene Zahl wird ja immer nur dann erhöht wenn sie größer/gleich der vorherigen Zahlen ist.



  • Antoras: Du verzerrst aber die Wahrscheinlichkeitsverteilung mit deinem Algorithmus.

    Angenommen im ersten Durchlauf ziehst du die Zahl x. Dann ist die Wahrscheinlichkeit für x+1 im nächsten Durchlauf nicht 1/(n-1), sondern 2/(n-1), da das Ergebnis "x+1" für die Ereignisse "x" und "x+1" geschrieben würde usw. Dadurch können Ketten entstehen, sodass deine tatsächliche Wahrscheinlichkeitsverteilung nicht mehr viel mit der Gleichverteilung zu tun hat.

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$


  • Mod

    Michael E. schrieb:

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$

    Mit der Komplexität hat er schon recht, der random_shuffle ist keine so gute Idee. Man muss die Methode zum Zahlenziehen bloß ein bisschen anpassen: Man erstellt ein Array der Größe k. Nun zieht man eine Zahl zwischen 1 und N und speichert sie im ersten Feld. Als nächsten zieht man eine Zahl von 1 bis N-1. Ist diese gezogene Zahl gleich der ersten Zahl, so nimmt man stattdessen N. Die Zahl speichert man in das zweite Feld. Als nächsten zieht man eine Zahl von 1 bis N-2. Ist die Zahl gleich einer der ersten gezogenen Zahl, nimmt man stattdessen N. Ist die Zahl gleich der zweiten gezogenen Zahl, nimmt man stattdessen N-1. Muster fortführen bis k Zahlen gezogen wurden.

    Dies hat eine Komplexität von k² Vergleichen, was gut sein kann, da k<N (aber es ist nicht zwangsläufig besser als Komplexität N des shuffles). Außerdem ist die Anzahl der Zufallszahlen gleich k und nicht wie beim shuffle N. Und die Zufallszahlzieherei ist im Vergleich zu Vergleichen 😉 eine teure Operation. Wieder ist k (möglicherweise deutlich) kleiner als N.



  • SeppJ schrieb:

    Michael E. schrieb:

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$

    Mit der Komplexität hat er schon recht, der random_shuffle ist keine so gute Idee.

    Das sollte eigentlich ne Komplexitätsschätzung für Antoras' Algorithmus sein. Denk dir einfach ein k statt nem n. Was würdest du denn sagen, was dieser Algorithmus für ne Komplexität hat?

    Man muss die Methode zum Zahlenziehen bloß ein bisschen anpassen: Man erstellt ein Array der Größe k. Nun zieht man eine Zahl zwischen 1 und N und speichert sie im ersten Feld. Als nächsten zieht man eine Zahl von 1 bis N-1. Ist diese gezogene Zahl gleich der ersten Zahl, so nimmt man stattdessen N. Die Zahl speichert man in das zweite Feld. Als nächsten zieht man eine Zahl von 1 bis N-2. Ist die Zahl gleich einer der ersten gezogenen Zahl, nimmt man stattdessen N. Ist die Zahl gleich der zweiten gezogenen Zahl, nimmt man stattdessen N-1. Muster fortführen bis k Zahlen gezogen wurden.

    Das ist ne coole Idee, auch wenn dadurch manche Kombinationen unmöglich werden. Aber ich denke, diese Bedenken kann man getrost vergessen, wenn man bedenkt, wie schlecht std::rand oftmals implementiert ist 😉

    Wenn k deutlich kleiner ist als n und ich nicht in garantierter Zeit die nächste Zahl liefern muss, würde ich wahrscheinlich einfach solange rand aufrufen, bis es mir ne Zahl liefert, die ich bisher noch nicht hatte.


  • Mod

    Michael E. schrieb:

    SeppJ schrieb:

    Michael E. schrieb:

    Edit: Die Komplexität wird dann auch eher sowas sein wie $$\mathcal{O}\left(n \sum\limits_{i=1}^{n} \frac 1i \right)$$

    Mit der Komplexität hat er schon recht, der random_shuffle ist keine so gute Idee.

    Das sollte eigentlich ne Komplexitätsschätzung für Antoras' Algorithmus sein. Denk dir einfach ein k statt nem n. Was würdest du denn sagen, was dieser Algorithmus für ne Komplexität hat?

    Ähnlich wie mein Vorschlag, da ist aber noch ein statistisches Element drin, dass ich zu dieser späten Stunde nicht analysieren mag. Worst-Case dürften aber k² Vergleiche sein. Und natürlich auch wieder k Zufallszahlen, was für kleine k deutlich teurer sein kann als die Vergleiche.

    Das ist ne coole Idee, auch wenn dadurch manche Kombinationen unmöglich werden. Aber ich denke, diese Bedenken kann man getrost vergessen, wenn man bedenkt, wie schlecht std::rand oftmals implementiert ist 😉

    Wenn k deutlich kleiner ist als n und ich nicht in garantierter Zeit die nächste Zahl liefern muss, würde ich wahrscheinlich einfach solange rand aufrufen, bis es mir ne Zahl liefert, die ich bisher noch nicht hatte.

    Och, den Anspruch habe ich aber, so etwas wenn überhaupt, dann perfekt zu machen*. Ein Lottoprogramm welches so arbeitet, würde ich mich ein bisschen für schämen. Und es ist natürlich auch ganz nützlich, sich über so etwas Gedanken zu machen, wenn man mal in die Bereiche k=N/2 kommt (bei k>N/2 kann man ja auch ziehen, welche Zahlen man nicht nimmt), damit der Algorithmus schnell terminiert.

    *: Das ist aber auch so eine Macke von mir. Ich bin viel zu perfektionistisch und verschwende deswegen viel zu viel Zeit.



  • Du kannst das Array in dem du die gezogenen Zahlen reinlegst auch sortiert halten. Dann brauchst du höchstens einmal über das Array iterieren. Eine Hälfte des Arrays um die einzufügende Position zu suchen und die neue Zahl einzufügen, die zweite um nach dem Einfügen die anderen Elemente nach hinten zu swappen.

    Du ziehst nach wie vor K-N (K die Gesamtanzahl der Elemente, N die bereits gezogenen), kannst dann aber nach dem Finden der richtigen Position den aktuellen Arrayindex aufaddieren. Du ziehst also praktisch aus der Anzahl der noch übrigen Elemente und überspringst dann diejenigen, die davor liegen. Vergiss nicht, auch zum Vergleichen den aktuellen Index aufzuaddieren!

    O(N) erreicht.



  • Vorweg: ich nenne die Anzahl der zu ziehenden Zahlen N und die grösse der Menge aus der gezogen wird M.
    (K und N wie Antoras in seinem Beitrag verwendet hat verwirrt mich hier zu sehr *g*)

    Also wir ziehe N=6 aus M=49.

    Random-Shuffle wurde erwähnt, Komplexität ist hier O(M). Bei grossen M also doof. Bei kleinen M ideal.

    @Michael E.:

    1. Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich. Weiss nicht wie du darauf kommst.
      Ist im Prinzip dasselbe wie wenn man einen Pot (z.B. std::vector) voll mit Zahlen von 1 bis M macht, und dann immer zufällig eine rausnimmt (=löscht). Das zerstört in keiner Weise irgendwas, das ist so zufällig wie es nur sein kann. Nur dass man sich das Erstellen des Pot und das Rausnehmen auch sparen kann, was die Sache bei grossen M deutlich schneller macht.
      Und was dabei rauskommt wenn man den Pot wegoptimiert hat Antoras beschrieben, ist nichts anderes.

    2. Die Komplexität des von Antoras beschriebenen Algorithmus ist O(N^2) wenn man ihn trivial implementiert:

    Man macht N Ziehungen.
    Bei jeder Ziehung muss man eine Zahl ermitteln und diese abspeichern. Das zählen wir als eine Operation (Zahl ermitteln sollte O(1) sein und Anhängen an einen std::vector/std::list/array/... ist O(1))
    Bei der 1. Ziehung kommt sonst nichts dazu.
    Bei der 2. Ziehung kommt ein Vergleich mit der ersten Zahl dazu, sowie möglicherweise ein Inkrement. Vergleich + Inkrement zählen wir auch als eine Operation. -> die 2. Ziehung braucht 2 Operationen.
    Bei der 3. Ziehung kommt 2x (Vergleich + Inkrement) dazu (sind ja schon 2 Zahlen in der Liste): 3 Operationen
    4. Ziehung: 4 Operationen
    ....
    N. Ziehung: N Operationen
    In Summe: 1+2+3+4+ ... +N Operationen, und das ist O(N^2).

    Das Ganze sollte sich optimieren lassen, wenn man statt eine einfachen Containers (wie std::vector) einen passenderen Container verwendet, so dass folgende Operationen in O(N log N) möglich sind:
    * Suchen einer Zahl im Container
    * Einfügen einer neuen Zahl
    * Ermitteln wie viele kleinere Zahlen im Container enthalten sind
    IMO müsste das mit den meisten Bäumen gehen (z.B. 2-3 Baum oder auch beliebige B-Bäume).
    (EDIT: wenn man den Algorithmus leicht modifiziert fällt die ist die letzte Anforderung an den Container, d.h. man kann gleich std::set oder ähnliches verwenden)

    Damit sollte der gesamte Algorithmus dann O(N log N) haben. Ich gehe davon aus dass das die bestmögliche Komplexität für den Fall M >> N ist.

    Das so für eine Hausaufgabe zu implementieren ist natürlich Overkill.

    @Antoras:

    Siehe oben.
    Der von dir beschriebene Algorithmus ist nicht O(N) sondern bestenfalls O(N log N), und so wie du ihn beschrieben hast sogar O(N^2).

    -----

    Zurück zum Thema.
    Wenn N=6 und M=49 feststehen würde ich ohne grösser zu überlegen eine von zwei (drei) Möglichkeiten wählen:

    * Wenn die Verwendung der Standard-Library etc. erlaubt ist: Random-Shuffle (M=49 ist definitiv ausreichend klein).

    * Wenn die Verwendung der Standard-Library nicht erlaubt ist, und man alles "zu Fuss" programmieren soll (und keine "Echtzeit" gefordert ist): Zahlen ziehen, merken, auf Duplikate checken und Duplikate verwerfen (neu ziehen). Die oben beschriebene Variante ist zwar in der Theorie besser, allerdings spielt das bei kleinen N, M keine Rolle. Und die "Verwerfen" Methode ist einfacher zu verstehen und einfacher zu implementieren. Natürlich ist dieser Algorithmus auch nicht deterministisch, spielt aber in der Praxis keine Rolle, da er immer ausreichend schnell terminiert. Mal vorausgesetzt dass der RNG kein kompletter Müll ist.

    Und wenn doch Echtzeit gefordert ist würde ich vermutlich die triviale Implementierung des von Antoras' beschriebenen Algorithmus implementieren. Eine O(N log N) wäre bei N = 6 ziemlich sicher langsamer, und ausserdem ... wen interessiert's für ne Hausaufgabe 🙂



  • Reintun sortiere schrieb:

    Du kannst das Array in dem du die gezogenen Zahlen reinlegst auch sortiert halten. Dann brauchst du höchstens einmal über das Array iterieren. Eine Hälfte des Arrays um die einzufügende Position zu suchen und die neue Zahl einzufügen, die zweite um nach dem Einfügen die anderen Elemente nach hinten zu swappen.

    Du ziehst nach wie vor K-N (K die Gesamtanzahl der Elemente, N die bereits gezogenen), kannst dann aber nach dem Finden der richtigen Position den aktuellen Arrayindex aufaddieren. Du ziehst also praktisch aus der Anzahl der noch übrigen Elemente und überspringst dann diejenigen, die davor liegen. Vergiss nicht, auch zum Vergleichen den aktuellen Index aufzuaddieren!

    O(N) erreicht.

    Nein, das ist genau so O(N^2).



  • Wieso wird über die Laufzeit geredet? Ist ein Shuffle halt teuer, ist doch egal.
    Bei dem echten Lotto wird auch ne Weile die Trommel gerührt 😃

    - Liste mit den Zahlen erstellen
    - User Sagt "Start"
    - Das Programm ruft so lange Shuffle auf bis der Benutzer auf "Stop" klickt
    - Zahl wird genommen (und aus der Liste entfernt) und wieder weiter geshufflet bis der User erneut auf Stop klickt...

    Wie beim echten Lotto.



  • Ah, ich habe gerade gesehen, dass Antoras das gleiche Verfahren schon erwähnt hatte. Das O(N) bezog ich auf das einmalige Ziehen einer Zahl mit N := Anzahl der bereits gezogenen Zahlen. Ich habe dazu noch ein Snippet herumliegen. Das Ziehen sieht dort so aus:

    procedure Random (This   : in out Generator;
                      Number :    out Integer) is
       use Number_Storage;
    
       Random_Number : Integer;
       Number_Count  : Natural := Natural(This.Stored_Numbers.Length);
    
       Cursor : Number_Storage.Cursor;
    begin
       Random_Number := Random_Integer (This.Random_Generator,
                                        This.First,
                                        This.Last - Number_Count);
    
       if Number_Count <= 0 then
          This.Stored_Numbers.Append (Random_Number);
          Number := Random_Number;
       elsif Random_Number + Number_Count > Element (This.Stored_Numbers.Last) then
          This.Stored_Numbers.Append (Random_Number + Number_Count);
          Number := Random_Number + Number_Count;
       else
          Cursor := This.Stored_Numbers.First;
          while Random_Number + To_Index (Cursor) >= Element (Cursor) loop
             Next (Cursor);
          end loop;
          Number := Random_Number + To_Index (Cursor);
          This.Stored_Numbers.Insert (Cursor, Random_Number + To_Index (Cursor));
       end if;
    end Random;
    


  • @hustbaer
    Danke für deine Erklärung. Ich hatte das ein bisschen missverständlich ausgedrückt - hätte gleich auf die zwei Parameter eingehen sollen und nicht nur auf einen.

    Wenn man eine einfache Lösung haben will, dann ist ein Shuffle mit Sicherheit die beste Wahl, ansonsten kann man sich den Algo ja echt mal angucken.



  • Hier gibt es einen älteren Thread zum Thema Würfeln:
    http://www.c-plusplus.net/forum/47483?highlight=w�rfel


Anmelden zum Antworten