Algorithmus für Permutation

14/12/2008 - 20:03 von Christof Reusch | Report spam
Hallo NG,

wie sieht ein effizienter Algotithmus für eine zufàllige Permutition aus?

Oder anders ausgedrückt: Wie befülle ich ein Array[1..n] zufàllig mit allen
Zahlen 1 bis n?

Besten Dank im voraus.

Gruß Christof.
 

Lesen sie die antworten

#1 Stefan Kirchner
14/12/2008 - 20:20 | Warnen spam
On Sun, 14 Dec 2008, Christof Reusch wrote:

Hallo NG,

wie sieht ein effizienter Algotithmus für eine zufàllige Permutition aus?

Oder anders ausgedrückt: Wie befülle ich ein Array[1..n] zufàllig mit allen
Zahlen 1 bis n?



// a sei Array[1..n]
for k = 1 to n
a[k] = k
next

for k = n downto 2
j = Zufallszahl mit 1 <= j <= k
vertausche a[j] und a[k]
next


Jede Permutation ist dann gleichwahrscheinlich [Übungsaufgabe], Aufwand
ist O(n) [ist hoffentlich offensichtlich].


Gruß Stefan

Ähnliche fragen