Zufallsausgabe

[Gunnar Bittersmann]

Hello out there!

Der dort vorgestellte Algorithmus ist ziemlicher Mist. Von einem solchen Algorithmus sollte man doch erwarten, dass er alle möglichen Permutationen mit gleicher Wahrscheinlichkeit ausgibt. Das kann dieser Algorithmus (für Anzahl der Elemente n > 2) gar nicht leisten. (Den Beweis spare ich mir für ein separates Posting auf.)

Wird hiermit nachgeholt:

Sei n die Anzahl der Elemente, n > 2.

Der Algorithmus zieht n mal eine aus n Zufallszahlen; dafür gibt es also nⁿ Möglichkeiten. Anhand der einen Zufallszahlenfolge aus nⁿ möglichen wird eine der n! möglichen Permutationen ausgeben. Es ist nⁿ > n!

Damit alle Permutationen gleichwahrscheinlich wären, müsste jede Permutationen durch gleichviele Zufallszahlenfolgen generiert werden. Dazu müsste nⁿ durch n! teilbar sein.

Für ungerades n ist nⁿ ungerade, n! jedoch gerade; nⁿ folglich nicht durch n! teilbar.

Für gerades n = 2k sei p die größte in n und damit auch in nⁿ enthaltene Primzahl; es ist p ≤ k. Nach dem Bertrandschem Postulat liegt zwischen k und 2k = n  eine Primzahl q. Diese ist als Faktor in n! enthalten. Da q > p, kann nⁿ nicht durch n! teilbar sein.

Der Algorithmus erzeugt folglich bei keinem n > 2 eine Gleichverteilung aller Permutationen.

See ya up the road,
Gunnar