Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Feb 16th, 2012  |  syntax: C#  |  size: 1.46 KB  |  views: 180  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Diagnostics;
  3.  
  4. public class Chall2
  5. {
  6.        
  7.         public static void Main(string[] args)
  8.         {
  9.                 int max = int.Parse(args[0]);
  10.                 var rand = new Random();
  11.                 Stopwatch sw = new Stopwatch();
  12.                 sw.Start();
  13.  
  14.                 var result = Shuffle( max, n=> rand.Next(n+1) );               
  15.                 sw.Stop();
  16.                
  17.                 Console.WriteLine(" In : {0} ms", sw.Elapsed.TotalMilliseconds);
  18.  
  19.         }
  20.  
  21.  
  22.     // n: number of slots (shuffles n-1)
  23.     // generator:  a random generator given x that gives 0 <= val <= x    
  24.         private static int[] Shuffle(int n, Func<int, int> generator)
  25.         {
  26.                 int[] values = new int[n];             
  27.                 values[0] = 0;
  28.                 for( int i=1; i < n; i++)
  29.                 {
  30.                         var pick = generator(i);
  31.                         values[i] = values[pick];
  32.                         values[pick] = i;
  33.                 }      
  34.                 return values;
  35.         }
  36.  
  37.         //proof by induction:  Each number is output once, and
  38.         // for each possible sequence of random numbers,
  39.         // a different output sequence is obtained
  40.         //   For n = 2:
  41.         //  Possible random sequence:     Output:
  42.     //          0                                               [1,0]
  43.     //          1                                               [0,1]
  44.     //   For n =3
  45.     //              0, 0                                        [2,0,1]
  46.     //              0, 1                                        [1,0,2]
  47.     //              1, 0                                        [0,1,2]
  48.     //              1, 1                                        [0,2,1]
  49.     //                  0, 2                                    [1,2,0]
  50.     //      and so on... (left to the reader)
  51.     // Since there are n! possible random sequences, and
  52.     // n! possible shuffles, and each unique random sequence
  53.     // outputs a unique shuffle, every possible shuffle has
  54.     // an equal chance, given an acceptable random generator.
  55. }
clone this paste RAW Paste Data