Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Diagnostics;
- public class Chall2
- {
- public static void Main(string[] args)
- {
- int max = int.Parse(args[0]);
- var rand = new Random();
- Stopwatch sw = new Stopwatch();
- sw.Start();
- var result = Shuffle( max, n=> rand.Next(n+1) );
- sw.Stop();
- Console.WriteLine(" In : {0} ms", sw.Elapsed.TotalMilliseconds);
- }
- // n: number of slots (shuffles n-1)
- // generator: a random generator given x that gives 0 <= val <= x
- private static int[] Shuffle(int n, Func<int, int> generator)
- {
- int[] values = new int[n];
- values[0] = 0;
- for( int i=1; i < n; i++)
- {
- var pick = generator(i);
- values[i] = values[pick];
- values[pick] = i;
- }
- return values;
- }
- //proof by induction: Each number is output once, and
- // for each possible sequence of random numbers,
- // a different output sequence is obtained
- // For n = 2:
- // Possible random sequence: Output:
- // 0 [1,0]
- // 1 [0,1]
- // For n =3
- // 0, 0 [2,0,1]
- // 0, 1 [1,0,2]
- // 1, 0 [0,1,2]
- // 1, 1 [0,2,1]
- // 0, 2 [1,2,0]
- // and so on... (left to the reader)
- // Since there are n! possible random sequences, and
- // n! possible shuffles, and each unique random sequence
- // outputs a unique shuffle, every possible shuffle has
- // an equal chance, given an acceptable random generator.
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement