Zufallenzahlen sollen nicht doppelt vorkommen

[Antoras]

@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.

[Erhard Henkes]

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

[Michael E.]

hustbaer schrieb:

Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

Stimmt, er funktioniert gar nicht.

Ziehe 3 Zahlen aus 6. Sei das Ergebnisarray nach zwei Durchgängen [3, 2] (3 zuerst gezogen). Dann ziehst du eine Zahl aus [1, 2, 3, 4] und mappst diese auf [1, 4, 5, 6].

Nun zieht man eine Zahl von 1 bis N-2.

Angenommen, du ziehst eine 2.

Ist sie wieder größer/gleich als die Erste addiert man wieder 1.

Nö, 2 < 3.

Ist sie danach auch noch größer als die Zweite addiert man nochmal 1.

Diese Zeile interpretiert als if und nicht als else if ergibt 2 + 1 = 3.

Diese Zahl kommt nun ins dritte Feld.

Also ist das Ergebnisarray [3, 2, 3].

Soll das Ergebnisarray vielleicht sortiert sein?

[Mathe2107]

´@codetagger
ich habe am anfang meines kompletten programms "int m=0" gesetzt... war vllt. ungünstig nur einen teil meines programms hier zu posten, aber das ist eben der teil der nicht funktioniert ...

[Mathe2107]

erst einmal danke für die vielen beiträge... leider bin ich jetzt nicht schlauer als vorher.
wie erwähnt bin ich c++ anfänger und weiß daher gar nicht, was Random-Shuffle und Komplexität in einem programm bewirken.

außerdem wüsste ich gerne, was in MEINEM programmstück nicht richtig läuft, also meinen fehler finden und daraus lernen und nicht eine komplett andere idee benutzen. das ist ja nicht sinn der übung.
(also nein, es ist keine prüfungsaufgabe, ich bin noch in meiner modulteilleistung)

ich kann natürlich noch einmal mein ganzes programm posten, vllt. weiß ja dann jemand eher etwas... also:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;
int main ()
{
int z; // Zahlen von 1-49
int n; // Laufvariable für n Speicherplätze
int m;
int l[6]; // Speicherplatz für 6 Lottozahlen

srand(time(NULL)); // Zufallsgenerator initialisieren

for (n=0; n<6; n=n+1)
{
l[n] = rand()%49 + 1; // 1 <= l <= 49 ~~> Lottozahlen im Bereich von 1 bis 49

while (m<n)
{
if (l[n] != l[m])
{m=m+1; continue;}
else
{ l[n] = rand()%49 + 1;
m = 0; continue;}
}
}

for (z=1; z<50; z=z+1)
{ // Statt der Zufallszahl soll ein 'X' stehen

if (z == l[0] || z == l[1] || z == l[2] || z == l[3] || z == l[4] || z == l[5])
cout << " X ";
else
if (z<10) // Vor einstelligen Zahlen ein Leerzeichen
cout << " " << z << " ";
else
cout << z << " ";

if ((z%7)!=0) // Neue Zeile beginnen nach Zahl, die durch 7 teilbar ist
; // leerer Rumpf
else
cout << "\n";
}

return 0;
}

[SeppJ]

Erster Fehler: m wird vor Benutzung nicht initialisiert. Weiter habe ich jetzt nicht gelesen sondern bloß überflogen, aber dies sollte es sein.

[Antoras]

@Michael E.
Ich sehe gerade, dass ich vergessen habe zu erwähnen, dass die Zahlen geordnet sein müssen. Es reicht also nicht sie nur im nächsten Array-index abzuspeichern, das hab ich falsch erklärt.

Weiterhin wird bei jedem Durchlauf immer nur die gezogene Zahl um eins hochgezählt, nicht die noch verfügbaren.

Bsp mit 6 aus 49:

1. Zahl = 7 (aus 49 verfügbaren):
Zahl wird unverändert gespeichert.
2. Zahl = 3 (aus 48 verfügbaren):
Da sie kleiner als 1.Zahl ist wird sie auch unverändert gespeichert.
3. Zahl = 6 (aus 47 verfügbaren):
Sie ist größer als die erste Zahl, die 3, also wird sie um 1 erhöht. Nun haben wir eine 7 welche gleich der bereits gespeicherten 7 ist. Sie wird nochmals um 1 erhöht. Eine 8 wird abgespeichert.
4. Zahl = 46 (aus 46 verfügbaren):
Sie ist größer als alle anderen Zahlen, also wird 4 addiert. Eine 49 wird abgespeichert.
5. Zahl = 1 (aus 45 verfügbaren):
Sie ist kleiner als alle anderen Zahlen. Also wird sie unverändert abgespeichert.
6. Zahl = 6 (aus 44 verfügbaren):
Sie ist größer als die 3. Eins wird addiert. Nun ist sie gleich der nächsten Zahl, der 7. Es wird nochmal 1 addiert. Die neue Zahl ist gleich der 8 also wird nochmal 1 addiert und eine 9 abgespeichert.

Ergebnis: 1,3,6,7,8,49
Alle Zahlen bleiben verfügbar. Und die Wahrscheinlichkeitsverteilung ändert sich auch nicht. Wichtig ist wirklich nur, dass die Zahlen geordnet abgespeichert werden.

[Reintun sortiere]

Michael E. schrieb:

hustbaer schrieb:

Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

Stimmt, er funktioniert gar nicht.

Ziehe 3 Zahlen aus 6. Sei das Ergebnisarray nach zwei Durchgängen [3, 2] (3 zuerst gezogen). Dann ziehst du eine Zahl aus [1, 2, 3, 4] und mappst diese auf [1, 4, 5, 6].

Nun zieht man eine Zahl von 1 bis N-2.

Angenommen, du ziehst eine 2.

Ist sie wieder größer/gleich als die Erste addiert man wieder 1.

Nö, 2 < 3.

Ist sie danach auch noch größer als die Zweite addiert man nochmal 1.

Diese Zeile interpretiert als if und nicht als else if ergibt 2 + 1 = 3.

Diese Zahl kommt nun ins dritte Feld.

Also ist das Ergebnisarray [3, 2, 3].

Soll das Ergebnisarray vielleicht sortiert sein?

Es funktioniert definitv. Probier es doch aus:

-- random_x_of_y.ads
with Ada.Numerics.Float_Random; use Ada.Numerics;
with Ada.Containers.Vectors; use Ada.Containers;

package Random_X_Of_Y is

   package Number_Storage is new Vectors (Index_Type   => Natural,
                                          Element_Type => Integer);

   type Generator is limited private;

   procedure Reset (This : in out Generator; First, Last : in Integer);

   procedure Random (This   : in out Generator;
                     Number :    out Integer);
private
   type Generator is record
      Random_Generator : Float_Random.Generator;
      Stored_Numbers : Number_Storage.Vector;
      First : Integer;
      Last  : Integer;
   end record;
end Random_X_Of_Y;

-- random_x_of_y.adb
package body Random_X_Of_Y is
   ----------------------------------------------------------------------------
   procedure Reset (This : in out Generator; First, Last : in Integer) is
   begin
      This.First := First;
      This.Last  := Last;
      Float_Random.Reset (This.Random_Generator);
      Number_Storage.Set_Length (This.Stored_Numbers, 0);
   end Reset;
   ----------------------------------------------------------------------------
   function Random_Integer (G         : Float_Random.Generator; 
                            Low, High : Integer) return Integer is
      M : Integer := High - Low + 1;
   begin      
      return Low + (Integer(Float(M) * Float_Random.Random(G)) mod M);
   end Random_Integer;
   ----------------------------------------------------------------------------
   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;
   ----------------------------------------------------------------------------
end Random_X_Of_Y;

Und zum Testen:

-- lotto.adb
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

with Random_X_Of_Y;

procedure Lotto is
   subtype Lotto_Type is Natural range 1 .. 49;

   Generator : Random_X_Of_Y.Generator;
   Number    : Lotto_Type;
begin
   Random_X_Of_Y.Reset (Generator, Lotto_Type'First, Lotto_Type'Last);
   for I in 1 .. 6 loop
      Random_X_Of_Y.Random (Generator, Number);
      Put (Integer(Number));
      New_Line;
   end loop;
end Lotto;

Zum besseren Testen kannst du auch mal 6 aus 6 ziehen.

Angenommen du ziehst 6 aus 1..6 und hast 1, 2 und 4 bereits gezogen. Dann ziehst du nur aus 0..2 und der Inhalt des Arrays der gezogenen Zahlen sieht so aus:
(1, 2, 4)

Dieser Inhalt beschreibt praktisch die Positionen in einem Array für eine Maske, die du dann für die restlichen 3 Zahlen verwendest:
(-, -, 1, -, 2, 3)

Ziehst du eine 1, dann vergleichst du die 1 mit der Zahl an Position 0. 0 + 1 ist größer gleich der 1 im ersten Feld, also vergleichst du mit dem nächsten Feld an Index 1. 1 + 1 ist größer gleich der 2 an Position 1, also vergleichst du mit dem dritten Feld an Index 2. dort steht eine 4 drin. 1 + 2 ist nicht größer gleich dieser 4, dein neues Ergebnis ist also 1 + 2 = 3. Dieses Ergebnis sortierst du jetzt ein:
( 1, 2, 3, 4)

[Michael E.]

Reintun sortiere schrieb:

Michael E. schrieb:

hustbaer schrieb:

Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

Stimmt, er funktioniert gar nicht.

Ziehe 3 Zahlen aus 6. Sei das Ergebnisarray nach zwei Durchgängen [3, 2] (3 zuerst gezogen). Dann ziehst du eine Zahl aus [1, 2, 3, 4] und mappst diese auf [1, 4, 5, 6].

Nun zieht man eine Zahl von 1 bis N-2.

Angenommen, du ziehst eine 2.

Ist sie wieder größer/gleich als die Erste addiert man wieder 1.

Nö, 2 < 3.

Ist sie danach auch noch größer als die Zweite addiert man nochmal 1.

Diese Zeile interpretiert als if und nicht als else if ergibt 2 + 1 = 3.

Diese Zahl kommt nun ins dritte Feld.

Also ist das Ergebnisarray [3, 2, 3].

Soll das Ergebnisarray vielleicht sortiert sein?

Es funktioniert definitv.

Dann wäre es nett, mir zu sagen, was ich bei meinem Beispiel falsch gemacht haben soll, statt mir 100 Zeilen Code hinzuknallen in einer Sprache, für die ich nicht mal nen Compiler hab, sodass das Ausprobieren etwas schwierig wird

[Jockelx]

Reintun sortiere schrieb:

Es funktioniert definitv. Probier es doch aus:

Nein, so wie es beschrieben wurde,funktioniert es offenbar nicht:

007EF6C9  mov         dword ptr [ebp-8Ch],eax 
007EF6CF  mov         edx,dword ptr [ebp-8Ch] 
007EF6D5  mov         dword ptr [ebp-5Ch],edx 
007EF6D8  mov         dword ptr [ebp-4],4 
007EF6DF  mov         eax,dword ptr [ebp-34h] 
007EF6E2  or          eax,2 
007EF6E5  mov         dword ptr [ebp-34h],eax 
007EF6E8  mov         ecx,dword ptr [ebp-5Ch] 
007EF6EB  mov         edx,dword ptr [ecx] 
007EF6ED  mov         dword ptr [ebp-54h],edx 
007EF6F0  mov         eax,dword ptr [ebp-54h] 
007EF6F3  mov         dword ptr [ebp-50h],eax 
007EF6F6  mov         ecx,dword ptr [ebp-5Ch] 
007EF6F9  mov         edx,dword ptr [ecx] 
007EF6FB  mov         eax,dword ptr [edx-8] 
007EF6FE  mov         dword ptr [ebp-58h],eax 
007EF701  mov         ecx,dword ptr [ebp-58h] 
007EF704  mov         dword ptr [ebp-4Ch],ecx

[Reintun sortiere]

Mathe2107 schrieb:

erst einmal danke für die vielen beiträge... leider bin ich jetzt nicht schlauer als vorher.
wie erwähnt bin ich c++ anfänger und weiß daher gar nicht, was Random-Shuffle und Komplexität in einem programm bewirken.

außerdem wüsste ich gerne, was in MEINEM programmstück nicht richtig läuft, also meinen fehler finden und daraus lernen und nicht eine komplett andere idee benutzen. das ist ja nicht sinn der übung.
(also nein, es ist keine prüfungsaufgabe, ich bin noch in meiner modulteilleistung)

Mit Komplexität brauchst du dich erstmal nicht beschäftigen. Random-Schuffle ist eine Funktion, die die Elemente einer Datenstruktur zufällig durcheinanderwürfelt.

Nutze bitte die Code-Tags des Forums, dann kann man deinen Quelltext auch besser lesen.

Bevor du aber das Programm schreibst, wäre es gut sich ein funktionierendes Verfahren zu überlegen und erst einmal darüber zu reden.

Dann wäre es nett, mit zu sagen, was ich bei meinem Beispiel falsch gemacht haben soll, statt mir 100 Zeilen Code hinzuknallen in einer Sprache, für die ich nicht mal nen Compiler hab, sodass das Ausprobieren etwas schwierig wird

Wenn du auf einem Linux-System bist, ist das mit dem Compiler kein Problem.

zypper install gcc-ada
gnatmake lotto.adb
zypper remove gcc-ada

Ist sogar einfacher, als wenn das in C oder C++ geschrieben und der Compiler bereits installiert wäre.

Was an deinem Beispiel falsch ist, hat Antoras ja schon gesagt: Du musst die neu gezogene Zahl an der richtigen Stelle einfügen, damit das Array immer sortiert bleibt.

[hustbaer]

Michael E. schrieb:

hustbaer schrieb:

Antoras' Algorithmus zerstört nicht die Gleichverteilung, und macht auch keine Kombinationen unmöglich.

Stimmt, er funktioniert gar nicht.
(...)
Soll das Ergebnisarray vielleicht sortiert sein?

Ja, soll sortiert sein. Da mir der Algorithmus bekannt ist, hab ich die Beschreibung nicht all zu genau gelesen nachden ich erkannt habe was hier beschrieben wird. Ist mir nicht aufgefallen dass die Info fehlt.

[hustbaer]

David W schrieb:

Wieso wird über die Laufzeit geredet?

Weil hier Informatiker/Programmierer verkehren?

[Michael E.]

Reintun sortiere schrieb:

Wenn du auf einem Linux-System bist, ist das mit dem Compiler kein Problem.

Ich bin aber nicht auf nem Linux-System. Selbst wenn ich das wäre, was würde mir das bringen? Zu sehen, dass dein Programm manchmal funktioniert?

Was an deinem Beispiel falsch ist, hat Antoras ja schon gesagt: Du musst die neu gezogene Zahl an der richtigen Stelle einfügen, damit das Array immer sortiert bleibt.

Das hab ich selber vermutet, noch bevor jemand gesagt hat, dass das nötig ist

[Mathe2107]

Ihr braucht gar nicht so lange Texte zu schreiben, SeppJ hatte vollkommen Recht.
DANKE
Meistens übersieht man (ich) ja so kleine Fehler

Thema beendet!

[Reintun sortiere]

Als Beispiel ziehe ich mal aus 1 .. 6

Du hast 2 Mengen die dir bekannt sind.
1. Die Menge der insgesamt möglichen Zahlen
2. Die Menge der bereits gezogenen Zahlen

Daraus ergibt sich 3. die Menge der aktuell noch möglichen Zahlen.

Wenn du die Mengen als Felder aufschreibst, hast du beispielweise
1. { 1, 2, 3, 4, 5, 6 }
2. { 1, 2, 4, 6 }
3. { 3, 5 }

Jetzt kannst du die Felder übereinander legen:

{ 1, 2, 3, 4, 5, 6 }
{ 1, 2, X, 4, X, 6 }
{ X, X, 3, X, 5, X }

Indizes der Mengen:

{ 1, 2, 3, 4, 5, 6 }
{ 1, 2, X, 3, X, 4 }
{ X, X, 1, X, 2, X }

In dem Verfahren ziehst du jetzt zufällig einen der Indizes der noch verfügbaren Zahlen. Hier ist es eine 1 oder eine 2. Die Verteilung ist also wie bei jedem Zug aus dem Zufallsgenerator. Alle übrigen Zahlen sind möglich und werden mit gleicher Wahrscheinlichkeit gezogen.

Jetzt musst du nur noch den Index finden, den die Zufallszahl in der Menge der insgesamt möglichen Zahlen (1.) entspricht. Beim Ziehen einer 1 ist es die 3, beim Ziehen einer 2 die 5. Das sind genau die beiden noch fehlenden Zahlen. Und sie werden mit einer gleich verteilten Wahrscheinlichkeit gezogen. Dieses Verfahren funktioniert für beliebige Mengen 1 und 2, wobei Menge 2 natürlich Teilmenge aus 1 sein muss.

Du benötigst nur 2 Informationen pro Mengenelement: Einen Zahlenwert und ein Index. Den Zahlenwert speicherst du, der Index ergibt sich aus der Position in der Datenstruktur (oder einem Start- und Endwert wie 1 .. 49 im Beispielprogramm). Daher ist es auch wichtig die Datenstruktur sortiert zu halten. Der Index muss zur Zahl passen.

[codetagger]

Mathe2107 schrieb:

Ihr braucht gar nicht so lange Texte zu schreiben, SeppJ hatte vollkommen Recht.
DANKE
Meistens übersieht man (ich) ja so kleine Fehler

Thema beendet!

Das was der sagte, hab ich schon am Anfang gesagt.

hustbaer schrieb:

David W schrieb:

Wieso wird über die Laufzeit geredet?

Weil hier Informatiker/Programmierer verkehren?

Ne, weil hier Prematureoptimierer verkehren, die sogar nicht messbare Unterschiede in einem simplen Lottospielchen "optimieren".

[hustbaer]

codetagger schrieb:

hustbaer schrieb:

David W schrieb:

Wieso wird über die Laufzeit geredet?

Weil hier Informatiker/Programmierer verkehren?

Ne, weil hier Prematureoptimierer verkehren, die sogar nicht messbare Unterschiede in einem simplen Lottospielchen "optimieren".

Wenn du meinst dass es wertlos ist sich Gedanken über theoretische Programmierprobleme zu machen, auch wenn man sie nicht gerade aktuell implementieren muss und/oder die aktuelle Problemgrösse so klein ist, dass es keinen Unterschied macht...
Den Rest kannst du dir vermutlich denken.

[Michael E.]

Reintun sortiere schrieb:

Als Beispiel ziehe ich mal aus 1 .. 6

Es ist lieb von dir, dass du dir so viel Mühe machst, aber seit ich rausgefunden habe, dass das Array sortiert sein soll, hab ich keine Probleme mit dem Algorithmus Vielleicht hilfts ja jemand anderem.

[codetagger]

hustbaer schrieb:

codetagger schrieb:

hustbaer schrieb:

David W schrieb:

Wieso wird über die Laufzeit geredet?

Weil hier Informatiker/Programmierer verkehren?

Ne, weil hier Prematureoptimierer verkehren, die sogar nicht messbare Unterschiede in einem simplen Lottospielchen "optimieren".

Wenn du meinst dass es wertlos ist sich Gedanken über theoretische Programmierprobleme zu machen, auch wenn man sie nicht gerade aktuell implementieren muss und/oder die aktuelle Problemgrösse so klein ist, dass es keinen Unterschied macht...
Den Rest kannst du dir vermutlich denken.

Wenn ihr euch mal Gedanken über kompiliziertere und sinnvollere Sachen, wie Softwaredesign und Architektur, machen würdet, dann würde man vlt. weniger scheußlichen Code in Firmen finden. Aber hier gibts immer nur Gedanken über mini Probleme.