An die Algorithmik- und Informatiker: Zufallszahlen

[Ralph S. (jjflash)]

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

[Jemand (Gast)]

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

[Dirk B. (dirkb2)]

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.

[Obelix (Gast)]

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.

[x^y (Gast)]

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

[Ralph S. (jjflash)]

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"

[x^y (Gast)]

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.

[Karl (Gast)]

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.

[Wolfgang (Gast)]

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"

[Ralph S. (jjflash)]

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):

/* -------------------------------------------------------
                           swap8

              tauscht 2 8-Bit Integerwerte
   ------------------------------------------------------- */
void swap8(uint8_t *a, uint8_t *b)
{
  uint8_t tmp;

  tmp= *a;
  *a= *b;
  *b= tmp;
}

/* --------------------------------------------------------
                         random16

    generiert eine 16-Bit grosse Pseudozufallszahl die
    mittels mitgekoppeltem Schieberegister erreicht wird

    Uebergabe:
      startwert  : Ausgangspunkt im Zahlenbereich

    rndm_mask ist die XOR-Maske beim Mitkoppeln des
    Schieberegisters

          XOR-Maske nach     Anzahl unterschiedlichen
          dem Schieben       Zahlen im Ergebnis
          -------------------------------------------
              0xb400               65535
              0x07c1                2047
              0x0be0                4095
  -------------------------------------------------------- */
uint16_t random16(uint16_t startwert)
{
  // Variable MUESSEN static sein, damit das Schieberegister
  // mit jedem Tick von der vorherigen Position aus weiter
  // schiebt
  static uint16_t start_state= 1;
  static uint16_t lfsr= 1;
  static char first = 0;
  uint16_t lsb;

  if (first== 0)
  {
    first= 1;
    start_state= startwert;
    lfsr= start_state;
  }
  lsb = lfsr & 1;                        // niederwertigstes Bit des Schieberegisters
  lfsr = lfsr >> 1;                      // das Schieberegister, eine Stelle nach rechts
  if (lsb) { lfsr ^= 0xb400; }           // wenn LSB gesetzt, XOR-Togglemaske auf SR anwenden
  return lfsr;
}

/* -------------------------------------------------------
                        rndm_permut10

     zufaellige Permutation von 10 Ziffern nach
     Fisher-Yates

     Uebergabe:
        *buf : Zeiger auf 10 Byte grosses Array
   ------------------------------------------------------- */
void rndm_permut10(uint8_t *buf, uint8_t startw)
{
  int8_t i,z;
  uint8_t *ptr;

  for (i= 0; i< 10; i++)
  {
    *(buf+i) = i;
  }
  for (i= 9; i> -1; i--)
  {
    z= (random16(startw) % 10);
    swap8(&(*(buf+i)), &(*(buf+z)));
  }
}
.
.
.
int       i,a;
uint16_t  zstw;

zstw= time(0);               // Zufallszahlenstartwert
for (i= 0; i< 10; i++)
{
  rndm_permut10(&symzif[0], zstw);
  printf("\n\r");
  for (a= 0; a< 10; a++) printf("%d ", symzif[a]);
}

Vielleicht hat das jemand kürzer und knackiger ?!? In dem Falle würde 
ich das dann gerne übernehmen.

Vielen Dank noch mal an "Jemand"

[Sven B. (scummos)]

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

[(prx) A. K. (prx)]

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.

[Sven B. (scummos)]

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.

[W. W. (Gast)]

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.

[foobar (Gast)]

> Vorsicht: nicht gleichverteilt, d.h. biased.

Dazu kommt, dass ein 16-Bit-Generator nicht ausreicht, um alle 
Permutationen der Länge 10 zu erzeugen.

[Ralph S. (jjflash)]

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:

ibg + ahg = egaa
 -     +      -
jbd - abj =   fj
----------------
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)

[foobar (Gast)]

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

[foobar (Gast)]

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.

[foobar (Gast)]

Ich schrieb:
> [quatsch]

Max 65535, da aber immer 10 rausgeholt werden, wiederholt sich da 
Sequenz nach 13107 Permutationen.

[Ralph S. (jjflash)]

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.

[Yalu X. (yalu) (Moderator)]

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.

[Ralph S. (jjflash)]

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.

[Yalu X. (yalu) (Moderator)]

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:

    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.

[Ralph S. (jjflash)]

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.