Wie mache ich es, dass die Zahlen nicht zwei Mal vorkommen?

Damian_Hiller

Grünschnabel
Also ich soll 6 Lottozahlen herausgeben und die sollen sich bei der Ausgabe nicht wiederholen. Generieren und Ausgeben ist kein Problem, aber ich finde einfach nirgendwo im Internet eine Lösung dazu..
C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void) {
    int min = 1;
    int max = 49;
   int meinezahlen[]= {4,8,15,16,23,42};
   int lottozahlen[49];
   int zufall;
   int i =1;

   srand(time(NULL));

   for (i; i<7;i++){


           zufall = (rand()% ((max+1)-min))+min;

       printf("Zahl %d: ", i);

           printf("%d\n", zufall);

   }
   return EXIT_SUCCESS;
}
Ausgabe:
Zahl 1: 46
Zahl 2: 25
Zahl 3: 15
Zahl 4: 25
Zahl 5: 1
Zahl 6: 23
(Die Zahlen sind jedes Mal andere)
 

cwriter

Erfahrenes Mitglied
Hi

Also ich soll 6 Lottozahlen herausgeben und die sollen sich bei der Ausgabe nicht wiederholen.
Halfbax hat ja schon einige gute Links herausgesucht, aber diese haben je ein paar Unreinheiten:
Der erste Link wird extrem aufwändig bei mehr Möglichkeiten (n = Anzahl Möglichkeiten), da O(n) Speicherplatz benötigt wird und der Aufwand O(n) beträgt.
Der zweite Link ist ein bisschen besser: O(k²) Laufzeit und O(k) Speicherplatz, wobei k die Anzahl gezogener Zahlen ist. Somit ist der Speicherplatz bereits optimal.

Eine weitere Option ist, einfaches Sonderien zu verwenden:
Wenn du Modulo verwendest, sorgst du für ständige Repetition. Z.B. ist 7 % 10 == 7, aber auch 17 % 10 == 7 usw.
Du machst dir diesen Mechanismus bereits zu nutze, wo die die Zufallszahlen berechnest.
Da die Lottozahlen in N stetig sind, kannst du das ausnutzen, ohne die Möglichkeiten zwischenspeichern zu müssen:
Dazu ein Programmablauf:
1. Du ziehst irgendeine Zahl.
2. Du überprüfst, ob diese Zahl modulo dem erlaubten Bereich schon vorkommt.
-> Falls Ja: Erhöhe die gezogene Zahl um 1 (oder ziehe einfach nochmals) und springe zu 2.
-> Falls Nein: Fahre fort
3. Speichere die Zahl.

Was folgt, bezieht sich nur auf die Datenstrukturen und deren Effizienzen.
Bitte nicht verwirren lassen!

Im Prinzip also das Gleiche wie der Ansatz im 2. Link. Aber wir können das noch stark verbessern:
Die Suche nach bereits existierenden Elementen beträgt beim Link eine Komplexität O(k²). Das hat damit zu tun, dass dieser Ansatz (bzw. diese Art der Speicherung) die Sortierbarkeit der Zahlen nicht ausnutzt.
Nehmen wir mal einen Array. Dieser ist bei kleinen 'k' noch sehr gut. Bei höheren 'k' mit einer ähnlich niedrigen Konfliktchance (Wahrscheinlichkeit, dass dieselbe Zahl öfter gezogen wird), ist ein AVL- oder Rot-Schwarz-Baum entsprechend zu bevorzugen.

Aber warum ist ein Array bei kleinen 'k' besser als eine Baumstruktur? Der Overhead bei Bäumen ist massiv. In deinem Anwendungsfall beträgt der Overhead rein vom Speicher her um die 800% des zu speichernden Werts (ist Systemabhängig).
Dies beginnt sich erst dann zu lohnen, wenn die Kollisionen sehr wahrscheinlich sind und mehr Zahlen gezogen werden müssen.
Die Wahrscheinlichkeit, dass dem Lottobeispiel Kollisionen auftreten, ist recht gering.
Speichern wir also mal den ersten Wert ein einer wahrscheinlich günstigen Stelle: Bei 49 Möglichkeiten und 6 Ziehungen heisst das: Wir speichern die gezogene Zahl am Index ((zahl-1)/9). Damit sind die Zahlen 1-9 am Index 0, 10-18 am Index 1, ..., 46-49 am Index 5. Die Verteilung ist nicht ganz ideal, aber darauf haben wir keinen Einfluss. Bei Kollisionen "sondieren" wir, wir verschieben einfach, bis es passt.

Gehen wir das an einem Beispiel durch:
Erste Zahl ist 15 und somit am Index 1.
Code:
===============================
| 00 | 15 | 00 | 00 | 00 | 00 |
===============================
Die Zweite Zahl ist 16. Diese wäre auch am Index 1. Wir überprüfen, ob dieser Index frei ist, und stellen fest, dass eine kleinere Zahl ungleich 0 schon dort steht. Also schieben wir die 16 in das Feld weiter rechts. Dieses ist ja noch frei.
Code:
===============================
| 00 | 15 | 16 | 00 | 00 | 00 |
===============================
Jetzt ziehen wir die 49, die an Index 5 kommt. Dieser ist noch frei.
Code:
===============================
| 00 | 15 | 16 | 00 | 00 | 49 |
===============================
Jetzt wird wieder die 16 gezogen. Wir zielen wieder auf den Index 1. Dieser ist aber von einer kleineren Zahl (15) besetzt. Also gehen wir nach rechts und schauen, ob dort frei ist. Aber ups: Gab's schon. Also wird eine komplett neue Zahl gezogen...

...Und diese ist 10. Diese sollte an Index 1 stehen. Wir schauen: Es gibt schon eine grössere Zahl. Wir gehen mit der 10 also nach links: Am Index 0 ist noch frei, also sind wir bei
Code:
===============================
| 10 | 15 | 16 | 00 | 00 | 49 |
===============================
Man beachte: Von links nach rechts ist nun alles sortiert (war es bis jetzt immer). Wir ziehen jetzt aber die Zahl 1. Index 0 ist aber schon besetzt, also gehen wir eins nach links. Aber ups: Das geht ja gar nicht. Daher müssen wir den Index modulo nehmen (bzw. immer die Arraygrösse dazuzählen und dann den Modulo mit der Arraygrösse nehmen). Hier also: (6 + (-1)) % 6 = 5. Dort steht schon die 49. Bis jetzt nannte sich dieses Verfahren "Hashen mit Sondieren". Nun weichen wir davon ab, um die Sortiereigenschaften beizubehalten: Wir schieben die 49 nach links und schreiben die 1 an die 5. Stelle. Dadurch haben wir noch immer eine sortierte Folge, auch wenn der kleinste Wert nicht mehr ganz links steht.
Das hat durchaus System: Bei einer solchen Verdrängungsoperation wird jeder Wert solange mit dem vorhergehenden getauscht, bis eine leere Stelle gefunden wird. (Also quasi wie beim Luftbläschen unter der Folie Hervorquetschen). Diese Operation ist mit Abstand die teuerste. Sie kostet O(k) Schreib- und O(k) Lesezugriffe, während einfaches Sondieren nur O(1) Schreib- und O(k) Lesezugriffe erfordert.
Dasselbe gilt übrigens auch ohne wrap-around: Wenn man nach mehrmaligem Sondieren nach rechts auf einen grösseren Wert trifft, der Sondieren nach links verlangt, wird auch der grössere nach rechts verschoben, bis es wieder passt. Umgekehrt natürlich analog.
Somit haben wir jetzt:
Code:
===============================
| 10 | 15 | 16 | 00 | 49 | 01 |
===============================

Der letzte Wert ist glücklicherweise eine 28 und damit gerade an Index 3. Damit gilt:
Code:
===============================
| 10 | 15 | 16 | 28 | 49 | 01 |
===============================

Aber warum ist das jetzt effizienter? Der schlimmste Fall würde ja bedeuten, dass wieder O(k²) Such- und Schreiboperationen ausgeführt werden müssen. Ja. Aber die Wahrscheinlichkeit, dass zwei Werte aus demselben Bereich kommen, ist relativ klein. Daher findet man die Werte auch schneller, als wenn man sie ungeordnet speichert. Schlimmstenfalls ist es nur gleich langsam wie die ungeordnete Speicherung, bestenfalls aber in Omega(1) machbar, was das beste ist, während die ungeordnete Speicherung immer langsamer (Omega(k)) ist.
Bilanz: Wir bleiben bei O(k) Speicherbedarf und bleiben im schlimmsten Falle bei O(k²), der dann eintritt, wenn alle Werte im gleichen index wären, und sind bestenfalls (wenn keine Zahl im gleichen Index ist) bei Omega(1).

Bei deinem sehr spezifischen Anwendungsgebiet ist diese Optimierung zwar besser als der naive Ansatz, aber wenn wir ehrlich sind, kommt es uns bei diesen Grössenordnungen nicht darauf an. Falls du aber einige Milliarden Ziehungen veranstalten würdest, könntest du mit optimierten Datenstrukturen sehr viel Zeit, Strom und Geld sparen.

Ich schätze, ich bin ziemlich abgeschweift, was? Aber irgendwie konnte ich die Stackoverflowlinks auch nicht so nackt stehen lassen :cool:

Gruss
cwriter
 
Zuletzt bearbeitet: