Previously we learned how to use a Linear Congruential Generator (use values a = 445, c = 700001, m = 2097069) to generate a list of psuedo-random numbers.
Now we will learn how to use the LCG to shuffle a list into pseudo-random order.
If we want to shuffle a list of integers of length n,
then we first generate a list of random numbers of the same length using our LCG and some seed value x0.
For each random number r at index i, we take the value r mod n.
For this example let's use a seed value of x0 = 9001.
i │ r │ r mod n
───┼─────────┼───────
0 │ 511308 │ 8
1 │ 1748609 │ 9
2 │ 818407 │ 7
3 │ 1110 │ 0
4 │ 1193951 │ 1
5 │ 1449739 │ 9
6 │ 2033673 │ 3
7 │ 1847747 │ 7
8 │ 896368 │ 8
9 │ 1140651 │ 1
For each value located at index iin our original list, we swap it with the value located at index r mod n.
So for our example, if the initial list consisted of sequential values equal to their indexes, we would perform the following steps:
0 (0) with the value at index 8 (8).1 (1) with the value at index 9 (9).2 (2) with the value at index 7 (7).3 (3) with the value at index 0 (8).4 (4) with the value at index 1 (9).5 (5) with the value at index 9 (1).6 (6) with the value at index 3 (8).7 (2) with the value at index 7 (2).8 (0) with the value at index 8 (0).9 (5) with the value at index 1 (4).The final result of values in the array should be [3, 5, 7, 6, 9, 1, 8, 2, 0, 4].
Input Data
First line will be three integers x0 n m, with x0 being the seed value of the Linear Congruential Generator, n being the quantity of values in the initial list, and m be the number of times the list must be shuffled.
Answer
Should consist of n space-separated values, corresponding to the original indexes of wherever the original values ended up after shuffling.
Example
input data:
9001 10 2
answer:
5 0 6 2 1 3 7 9 8 4