arc4random Aufeinanderfolgende

Alex · 24. Februar 2013, 16:05

Bei 5 Möglichkeiten sehe ich keine all zu viele Alternativen wenn sich die Zahl nicht wiederholen darf. Selbst wenn ich die Zahlen Strecke, können sie gleich sein. Also entweder in eine Array schreiben und dann da raus nehmen oder eben Schleife.

Michael · 24. Februar 2013, 16:14

Alex schrieb:

Bei 5 Möglichkeiten sehe ich keine all zu viele Alternativen wenn sich die Zahl nicht wiederholen darf.

Das Threadersteller hat nichts dagegen, dass sich Zahlen wiederholen. Sie sollen nur nicht direkt aufeinander folgen.

Michael

beage · 24. Februar 2013, 16:37

gritsch schrieb:

macmoonshine schrieb:

beage schrieb:

Ich würde in einer while checken, ob die aktuelle Zahl gleich die letzte ist und das so lange machen, bis es nicht mehr so ist.

Dann kann jedoch die aktuelle Zahl gleich der vorletzten sein. Das Vorgehen von Alex ist nicht nur richtig sondern in der Regel auch effizienter...

genau das meinte ich. also jede zweite zahl kann gleich sein.

Der TO will aber nur, dass die gerade gezogene nicht gleich der letzten ist. Natürlich wäre das kein Lottogenerator, das ist richtig.

Ansonsten würde ich alle gezogenen in ein Array schmeissen und dann bei jeder Ziehung das Array checken.

gritsch · 24. Februar 2013, 17:49

beage schrieb:

gritsch schrieb:

macmoonshine schrieb:

beage schrieb:

Ich würde in einer while checken, ob die aktuelle Zahl gleich die letzte ist und das so lange machen, bis es nicht mehr so ist.

Dann kann jedoch die aktuelle Zahl gleich der vorletzten sein. Das Vorgehen von Alex ist nicht nur richtig sondern in der Regel auch effizienter...

genau das meinte ich. also jede zweite zahl kann gleich sein.

Der TO will aber nur, dass die gerade gezogene nicht gleich der letzten ist. Natürlich wäre das kein Lottogenerator, das ist richtig.

Ansonsten würde ich alle gezogenen in ein Array schmeissen und dann bei jeder Ziehung das Array checken.

warum alle gezogenen in ein array werfen und wieder eine schleife bis ins ungewisse laufen lassen?

besser ist dann doch alle möglichen zahlen in ein array zu stecken und dann genau so oft den generator aufzurufen wie du zahlen benötigst (den gezogenen index entfernst du nach jedem durchlauf)

Thallius · 24. Februar 2013, 17:54

gritsch schrieb:

beage schrieb:

gritsch schrieb:

macmoonshine schrieb:

beage schrieb:

Ich würde in einer while checken, ob die aktuelle Zahl gleich die letzte ist und das so lange machen, bis es nicht mehr so ist.

Dann kann jedoch die aktuelle Zahl gleich der vorletzten sein. Das Vorgehen von Alex ist nicht nur richtig sondern in der Regel auch effizienter...

genau das meinte ich. also jede zweite zahl kann gleich sein.

Der TO will aber nur, dass die gerade gezogene nicht gleich der letzten ist. Natürlich wäre das kein Lottogenerator, das ist richtig.

Ansonsten würde ich alle gezogenen in ein Array schmeissen und dann bei jeder Ziehung das Array checken.

warum alle gezogenen in ein array werfen und wieder eine schleife bis ins ungewisse laufen lassen?

besser ist dann doch alle möglichen zahlen in ein array zu stecken und dann genau so oft den generator aufzurufen wie du zahlen benötigst (den gezogenen index entfernst du nach jedem durchlauf)

Nachdem moderne Array ja eigentlich keine Array mehr snd sondern Listen ist das natürlich schlauer. Wir haben damals das Lotto Problem in der Schule auch mit einem Array gelöst. Allerdings mit einem C-Array. Da müßte man jedesmal alle Inhalte neu kopieren. Also war es einfacher den Inhalt auf 0 zu setzen und in einer Schleife zu ziehen bis man einen Index findet dessen Inhalt nicht 0 ist.

Gruß

Claus

gritsch · 24. Februar 2013, 17:58

Thallius schrieb:

gritsch schrieb:

beage schrieb:

gritsch schrieb:

macmoonshine schrieb:

beage schrieb:

Ich würde in einer while checken, ob die aktuelle Zahl gleich die letzte ist und das so lange machen, bis es nicht mehr so ist.

Dann kann jedoch die aktuelle Zahl gleich der vorletzten sein. Das Vorgehen von Alex ist nicht nur richtig sondern in der Regel auch effizienter...

genau das meinte ich. also jede zweite zahl kann gleich sein.

Der TO will aber nur, dass die gerade gezogene nicht gleich der letzten ist. Natürlich wäre das kein Lottogenerator, das ist richtig.

Ansonsten würde ich alle gezogenen in ein Array schmeissen und dann bei jeder Ziehung das Array checken.

warum alle gezogenen in ein array werfen und wieder eine schleife bis ins ungewisse laufen lassen?

besser ist dann doch alle möglichen zahlen in ein array zu stecken und dann genau so oft den generator aufzurufen wie du zahlen benötigst (den gezogenen index entfernst du nach jedem durchlauf)

Nachdem moderne Array ja eigentlich keine Array mehr snd sondern Listen ist das natürlich schlauer. Wir haben damals das Lotto Problem in der Schule auch mit einem Array gelöst. Allerdings mit einem C-Array. Da müßte man jedesmal alle Inhalte neu kopieren. Also war es einfacher den Inhalt auf 0 zu setzen und in einer Schleife zu ziehen bis man einen Index findet dessen Inhalt nicht 0 ist.

Gruß

Claus

warum ALLE inhalte? betrifft doch nur die HINTER dem gezogenen index

Thallius · 24. Februar 2013, 18:02

gritsch schrieb:

Thallius schrieb:

gritsch schrieb:

beage schrieb:

gritsch schrieb:

macmoonshine schrieb:

beage schrieb:

Ich würde in einer while checken, ob die aktuelle Zahl gleich die letzte ist und das so lange machen, bis es nicht mehr so ist.

Dann kann jedoch die aktuelle Zahl gleich der vorletzten sein. Das Vorgehen von Alex ist nicht nur richtig sondern in der Regel auch effizienter...

genau das meinte ich. also jede zweite zahl kann gleich sein.

Der TO will aber nur, dass die gerade gezogene nicht gleich der letzten ist. Natürlich wäre das kein Lottogenerator, das ist richtig.

Ansonsten würde ich alle gezogenen in ein Array schmeissen und dann bei jeder Ziehung das Array checken.

warum alle gezogenen in ein array werfen und wieder eine schleife bis ins ungewisse laufen lassen?

besser ist dann doch alle möglichen zahlen in ein array zu stecken und dann genau so oft den generator aufzurufen wie du zahlen benötigst (den gezogenen index entfernst du nach jedem durchlauf)

Nachdem moderne Array ja eigentlich keine Array mehr snd sondern Listen ist das natürlich schlauer. Wir haben damals das Lotto Problem in der Schule auch mit einem Array gelöst. Allerdings mit einem C-Array. Da müßte man jedesmal alle Inhalte neu kopieren. Also war es einfacher den Inhalt auf 0 zu setzen und in einer Schleife zu ziehen bis man einen Index findet dessen Inhalt nicht 0 ist.

Gruß

Claus

warum ALLE inhalte? betrifft doch nur die HINTER dem gezogenen index

Ja, aber laut Murphy gibt der Zufall dann 1,1,1,1,1,1 aus

Gruß

Claus

gritsch · 24. Februar 2013, 18:03

Thallius schrieb:

gritsch schrieb:

Thallius schrieb:

gritsch schrieb:

beage schrieb:

gritsch schrieb:

macmoonshine schrieb:

beage schrieb:

Ich würde in einer while checken, ob die aktuelle Zahl gleich die letzte ist und das so lange machen, bis es nicht mehr so ist.

Dann kann jedoch die aktuelle Zahl gleich der vorletzten sein. Das Vorgehen von Alex ist nicht nur richtig sondern in der Regel auch effizienter...

genau das meinte ich. also jede zweite zahl kann gleich sein.

Der TO will aber nur, dass die gerade gezogene nicht gleich der letzten ist. Natürlich wäre das kein Lottogenerator, das ist richtig.

Ansonsten würde ich alle gezogenen in ein Array schmeissen und dann bei jeder Ziehung das Array checken.

warum alle gezogenen in ein array werfen und wieder eine schleife bis ins ungewisse laufen lassen?

besser ist dann doch alle möglichen zahlen in ein array zu stecken und dann genau so oft den generator aufzurufen wie du zahlen benötigst (den gezogenen index entfernst du nach jedem durchlauf)

Nachdem moderne Array ja eigentlich keine Array mehr snd sondern Listen ist das natürlich schlauer. Wir haben damals das Lotto Problem in der Schule auch mit einem Array gelöst. Allerdings mit einem C-Array. Da müßte man jedesmal alle Inhalte neu kopieren. Also war es einfacher den Inhalt auf 0 zu setzen und in einer Schleife zu ziehen bis man einen Index findet dessen Inhalt nicht 0 ist.

Gruß

Claus

warum ALLE inhalte? betrifft doch nur die HINTER dem gezogenen index

Ja, aber laut Murphy gibt der Zufall dann 1,1,1,1,1,1 aus

Gruß

Claus

naja, bisschen speicher verschieben ist doch kein ding

Amin Negm-Awad · 24. Februar 2013, 19:17

mattik schrieb:

Dass Lottozahlen und das TO komplett unterschiedliche Probleme sind ist mittlerweile klar.

Unabhängig davon ist es _immer_ falsch, ein Schleifenende ausschießlich von einer Zufallszahl abhängig zu machen (was in dem Fall von "hole eine neue Zufallszahl, bis sie bestimmte Kriterien entspricht" der Fall wäre). Der Grund ist eher theoretisch: Es lässt sich nicht mehr nachweisen, dass die Schleife überhaupt beendet wird. Ein echter Zufallszahlengenerator kann beliebig lange Sequenzen von ein und derselben Zahl erzeugen - die Wahrscheinlichkeit dafür geht gegen null, aber es ist nicht ausgeschlossen. EIn Programm, das für ein nachweislich entscheidbares Problem nicht nachweislich terminiert ist keine Lösung für das Problem.

Jaja, Klugscheißerei, ich weiß. Das ist zwar ein sehr theoretisches Argument und solche unendlich langen Sequenzen kommen in der Praxis meistens nicht vor, andererseits entstehen viele Fehler in Software dadurch, dass irgendjemand irgendwann mal angenommen hat, dass ein bestimmter Fall in der Praxis nicht vorkommt.

Die Wahrscheinlichkeit, dass der Nachweis der garantierten Terminierung einen Fehler enthält, ist bedeutsam größer.

mattik · 24. Februar 2013, 21:03

Amin Negm-Awad schrieb:

mattik schrieb:

Dass Lottozahlen und das TO komplett unterschiedliche Probleme sind ist mittlerweile klar.

Unabhängig davon ist es _immer_ falsch, ein Schleifenende ausschießlich von einer Zufallszahl abhängig zu machen (was in dem Fall von "hole eine neue Zufallszahl, bis sie bestimmte Kriterien entspricht" der Fall wäre). Der Grund ist eher theoretisch: Es lässt sich nicht mehr nachweisen, dass die Schleife überhaupt beendet wird. Ein echter Zufallszahlengenerator kann beliebig lange Sequenzen von ein und derselben Zahl erzeugen - die Wahrscheinlichkeit dafür geht gegen null, aber es ist nicht ausgeschlossen. EIn Programm, das für ein nachweislich entscheidbares Problem nicht nachweislich terminiert ist keine Lösung für das Problem.

Jaja, Klugscheißerei, ich weiß. Das ist zwar ein sehr theoretisches Argument und solche unendlich langen Sequenzen kommen in der Praxis meistens nicht vor, andererseits entstehen viele Fehler in Software dadurch, dass irgendjemand irgendwann mal angenommen hat, dass ein bestimmter Fall in der Praxis nicht vorkommt.

Die Wahrscheinlichkeit, dass der Nachweis der garantierten Terminierung einen Fehler enthält, ist bedeutsam größer.

Man sollte halt wissen, was man tut - wie eigentlich überall. Nur weil ein Terminierungsbeweis manchmal nicht ganz einfach ist, heißt das ja nicht, dass solche Gedanken grundsätzlich sinnlos wären. Hier ist es jedoch einfach: Beim Ansatz mit der Schleife lässt sich (zumindest mit einem idealen Zufallszahlengenerator) die Nichtterminierung leicht indirekt beweisen: Für jede Laufzeitschranke gibt es eine Zufallszahlensequenz mit p>0, für die das Programm nicht terminiert. Beim Ansatz ohne Schleife ist der Terminierungsbeweis trivial (LOOP-berechenbar). Also ist (Korrektheit der beiden Ansätze angenommen) der Schleifenansatz partiell korrekt, der andere total korrekt.

Mit dem Verhalten arc4random könnte man zwar die totale Korrektheit des Schleifenansatzes zeigen, allerdings bringt dir eine obere Schranke von rund 2^1700 Durchläufen in der realen Welt nicht viel.

Und gerade weil solche Beweise kompliziert sein können, ist es ja nicht dumm, einen Ansatz zu wählen, bei dem es nicht so ist. Kurz: Warum eine Schleife verwenden, wenn sie nicht nötig ist?

Amin Negm-Awad · 24. Februar 2013, 21:19

Kannst du mir die Richtigkeit deiner Antwort beweisen?

Der Ansatz mit einer Schleife ist etwa 398239823 Mal intuitiver und leichter zu lesen. Die Wahrscheinlichkeit, dass das jemand später falsch verbaut, ist da bei deinem Ansatz 9234798234987 Mal größer als das Problem, dass eine praktisch existierende Laufzeitschranke, die überhaupt nicht genannt ist, überschritten wird.

Übrigens interessiert mich die Wahrscheinlichkeit für das Überschreiten einer Laufzeitschranke nicht im geringsten, wenn sie Größenordnungen kleiner ist als die Wahrscheinlichkeit eines kippenden Bits im RAM oder einer Kernel-Panic.

mattik · 24. Februar 2013, 23:32

Amin Negm-Awad schrieb:

Kannst du mir die Richtigkeit deiner Antwort beweisen?

Habe ich - die Beweislinien stehen da, der Rest sind allgemeine Grundlagen der Theoretischen Informatik.

Lesbarkeit hängt stark von den Fähigkeiten des Schreibers und des Lesers ab. Für mich sind beide Ansätze gleich gut lesbar.

Wenn zwei Algorithmen zur Auswahl stehen - einer mit einem kleinen Problem, der andere ohne - würde ich den ohne das Problem nehmen. So riesig ist der Unterschied der Komplexität ja nicht, aber den Ansatz ohne Schleife halte ich für prinzipiell noch einfacher.

Die Möglichkeit kippender Bits oder Kernel Panics ist niemals eine Entschuldigung für schlechten Code.

beage · 24. Februar 2013, 23:51

In PHP würd ich das auf die Schnelle so machen. Keine Doppelten und sortierte Ausgabe

PHP-Quellcode

<?php
$zahlen = array();
for($i = 0; $i<6; $i++){
do {
$zufallszahl = rand(1,49);
} while(in_array($zufallszahl, $zahlen));
$zahlen[$i] = $zufallszahl;
}
sort($zahlen);
foreach($zahlen as $ausgabe)
echo $ausgabe." ";
?>

Alles anzeigen

mattik · 25. Februar 2013, 00:42

Warum bloß PHP?

Mein Gegenvorschlag - genau so lang und die blöde innere Schleife ist weg:

PHP-Quellcode

<?php
$lostrommel = range(1,49);
$zahlen = array();
for($i = 0; $i<6; $i++){
$wahl = rand(0,count($lostrommel)-1);
$zahlen[$i] = $lostrommel[$wahl];
array_splice($lostrommel, $wahl, 1);
}
sort($zahlen);
foreach($zahlen as $ausgabe)
echo $ausgabe." ";
?>

Alles anzeigen

Alex · 25. Februar 2013, 05:43

Um auf einen gemeinsamen Nenner zu kommen, würde ich vorschlagen, man nimmt aus der Array die eben gezogene Zahl raus, fügt die vorher entferne Zahl zu und wiederholt dies nach der nächsten Ziehung. So gibt es keine theoretisch unendliche Schleifen und die letzte gezogene Zahl ist nie ident mit der aktuell gezogenen Zahl. Die Array enthält demnach bei der ersten Ziehung alle Zahlen - danach immer eine weniger.

Alex · 25. Februar 2013, 06:10

Hier ein Beispiel so wie ich es mir vorgestellt hätte (vor dem 1. Kaffe - und diesmal wirklich

)

Quellcode

NSMutableArray *zahlenArray = [NSMutableArray arrayWithArray:[NSArray arrayWithObjects:@"1",@"2",@"3",@"4",@"5", nil]];
NSString * letzteZahl = @"";
NSString * aktuelleZahl = @"";
NSMutableArray * gezogeneZahlen = [NSMutableArray arrayWithCapacity:6];
for (int a = 0; a<20; a++)
{
NSLog(@"Durchlauf start\n=================\nLETZTE ZAHL: %@", letzteZahl);
bool lastflag = false;
if ([gezogeneZahlen count]) lastflag = true;
int randomnumber = (arc4random()%[zahlenArray count]);
aktuelleZahl = [zahlenArray objectAtIndex:randomnumber];
[gezogeneZahlen addObject:[zahlenArray objectAtIndex:randomnumber]];
[zahlenArray removeObjectAtIndex:randomnumber];
if (lastflag) [zahlenArray addObject:letzteZahl];
letzteZahl = aktuelleZahl;
NSLog(@"Gezogene Zahl: %@", aktuelleZahl);
}
NSLog(@"Alle Zahlen: %@", gezogeneZahlen);

Alles anzeigen

Achso - hier wird die "letzte" Zahl immer ans Ende der array geschoben. Also ist das vielleicht "suboptimal" - vielleicht aber auch irrelevant. Bin mir gerade nicht sicher.

//EDIT: sizeof und count sind natürlich nicht dasselbe. Fehler korrigiert

Alex · 25. Februar 2013, 06:18

Und noch ein Nachtrag: Will man nun die "Lottozahlen", lässt man einfach das erneute Hinzufügen zur Zahlenarray weg. Dabei muss man jedoch beachten dass immer genug Zahlen da sind um gezogen zu werden. Sprich: 5 Zahlen aber 6 Durchläufe ergibt nen Error

Quellcode

NSMutableArray *zahlenArray = [NSMutableArray arrayWithArray:[NSArray arrayWithObjects:@"1",@"2",@"3",@"4",@"5", nil]];
NSString * letzteZahl = @"";
NSString * aktuelleZahl = @"";
NSMutableArray * gezogeneZahlen = [NSMutableArray arrayWithCapacity:6];
for (int a = 0; a<5; a++)
{
bool lastflag = false;
if ([gezogeneZahlen count]) lastflag = true;
int randomnumber = (arc4random()%[zahlenArray count]);
aktuelleZahl = [zahlenArray objectAtIndex:randomnumber];
[gezogeneZahlen addObject:[zahlenArray objectAtIndex:randomnumber]];
[zahlenArray removeObjectAtIndex:randomnumber];
//if (lastflag) [zahlenArray addObject:letzteZahl];
letzteZahl = aktuelleZahl;
}
NSLog(@"Alle Zahlen: %@", gezogeneZahlen);

Alles anzeigen

Ergibt dann zb.
4, 1, 2, 3, 5

Amin Negm-Awad · 25. Februar 2013, 07:43

mattik schrieb:

Amin Negm-Awad schrieb:

Kannst du mir die Richtigkeit deiner Antwort beweisen?

Habe ich - die Beweislinien stehen da, der Rest sind allgemeine Grundlagen der Theoretischen Informatik.

Lesbarkeit hängt stark von den Fähigkeiten des Schreibers und des Lesers ab. Für mich sind beide Ansätze gleich gut lesbar.

Wenn zwei Algorithmen zur Auswahl stehen - einer mit einem kleinen Problem, der andere ohne - würde ich den ohne das Problem nehmen. So riesig ist der Unterschied der Komplexität ja nicht, aber den Ansatz ohne Schleife halte ich für prinzipiell noch einfacher.

Die Möglichkeit kippender Bits oder Kernel Panics ist niemals eine Entschuldigung für schlechten Code.

Nein, du hast nicht die Richtigkeit deiner Antwort bewiesen. Deine Antwort enthält die Beweislinie. Diese kann wiederum fehlerhaft sein. Deshalb müsste die Richtigkeit deiner in deiner Antwort enthaltenen Beweislinie wiederum bewiesen werden. Übrigens geht es viel einfacher und ohne theoretische Informatik: Die Problematik ist sofort erkennbar, bloß eben hinreichend unbedeutend. Ich bin mir sicher, dass sich Michael des Problemes bewusst war. Er hat es nur als unwichtig ausgeblendet.

Es sind auch offenkundig beide Ansätze nicht gleich gut verständlich. Man kann sich das ganz einfach mit einer Parallelwertung in der Besoffenensphäre klar machen: Wenn es in einem Trinkspiel – warum auch immer – verboten wäre, zweimal dieselbe Zahl zu würfeln, würde jeder Teilnehmer ohne weiteres Nachdenken es auch noch bei 2,3 %0 hinbekommen, einfach noch einmal zu würfeln, wenn sich ein Wurf wiederholt hat. Die Richtigkeit deines Ansatzes (im Prinzip Reduktion der Ergebnismenge auf N-1 und Verschiebung auf die freien Würfe) verstehen die meisten Menschen nicht einmal nüchtern. "Dein" Ansatz ist deutlich unnatürlicher und unintuitiver.

Der code von Michael ist auch nicht schlecht. /Du/ hast damit argumentiert, dass es für jede Laufzeitschranke ein p > 0 gibt, welches die Schanke verletzt. /Du/ hast dabei aber verschwiegen, dass diese Problem nur theoretisch existiert, weil diese Laufzeitschranke zum einen im OP nicht existiert, zum anderen generell in der Praxis nicht existiert, weil p hinreichend klein ist. /Du/ hast damit verschwiegen, dass in jedem Code p leicht überschritten werden kann aufgrund anderer Umstände. /Du/ hast diese anderen Umstände einfach ausgeblendet. Das ist ein generelles Problem des Richtigkeitsbeweises: Er ist fast immer partiell, weil er einfach die Hälfte der Wahrheit verschweigt, um dann zu sagen, dass alles richtig sei. Das ist meist auch unwichtig, weil immerhin der bewiesene Teil richtig ist, auf den es mir ankommt. Wenn aber mit einer vernachlässigbaren Wahrscheinlichkeit argumentiert wird, dann spielt das doch wieder eine Rolle. Oder kurz formuliert: Der theoretische Hinweis auf ein sehr, sehr unwahrscheinliches Problem ist dann völlig unsinnig, überflüssig, nutzlos, wenn es ganz viele nicht berücksichtigte Probleme gibt, die eine viel höhere Wahrscheinlichkeit aufweisen.

Wenn du also die Richtigkeit beweisen möchtest, dann mache es bitte so, dass du auch alle Fehlerquellen mit gleicher Wahrscheinlichkeit einbeziehst Sonst ist der Beweis nämlich in einem realen Stück Code für die Tonne.

Nicht, dass am Ende noch Menschen keine UUID mehr benutzen, weil man deren Kollisionsfreiheit nicht beweisen kann.

zerm · 25. Februar 2013, 08:40

Heh, dank Amin braucht man die theoretische Informatik nicht mehr, weils ohnehin unwichtig ist. Ich nehm manchmal auch lieber Bubblesort, weils viel einfacher verständlich ist und überhaupt, soviel sortiere ich nie, dass das ein Unterschied machen würde. Oder? Oder? Und was sagen diese ganzen Beweise überhaupt aus? Nichts, genau!

Alex · 25. Februar 2013, 08:52

Bin ich der einzige der sich fragt worum es hier eigentlich geht ?

PHP-Quellcode

PHP-Quellcode

Quellcode

Quellcode

Tags