Knuth shuffle
Implement the Knuth Shuffle (aka the Fisher-Yates Shuffle) for an integer array. Knuth shuffle is used to create a random permutation of an array.
You are encouraged to solve this task according to the task description, using any language you may know.
Modula-3
<lang modula3>MODULE Shuffle EXPORTS Main;
IMPORT IO, Fmt, Random;
VAR a := ARRAY [0..9] OF INTEGER {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
PROCEDURE Shuffle(VAR a: ARRAY OF INTEGER) =
VAR temp: INTEGER;
n: INTEGER := NUMBER(a);
BEGIN
WITH rand = NEW(Random.Default).init() DO
WHILE n > 1 DO
WITH k = rand.integer(0, n - 1) DO
DEC(n);
temp := a[n];
a[n] := a[k];
a[k] := temp;
END;
END;
END;
END Shuffle;
BEGIN
Shuffle(a);
FOR i := FIRST(a) TO LAST(a) DO
IO.Put(Fmt.Int(a[i]) & " ");
END;
IO.Put("\n");
END Shuffle.</lang> Output:
martin@thinkpad:~$ ./shuffle 9 2 7 3 6 8 4 5 1 10 martin@thinkpad:~$ ./shuffle 1 7 8 10 5 4 6 3 9 2