Zufallenzahlen sollen nicht doppelt vorkommen

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

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!

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.

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.

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.

Jester

codetagger schrieb:

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.

Aber irgendjemand muß sich auch Gedanken darüber machen, wie man am allerbesten nicht wiederholende Zufallszahlen zieht und wie man am besten was sortiert und und und... Wie kommst Du drauf, dass das alles weniger "kompiliziert" sei als Softwaredesign und Architektur.

hustbaer

codetagger schrieb:

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.

Ich sehe jetzt keinen grossen Vorteil darin, wenn das Design bzw. die Architektur gut ist, dafür aber die Implementierung Mist.

SideWinder

@codetagger: Man sollte als Informatiker schon in der Lage sein die beste Datenstruktur und den schnellsten Algorithmus für ein gegebenes Problem zu finden bzw. einzusetzen. Das hat noch nichts mit "premature optimization" zu tun. Wenn du dann hergehst und einen in O-Notation optimalen Algorithmus verschnellerst in dem du zwei Zeilen Assembler hier und eine unleserliche Umstellung anderswo verwendest um zwei Ticks in genau deinem Fall und sonst in keinem Fall einzusparen, dann befindest du dich dort. Wenn du aber statt O(n) einfach mal ein O(n^4) hinnimmst und das als "mini" bezeichnest...

MfG SideWinder

Jester schrieb:

codetagger schrieb:

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.

Aber irgendjemand muß sich auch Gedanken darüber machen, wie man am allerbesten nicht wiederholende Zufallszahlen zieht und wie man am besten was sortiert und und und... Wie kommst Du drauf, dass das alles weniger "kompiliziert" sei als Softwaredesign und Architektur.

Weil es sogar hier im Forum Unmengen an Beiträge über das ziehen von solchen Zahlen gibt.

hustbaer schrieb:

codetagger schrieb:

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.

Ich sehe jetzt keinen grossen Vorteil darin, wenn das Design bzw. die Architektur gut ist, dafür aber die Implementierung Mist.

Ne schlechte Implementierung läßt sich bei einer guten Architektur schnell austauschen, aber ne schlechte Architektur austauschen ist viel aufwendiger. Außerdem ist mir noch keiner begegnet, der gute Architektur designt, aber schlecht ziemlich implementiert, aber schon viele die nen schnellen Algo implementieren können, aber keine gute Architektur hinbekommen.

SideWinder schrieb:

@codetagger: Man sollte als Informatiker schon in der Lage sein die beste Datenstruktur und den schnellsten Algorithmus für ein gegebenes Problem zu finden bzw. einzusetzen. Das hat noch nichts mit "premature optimization" zu tun. Wenn du dann hergehst und einen in O-Notation optimalen Algorithmus verschnellerst in dem du zwei Zeilen Assembler hier und eine unleserliche Umstellung anderswo verwendest um zwei Ticks in genau deinem Fall und sonst in keinem Fall einzusparen, dann befindest du dich dort. Wenn du aber statt O(n) einfach mal ein O(n^4) hinnimmst und das als "mini" bezeichnest...

Ja, ja, ganz billiger Versuch mir die Worte im Mund umzudrehen oder bist wirklich so dumm den Zusammenhang zu verstehen. Ich habe dieses Lottospiel als "mini" bezeichnet, O(n^4) hast du gerade hergezaubert. Premature Optimization ist das Optimieren von Programmteilen die keinen messbaren Unterschied bringen. Und irgendwas mit Assembler besser an eine Hardware anzupassen, muss auch nicht immer Premature Optimization sein, wenn man es zum richtigen Zeitpunkt an der richtigen Stelle macht.

EXDW

hustbaer schrieb:

David W schrieb:

Wieso wird über die Laufzeit geredet?

Weil hier Informatiker/Programmierer verkehren?

Und? Die Laufzeit und Komplexität ist für die Aufgabenstellung völlig irrelevant.
-> Fällt schon unter YAGNI. Über die Aspekte der Laufzeit kann geredet werden sofern es erforderlich ist.

Und nur weil es Langsamer ist als anderer Code den man ausgearbeitet hat heißt das noch lange nicht das es Schrecklicher Code ist.

Die Aufgabenstellung besagte ja "Lottozahlen Ziehen", das kann man schon einmal sauber aufziehen mit ersten Focus auf Sauberkeit und Funktionalität. Wenn dann gemerkt wird das es von der Performance her nicht aus reicht, also nachgewiesen mit einem Profiler, kann man dieses Modul (Klasse oder Methode) neu implementieren und in der eigentlichen Applikation austauschen.

List<int> lottoNumbers = GetLottoNumbers();

public List<int> GetLottoNumbers()
{
    List<int> numbers = new List<int>();
    for (int i = 1; i < 49; ++i)
        numbers.Add(i);
    numbers .OrderBy(a => Guid.NewGuid());
    return numbers.GetRange(0, 6);
}

Kurz, knapp, funktioniert.

Walli

SideWinder schrieb:

Wenn du aber statt O(n) einfach mal ein O(n^4) hinnimmst und das als "mini" bezeichnest...

Ergänzend und mal ganz vom konkreten Problem hier losgelöst: Bei begrenztem n kann es durchaus Sinn machen den asymptotisch langsameren Algorithmus herzunehmen. Wer einfach nur blind die asymptotischen Laufzeitkomplexitäten vergleicht, der hat die O-Notation nicht verstanden. Ich sehe leider viel zu oft die Pauschalaussage, dass O(n) besser als O(n^2) ist.

David W schrieb:

Über die Aspekte der Laufzeit kann geredet werden sofern es erforderlich ist.

Nachdenken kann nie schaden, besonders bei Übungsaufgaben.

EXDW

Walli schrieb:

Nachdenken kann nie schaden, besonders bei Übungsaufgaben.

Korrekt, und zwar wie man es sauber auf zieht das andere es auch verstehen und Maintainen können, das ist viel wichtiger als Optimierungen die in den Mikro bereich fallen.

Jester

Mit der Aufgabe hat sich hier im Prinzip ja kaum einer beschäftigt. Es gibt nämlich zwei Lager, die einen Sagen das ist ja total einfach, lass uns ne möglichst simple Lösung machen die für 6 Zahlen aus 49 funktioniert. Die meisten haben aber sofort gesagt, okay wir haben N Zahlen und wir wollen K stück ziehen, ohne doppelte und haben sich auf dieses neue Problem gestürzt, weil es interessanter ist -- zumindest für viele Informatiker.

Und hier kommt es zu sehr interessanten Effekten, während Du mir verkaufst, dass eine Laufzeit von O(N) toll sei mit dem random shuffle und mir dafür sogar noch eine Implementierung mit O(N log N) Laufzeit verkaufst (und O(N) Speicher) und behauptest man müsse sich nun auf die Architektur konzentrieren, denken sich andere dass das ja doof wäre, weil N viel viel größer sein könnte als K und überlegen, wie sie das N aus der Laufzeit rauskriegen, fokussieren also eher auf algorithmische Aspekte und stellen fest, dass auch O(K log K) geht.

Es war eine simple Übungsaufgabe, es ist weder Architektur und Wartbarkeit noch eine theoretische Überlegung für N Zahlen ohne Wiederholung aus K gefragt. Wir verallgemeinern die Übungsaufgabe also in unterschiedliche Richtungen. Nur Du scheinst als einziger genau zu wissen, dass das eine Quatsch ist und das andere total wichtig. Warum? -- Mir scheint nur aus Gewohnheit; willkommen am Tellerrand! Wallis Einwand gilt hier nicht so wirklich, weil die Konstanten der Algorithmen vernachlässigbar klein sein dürften so dass der theoretisch bessere hier auch ziemlich bald der praktisch bessere ist.