Irgendwie scheint mein Hirn eingerostet zu sein (oder ich bin einfach nur zu doof, egal ob geworden oder immer gewesen). Ich habe ein mathematisches / algorithmisches Problem von dem ich nicht dachte dass ich ein Problem hätte. Ich benötige eine 10-stellige Ziffernreihenfolge, in der jede Ziffer nur einmal vorkommen darf. Zuerst dachte ich, ich nehm programmiere ein rückgekoppeltes Schieberegister (LFSR), aber das war dann nichts, weil mir das Teil (warum auch immer) einfach nur 10 verschiedene Kombinationen ausspuckt. Natürlich geht auch die Brut-Force Methode wenn ich ein 32-Bit Schieberegister nehme und so lange würfel, bis jede Ziffer genau einmal dran gekommen war. Ich könnte auch eine Ziffer generieren lassen und falls die schon mal da war, die nächst höhere nehmen, wenn die da war wieder die nächst höhere usw. und so fort. Aber irgendwie ist das absolut unelegant und widerstrebt mir daher. Wo ist der Knoten in meinem Hirn (okay, ich bin krank geschrieben und nicht so sehr fit, aber das ist keine Entschuldigung). Ich verrenke mir noch mal den Kopf über das Schieberegister, vllt. hilft mir hier jemand auf die Sprünge
Ich glaube dir fehlt einfach ein passender Suchbegriff. Du willst eine zufällige Permutation von [0,1,2,3,4,5,6,7,8,9] erzeugen. https://de.wikipedia.org/wiki/Zuf%C3%A4llige_Permutation#Fisher-Yates-Verfahren
nimm ein Array mit deinen 10 Ziffern. Dann tauscht du in einer Schleife diese Ziffern zufällig untereinander array[i]=array[rand()%(10-i)] oder so Dann stehen im Array die Ziffern in zufälliger Reihenfolge.
:
Bearbeitet durch User
Ich würde das mit einem Zufallszahlengenerator und indirekt angehen. Zwei Arrays mit jeweils 10 Elementen anlegen. Array 1 wird mit den Ziffern 0 bis 9 gefüllt. Der Zufallszahlengenerator wählt nun ein Element über den Arrayindex (0..9) aus. Die Ziffer des gewählten Arrayeintrags wird in Array 2 kopiert, und in Array 1 gelöscht indem alle nachfolgenden Einträge nach unten geschoben werden. Jetzt wählt der Generator das nächste Element, der Index geht nun noch von 0..8. So lange bis Array 1 leer und Array 2 voll ist.
Da du nur Ziffern (0..9) suchst, warum erzeugst du nicht einfach eine zufällige Permutation von 0123456789? Algorithmen dafür gibt's: https://en.wikipedia.org/wiki/Random_permutation
Jemand schrieb: > Ich glaube dir fehlt einfach ein passender Suchbegriff. > Du willst eine zufällige Permutation von [0,1,2,3,4,5,6,7,8,9] erzeugen. > https://de.wikipedia.org/wiki/Zuf%C3%A4llige_Permutation#Fisher-Yates-Verfahren da lese ich gerade. Obelix schrieb: > Zwei Arrays mit jeweils 10 Elementen anlegen. Array 1 wird mit den > Ziffern 0 bis 9 gefüllt. Der Zufallszahlengenerator wählt nun ein > Element über den Arrayindex (0..9) aus. Die Ziffer des gewählten > Arrayeintrags wird in Array 2 kopiert, und in Array 1 gelöscht indem > alle nachfolgenden Einträge nach unten geschoben werden. Jetzt wählt der > Generator das nächste Element, der Index geht nun noch von 0..8. So > lange bis Array 1 leer und Array 2 voll ist. das habe ich ja bereits gemacht, aber irgendwie ist das schon sehr "brachial"
Da war schon jemand schneller :) Das Problem mit Algorithmen die sukzessive auswählen ist etwas subtil. Meistens ist die Dichtefunktion der Ergebnisse nach dem Modulo nicht mehr perfekt uniform. Also beispielsweise wenn ein PRNG immer ein Byte 0..255 liefert, ergeben sich unterschiedliche Wahrscheinlichkeiten für die Ergebnisse -nach- Modulo rand() % 9,8,7, ... usw.
Ralph S. schrieb: > das habe ich ja bereits gemacht, aber irgendwie ist das schon sehr > "brachial" Nein deine "Zufallszahl" ist hat wie als PIN 4 mal die Null, aber die Reihenfolge ist geheim.
Ralph S. schrieb: > Zuerst dachte ich, ich nehm programmiere ein rückgekoppeltes > Schieberegister (LFSR), aber das war dann nichts, weil mir das Teil > (warum auch immer) einfach nur 10 verschiedene Kombinationen ausspuckt. Entweder hattest du einen Programmierfehler, oder deine Abgriffe lagen falsch. Beitrag "Re: Schnelle (Pseudo-)Zufallszahlen"
Jemand schrieb: > Ich glaube dir fehlt einfach ein passender Suchbegriff. > Du willst eine zufällige Permutation von [0,1,2,3,4,5,6,7,8,9] erzeugen. Das war der entscheidende Hinweis, ganz vielen Dank dafür. Gelöst habe ich das jetzt so (die Funktion "random16" benötige ich noch anderweitig im Programm):
1 | /* ------------------------------------------------------- |
2 | swap8 |
3 | |
4 | tauscht 2 8-Bit Integerwerte |
5 | ------------------------------------------------------- */ |
6 | void swap8(uint8_t *a, uint8_t *b) |
7 | { |
8 | uint8_t tmp; |
9 | |
10 | tmp= *a; |
11 | *a= *b; |
12 | *b= tmp; |
13 | } |
14 | |
15 | /* -------------------------------------------------------- |
16 | random16 |
17 | |
18 | generiert eine 16-Bit grosse Pseudozufallszahl die |
19 | mittels mitgekoppeltem Schieberegister erreicht wird |
20 | |
21 | Uebergabe: |
22 | startwert : Ausgangspunkt im Zahlenbereich |
23 | |
24 | rndm_mask ist die XOR-Maske beim Mitkoppeln des |
25 | Schieberegisters |
26 | |
27 | XOR-Maske nach Anzahl unterschiedlichen |
28 | dem Schieben Zahlen im Ergebnis |
29 | ------------------------------------------- |
30 | 0xb400 65535 |
31 | 0x07c1 2047 |
32 | 0x0be0 4095 |
33 | -------------------------------------------------------- */ |
34 | uint16_t random16(uint16_t startwert) |
35 | { |
36 | // Variable MUESSEN static sein, damit das Schieberegister |
37 | // mit jedem Tick von der vorherigen Position aus weiter |
38 | // schiebt |
39 | static uint16_t start_state= 1; |
40 | static uint16_t lfsr= 1; |
41 | static char first = 0; |
42 | uint16_t lsb; |
43 | |
44 | if (first== 0) |
45 | { |
46 | first= 1; |
47 | start_state= startwert; |
48 | lfsr= start_state; |
49 | } |
50 | lsb = lfsr & 1; // niederwertigstes Bit des Schieberegisters |
51 | lfsr = lfsr >> 1; // das Schieberegister, eine Stelle nach rechts |
52 | if (lsb) { lfsr ^= 0xb400; } // wenn LSB gesetzt, XOR-Togglemaske auf SR anwenden |
53 | return lfsr; |
54 | } |
55 | |
56 | /* ------------------------------------------------------- |
57 | rndm_permut10 |
58 | |
59 | zufaellige Permutation von 10 Ziffern nach |
60 | Fisher-Yates |
61 | |
62 | Uebergabe: |
63 | *buf : Zeiger auf 10 Byte grosses Array |
64 | ------------------------------------------------------- */ |
65 | void rndm_permut10(uint8_t *buf, uint8_t startw) |
66 | { |
67 | int8_t i,z; |
68 | uint8_t *ptr; |
69 | |
70 | for (i= 0; i< 10; i++) |
71 | { |
72 | *(buf+i) = i; |
73 | } |
74 | for (i= 9; i> -1; i--) |
75 | { |
76 | z= (random16(startw) % 10); |
77 | swap8(&(*(buf+i)), &(*(buf+z))); |
78 | } |
79 | } |
80 | . |
81 | . |
82 | . |
83 | int i,a; |
84 | uint16_t zstw; |
85 | |
86 | zstw= time(0); // Zufallszahlenstartwert |
87 | for (i= 0; i< 10; i++) |
88 | { |
89 | rndm_permut10(&symzif[0], zstw); |
90 | printf("\n\r"); |
91 | for (a= 0; a< 10; a++) printf("%d ", symzif[a]); |
92 | } |
Vielleicht hat das jemand kürzer und knackiger ?!? In dem Falle würde ich das dann gerne übernehmen. Vielen Dank noch mal an "Jemand"
x^y schrieb: > Da war schon jemand schneller :) > > Das Problem mit Algorithmen die sukzessive auswählen ist etwas subtil. > Meistens ist die Dichtefunktion der Ergebnisse nach dem Modulo nicht > mehr perfekt uniform. Also beispielsweise wenn ein PRNG immer ein Byte > 0..255 liefert, ergeben sich unterschiedliche Wahrscheinlichkeiten für > die Ergebnisse -nach- Modulo rand() % 9,8,7, ... usw. Dann ist der PRNG aber extrem schlecht, würde ich sagen. Und es gibt heutzutage ziemlich gute RNGs in wenigen Zeilen, z.B. http://www.pcg-random.org/download.html
Sven B. schrieb: >> Also beispielsweise wenn ein PRNG immer ein Byte >> 0..255 liefert, ergeben sich unterschiedliche Wahrscheinlichkeiten für >> die Ergebnisse -nach- Modulo rand() % 9,8,7, ... usw. > > Dann ist der PRNG aber extrem schlecht, würde ich sagen. Je weniger Bits ein RNG liefert, desto schiefer ist das Ergebnis nach Modulo ungleich 2^K. Bei den beschriebenen 0..255 kann sich das auch bei gutem Generator bemerkbar machen.
:
Bearbeitet durch User
A. K. schrieb: > Sven B. schrieb: >>> Also beispielsweise wenn ein PRNG immer ein Byte >>> 0..255 liefert, ergeben sich unterschiedliche Wahrscheinlichkeiten für >>> die Ergebnisse -nach- Modulo rand() % 9,8,7, ... usw. >> >> Dann ist der PRNG aber extrem schlecht, würde ich sagen. > > Je weniger Bits ein RNG liefert, desto schiefer ist das Ergebnis nach > Modulo ungleich 2^K. Bei den beschriebenen 0..255 kann sich das auch bei > gutem Generator bemerkbar machen. Stimmt, daran habe ich nicht gedacht. Ich nehme meine Aussage zurück.
:
Bearbeitet durch User
Dirk B. schrieb: > rand()%(10-i) Vorsicht: nicht gleichverteilt, d.h. biased. Nimm stattdessen den Fisher–Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle rand() ist auch sehr lahm. Wenn du mehr Zufallszahlen brauchst, könntest du auch darüber nachdenken, einfach einen AES128-CBC (mit TRNG seed) laufen zu lassen. Ist schnell (auch auf einem AVR) und liefert gleichverteilte Zahlen.
> Vorsicht: nicht gleichverteilt, d.h. biased.
Dazu kommt, dass ein 16-Bit-Generator nicht ausreicht, um alle
Permutationen der Länge 10 zu erzeugen.
foobar schrieb: > Dazu kommt, dass ein 16-Bit-Generator nicht ausreicht, um alle > Permutationen der Länge 10 zu erzeugen. Das ist wohl wahr, er erzeugt nur 655350 Permutationen anstelle von 3628800. Hier gehts für mich um ein Rätselgenerator / Spiel das sich in den Programmzeitschriften früher Symbolrätsel nannte und das ich jetzt für Controller mit Display umsetzen möchte. Diese Art Rätsel werden auch "Arithmogriph" genannt. Unterm Strich ist die erreichte Permutation hierfür vollkommen ausreichend und der Generator spuckt sehr brauchbare Rechengleichungen aus:
1 | ibg + ahg = egaa |
2 | - + - |
3 | jbd - abj = fj |
4 | ---------------- |
5 | gdg + fai = eeaf |
Wie das immer so ist, habe ich mich von diesem einen (kleinen) funktionsfähigen Teil ablenken lassen und habe 3 davon jetzt gelöst (die Buchstaben sollen als nächstes durch graphische Symbole ersetzt werden). Allerdings stellt sich mir die Frage, ob aus der Sicht der Dinge heute so etwas noch gemacht wird und wenn ja ob das zu schwierig ist. ---------------------------------------------------- Ohne Ironie: ich finde das immer wieder spannend (und das ist dann eine Bereicherung in diesem Forum) verschiedene Lösungen diskutiert werden. Mir war von Anfang an klar, dass ein 16-Bit Generator keine statistisch guten Werte liefert, aber für meine Aufgabenstellung absolut ausreichend (wie gesagt, der Generator hat schon ein paar harte Nüsse - zumindest für mich - ausgespuckt)
>> Dazu kommt, dass ein 16-Bit-Generator nicht ausreicht, um alle >> Permutationen der Länge 10 zu erzeugen. > > Das ist wohl wahr, er erzeugt nur 655350 Permutationen anstelle von > 3628800. Sind nur 65535 - nicht mal 2%.
Ich schrieb:
> Sind nur 65535
Hmm... etwas nachgedacht ... könnte das doppelte sein, 131070, wenn der
Generator ausschließlich für diese Routine benutzt wird.
Ich schrieb:
> [quatsch]
Max 65535, da aber immer 10 rausgeholt werden, wiederholt sich da
Sequenz nach 13107 Permutationen.
Asche über mein Haupt: 655350 ist ein Schreibfehler, es waren 65535 gemeint. Aber: foobar schrieb: > Max 65535, da aber immer 10 rausgeholt werden, stimmt natürlich, weil das Schieberegister von der Permutation 10 mal aufgerufen wird. Das wären 6553. Wie kommst du auf (2^16)/5 ? (Das ist keine Ironie von mir, das ist wirklich eine Interessens - / Wissensfrage). Ich werde eine kleines Programm schreiben um die verschiedenen Permutationen zu zählen. Für mein Programm spielt es allerdings keine Rolle, weil auch knapp über 6000 reichen.
Ralph S. schrieb: > Wie kommst du auf (2^16)/5 ? Der Zufallszahlengenerator liefert eine sich periodisch wiederholende Folge von 65535 Zahlen. Die ersten beiden Perioden zusammengenommen enthalten also insgesamt 2·65535=131070 Folgenelemente, aus denen für den Permutationsalgorithmus exakt 131070/10=13107 10-Tuples extrahiert werden können. Danach wiederholt sich das Spiel von vorne. Fügst du dem Permutationsalgorithmus noch eine elfte (Dummy-)Abfrage des Zufallszahlengenerators hinzu, wiederholt sich das ganze Spiel erst nach 11 Perioden, da erst dann die Gesamtzahl der Folgenelemente durch 11 teilbar ist. Aus den 65535·11=720885 Folgenelementen werden dabei 720885/11=65535 11-Tupel gebildet. Allgemein: Ist p die Periodenlänge des Zufallszahlengenerators und t die Größe der extrahierten Tupel, dann können n = kgV(p,t) / t = p / ggT(p,t) verschiedene Tupel gebildet werden. Für teilerfremde p und t ist n=p, was für gegebenes p auch das Maximum für n darstellt. Für p=65535 wird mit t=11 dieses Maximum erreicht. Da der Permutationsalgorithmus die nichtinjektive Modulofunktion auf die Zufallszahlen anwendet, ist die Anzahl der erzeugten Permutation i.Allg. noch etwas kleiner als die Anzahl der n Zufallszahlentupel. Dein obiges Programm liefert deswegen nicht 13107, sondern nur 11449 verschiedene Permutationen. Das %10 in deinem Programm ist übrigens nicht ganz richtig, da es die Gleichverteilung der erzeugten Permutationen verzerrt. Richtig wäre %(i+1). Mit dieser Modifiktion liefert das Programm 13060 verschiedene Permutationen.
Hey Yalu, ganz vielen Dank für den Text. Ich merke, dass meine grauen Zellen langsam wirklich noch älter werden. Ich bin am "Aufarbeiten" deines Textes (mit Hirn und mit Miniprogrammen zum für mich verständlichen Analysieren deiner Aussagen). Stimmt alles was du sagst und ich kann das im Moment sogar nachvollziehen, bis auf: Yalu X. schrieb: > Richtig wäre > %(i+1). Da bin ich noch wirklich am Grübeln warum das so ist. Schule ist lange her und immer wieder merk ich, dass ich nur Techniker bin und nicht studiert habe. (smile, nein, kein Selbstmitleid, das ist halt so). ------------------------- Solche Kopfnüsse wie diese hier verhindern das noch schnellere altern.
Ralph S. schrieb: > Yalu X. schrieb: >> Richtig wäre >> %(i+1). > > Da bin ich noch wirklich am Grübeln warum das so ist. Die Idee bei dem Fisher-Yates-Verfahren ist ja die folgende: Zuerst wird das Array auf [0, 1, ... 9] initialisiert. Dann wird ein zufällig ausgewähltes der 10 Elemente mit dem letzten Element (mit Index 9) vertauscht. Somit steht nun an Index 9 eine der Ziffern 0..9, jeweils mit einer Wahrscheinlichkeit von 1/10. Die möglichen Werte an diesem Index sind also gleichverteilt, so wie es sein soll. Damit das so bleibt, wird dieses Element fortan nicht mehr angerührt. Nun wird das im vorigen Abschnitt beschriebene Verfahren auf das um das letzte Element verminderte 9-elementige Unterarray angewandt. Da jetzt das zu tauschende Element nicht mehr aus 10, sondern aus 9 Elementen ausgewählt wird, wird sein zufälliger Index mit mit random16(startw)%9 erzeugt. Das Ganze wird für Untererrays mit 8, 7, 6, 5, 4, 3, 2 und 1 Element(en) wiederholt (wobei man sich den letzten Durchgang sparen könnte, da es bei nur 1 Element nichts mehr zu tauschen gibt). Somit stehen 10 Werte für das Element mit Index 9 zur Verfügung, 9 Werte für das Element mit Index 8, ... und schließlich 1 Wert für das Element mit Index 0. Das ergibt insgesamt 10·9·8·...·1=10! Auswahlmöglichkeiten, was gerade der Anzahl möglicher Permutationen entspricht. Mit random16(startw)%10 hingegen wird das zu tauschende Element in jedem Durchgang aus allen 10 Elementen ausgewählt. Dadurch gibt es insgesamt 10¹⁰ Auswahlmöglichkeiten. Da 10¹⁰>10! ist, sind die 10! möglichen Permutationen mehrfach in den 10¹⁰ Auswahlmöglichkeiten enthalten. Das wäre kein Problem, wenn sie alle gleich oft enthalten wären, was aber nicht der Fall sein kann, weil 10¹⁰ kein ganzzahliges Vielfaches von 10! ist. Da die Gleichverteilung für dich nicht so wichtig ist und sie ohnehin schon durch die Reduktion des Wertebereichs der Zufallszahlen mittels der Modulo-Funktion verzerrt ist, ist das alles im konkreten Fall nicht schlimm. Wenn man das Fisher-Yates-Verfahren aber sauber implementieren möchte, sollte man das schon berücksichtigen. Im Wikipedia-Artikel wird es ebenfalls richtig gemacht:
1 | z = random(i) // Gleichverteilte Zufallszahl zwischen 1 und i |
wobei mit "zwischen 1 und i" hier einschließlich 1 und i gemeint ist. Zu beachten ist noch, dass dort die Arrayindizes anders als in C von 1 ab gezählt werden.
Yalu X. schrieb: > Wenn man das Fisher-Yates-Verfahren aber sauber implementieren > möchte, sollte man das schon berücksichtigen. eben genau drum möchte ich das verstehen. Bisher hab ich einfach fertige Funktionen zu Statistik genommen und gut war. Auch für bestimmte Dinge in der Sprache R. Die unsere Wissenschaftler so lieben und ich nicht. Deine Erklärungen sind gut und haben zum Verständnis geholfen.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.