Fisher-Yates Shuffle for Random Permutations

fisher-yates.cs

using System;
using System.Diagnostics;
using System.Text;

namespace norepeat
{
    public static class Extensions
    {
        public static string FormatForPadZeroUpTo( this int range )
        {
            var n = range - 1;
            var sb = new StringBuilder();

            for( var i = 0; i < n.ToString().Length; i++ )
            {
                sb.Append( "0" );
            }

            return sb.ToString();
        }

        public static string ToStringGroupThrees( this int number, int range )
        {
            var format = range.FormatForPadZeroUpTo();
            var s = number.ToString( format );
            var len = s.Length;

            if( len > 4 )
            {
                s = s.Insert(3, " ");
            }
            if( len > 7 )
            {
                s = s.Insert( 7, " " );
            }
            if( len > 10 )
            {
                s = s.Insert( 11, " " );
            }

            return s;
        }
    }

    public static class FisherYates
    {
        /// <summary>
        /// Generates an array of numbers from 0 to n (exclusive) in random order
        /// </summary>
        /// <param name="n">The exclusive upper bound and length of the generated array</param>
        /// <returns>The generated array</returns>
        public static int[] GenerateRandomArray( Random r, int n )
        {
            var array = new int[n];
            
            for( var i = 0; i < n; i++ )
            {
                array[i] = i;
            }

            int j = 0, t = 0;

            for( var i = 0; i < array.Length; i++ )
            {
                j = r.Next( i );

                t = array[j];
                array[j] = array[i];
                array[i] = t;
            }

            return array;
        }

        /// <summary>
        /// Shuffles a string using the specified seed
        /// </summary>
        /// <param name="s">The string to shuffle</param>
        /// <param name="seed">The seed value (use Environment.TickCount if you don't have one)</param>
        /// <returns>A copy of the string, shuffled</returns>
        public static string Shuffle( this string s, int seed )
        {
            int j;
            char t;
            char[] c = s.ToCharArray();
            Random r = new Random( seed );

            int[] rs = new int[c.Length];
            for( int i = 0; i < c.Length; i++ )
            {
                rs[i] = r.Next( i );
            }

            for( int i = 0; i < c.Length; i++ )
            {
                j = rs[i];
                t = c[j];
                c[j] = c[i];
                c[i] = t;
            }

            return new string( c );
        }

        /// <summary>
        /// Shuffles a string using the specified seed (in reverse, can undo Shuffle if the same seed is used)
        /// </summary>
        /// <param name="s">The string to shuffle</param>
        /// <param name="seed">The seed value (use Environment.TickCount if you don't have one)</param>
        /// <returns>A copy of the string, shuffled</returns>
        public static string Unshuffle( this string s, int seed )
        {
            int j;
            char t;
            char[] c = s.ToCharArray();
            Random r = new Random( seed );

            int[] rs = new int[c.Length];
            for( int i = 0; i < c.Length; i++ )
            {
                rs[i] = r.Next( i );
            }

            for( int i = c.Length - 1; i >= 0; i-- )
            {
                j = rs[i];
                t = c[j];
                c[j] = c[i];
                c[i] = t;
            }

            return new string( c );
        }
    }

    class Program
    {
        const int RANGE = 10000000;
        const int ITERATIONS = 50;

        static void Main( string[] args )
        {
            var timer = Stopwatch.StartNew();
            var random = new Random();
            var numbers = new int[1];
            var times = new int[ITERATIONS];

            for( int i = 0; i < ITERATIONS; i++ )
            {
                timer.Restart();
                numbers = FisherYates.GenerateRandomArray( random, RANGE );
                times[i] = (int)timer.ElapsedMilliseconds;
                Console.WriteLine( times[i].ToString() + " milliseconds." );
            }
            Console.WriteLine();

            var sum = 0;
            foreach(var t in times)
            {
                sum += t;
            }

            Console.WriteLine( "Range: " + RANGE + ", Iterations: " + ITERATIONS );
            Console.WriteLine( "Average: " + ( sum / times.Length ).ToString() + " milliseconds." );
            Console.Write("Average/Range: " + (((double)sum / (double)times.Length) / (double)RANGE).ToString() + " milliseconds.");
            Console.ReadKey();
            Console.WriteLine();

            Console.WriteLine( "Last Numbers:" );
            var format = RANGE.FormatForPadZeroUpTo();

            foreach( var number in numbers )
            {
                Console.WriteLine( number.ToStringGroupThrees( RANGE ) );
            }
            Console.WriteLine();
        }
    }
}

prenumber-output.txt

354 milliseconds.
376 milliseconds.
371 milliseconds.
369 milliseconds.
363 milliseconds.
370 milliseconds.
372 milliseconds.
366 milliseconds.
368 milliseconds.
375 milliseconds.
374 milliseconds.
382 milliseconds.
371 milliseconds.
372 milliseconds.
371 milliseconds.
369 milliseconds.
369 milliseconds.
368 milliseconds.
377 milliseconds.
375 milliseconds.
375 milliseconds.
371 milliseconds.
369 milliseconds.
369 milliseconds.
370 milliseconds.
370 milliseconds.
384 milliseconds.
384 milliseconds.
407 milliseconds.
369 milliseconds.
369 milliseconds.
367 milliseconds.
368 milliseconds.
384 milliseconds.
381 milliseconds.
406 milliseconds.
369 milliseconds.
382 milliseconds.
398 milliseconds.
373 milliseconds.
373 milliseconds.
368 milliseconds.
377 milliseconds.
384 milliseconds.
388 milliseconds.
398 milliseconds.
363 milliseconds.
361 milliseconds.
371 milliseconds.
393 milliseconds.

Range: 10,000,000, Iterations: 50
Average: 372 milliseconds.
Average/Range: 3.725E-05 milliseconds.