An die Algorithmik- und Informatiker: Zufallszahlen

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.

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"

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.

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.

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)

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.