[Rika]

Multiplikation von Permutationen :-)

Laufe durch das Array durch und bestimme für jede Position jeweils eine zweite Position durch eine Zufallszahl - und dann tausche diese Elemente. Die durch die statistisch gleichverteilten Transpositionen gebildeten möglichen Permutationen sind ebenfalls gleichverteilt.

Random r := new Random();
for Integer i:=0 to 31 do begin
  array[i]:=array[r.getLong()%32];
end;

Dieser Beitrag wurde von Rika bearbeitet: 28. Februar 2006 - 20:49

[Rika]

Nein, eher die Idee dahinter.
Dein ursprüngliches Array ist eine Permutation, das Ziel ist eine Permutation und das Überprüfen, ob ein Array eine Permutation ist, ist halt zu aufwendig. Also verwendet man eine Operation, unter der die Gruppe der Permutation abgeschlossen ist, wie z.B. die Multiplikation.

Und die ist sogar noch isomorph zu der Gruppe selbst und damit gleichverteilt. Die einzige Eleganz besteht darin, das Erstellen einer zufälligen Permutation in das Erstellen von einzelnen zufälligen Transpositionen zu zerlegen.