We should have a Shuffle function for the Array base class - like Java

This is only my opinion of course and I am, like always, braced for someone to come along and say "There is one!" lol .  But at present I am not aware if there is one, so... I am just writing to display my attempt at one.  I think I have made it quite, well generic, in the fact that I have used generics.  I would love to see any Maths gurus out there put me to shame by cutting my lines of code in half or less lol, using some real efficient maths.  I need to learn more about that topic.  So complex.

Any way here is my attempt.  It looks long to me, but I as I was once told, "Don't let perfection get in the way of GOOD ENOUGH."

Hide Code [-] 
        public static T[] RandomizeArray<T>(T[] listIn)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            T[] destination = new T[listIn.Length];
            T[] stagingList = listIn;
            for (int i = 0; i < listIn.Length; i++)
            {
                T[] tempList = new T[stagingList.Length == 1 ? stagingList.Length : stagingList.Length - 1];
                int randomNumber = r.Next(stagingList.Length);
                destination[i] = randomNumber == 0 ? stagingList[0] : stagingList[randomNumber - 1];
                int item = 0;
                for (int j = 0; j < stagingList.Length; j++)
                {
                    if (j != ((randomNumber == 0) ? 0 : randomNumber - 1))
                    {
                        tempList[item] = stagingList[j];
                        item++;
                    }
                }
                stagingList = tempList;
            }
            return destination;
        }
{..} Click Show Code

 

The example implementation is as follows:

 

Hide Code [-] 
            int[] test = new int[10];

            for (int i = 0; i < 10; i++)
            {
                test[i] = i;
            }

            int[] newList = RandomizeArray<int>(test);

            foreach (int j in newList)
            {
                Console.WriteLine(j.ToString());
            }

            newList = RandomizeArray<int>(test);

            Console.ReadLine();
{..} Click Show Code

 

Cheers,

 

Andrew :-)

Published Monday, June 16, 2008 10:05 PM by REA_ANDREW
Filed under: , , ,

Comments

# re: We should have a Shuffle function for the Array base class - like Java

Monday, June 16, 2008 8:29 PM by Michael Hart

Why not use Lists to do it? Much cleaner...

Also, the default constructor to Random uses a time-dependent seed anyway. And you might want to allow people to put their own random generator in there - for example, if they're shuffling many lists, then they would just want to initialise Random once, otherwise it's unlikely to still be "random".

The main performance hits in the code below are the cloning of the enumerable and the removal from the remaining items list - the latter could be alleviated by using an OrderedDictionary if the items are unique, at the sacrifice of a little cleanliness and memory, but probably a big speed-up for very large arrays.

public static T[] RandomizeArray<T>(T[] listIn)

{

   return RandomizeArray<T>(listIn, new Random());

}

public static T[] RandomizeArray<T>(T[] listIn, Random randGen)

{

   return RandomizeList<T>(listIn, randGen).ToArray();

}

public static List<T> RandomizeList<T>(IEnumerable<T> listIn)

{

   return RandomizeList<T>(listIn, new Random());

}

public static List<T> RandomizeList<T>(IEnumerable<T> listIn, Random randGen)

{

   List<T> remainingItems = new List<T>(listIn);

   List<T> shuffledItems = new List<T>(remainingItems.Count);

   while (remainingItems.Count > 0)

   {

       int remainingItemsIx = randGen.Next(remainingItems.Count);

       shuffledItems.Add(remainingItems[remainingItemsIx]);

       remainingItems.RemoveAt(remainingItemsIx);

   }

   return shuffledItems;

}

# re: We should have a Shuffle function for the Array base class - like Java

Monday, June 16, 2008 9:15 PM by Michael Hart

Actually, what was I thinking, it's much quicker to use swapping...

public static T[] RandomizeArray<T>(T[] listIn)

{

   return RandomizeArray<T>(listIn, new Random());

}

public static T[] RandomizeArray<T>(T[] listIn, Random randGen)

{

   T[] shuffled = (T[])listIn.Clone();

   // Don't need to go to 1 as Random.Next(1) always equals 0

   for (int i = shuffled.Length; i > 1; i--)

   {

       int randIx = randGen.Next(i);

       T randItem = shuffled[randIx];

       shuffled[randIx] = shuffled[i - 1];

       shuffled[i - 1] = randItem;

   }

   return shuffled;

}

# re: We should have a Shuffle function for the Array base class - like Java

Monday, June 16, 2008 9:59 PM by Raj

Consider using the RNGCryptoServiceProvider class instead..

msdn.microsoft.com/.../system.security.cryptography.rngcryptoserviceprovider.aspx

# re: We should have a Shuffle function for the Array base class - like Java

Wednesday, June 18, 2008 7:19 AM by REA_ANDREW

Hi Michael:

One small amend to your code.  I did the following to output three runs of your function:

           int[] i = new int[] { 1,2,3,4,5,6,7,8,9,10};

           int[] b = RandomizeArray<int>(i);

           foreach(int a in b)

           {

               Console.WriteLine(a);

           }

           Console.WriteLine("--");

           b = RandomizeArray<int>(i);

           foreach (int a in b)

           {

               Console.WriteLine(a);

           }

           Console.WriteLine("--");

           b = RandomizeArray<int>(i);

           foreach (int a in b)

           {

               Console.WriteLine(a);

           }

           Console.ReadLine();

Now this gave the exact same order three times.  So simply putting in a seed fixes this, so my simple amend was this:

       public static T[] RandomizeArray<T>(T[] listIn)

       {

           return RandomizeArray<T>(listIn, new Random(DateTime.Now.Millisecond));

       }

GREAT WORK, on the small function.  I knew someone like yourself, would come and show me lol.  Great Work!

Cheers,

Andrew :-)

# re: We should have a Shuffle function for the Array base class - like Java

Tuesday, July 29, 2008 12:23 PM by Jens

I was actually wondering this myself, but came up with another solution: why not sort the array, but randomly? That is, sort with a predicate that returns a random value between -1 and 1 (for lesser than, equal and greater than).

Example:

   public class RandomComparer : IComparer

   {

       public RandomComparer(int max)

       {

           m_count = max;

       }

       int IComparer.Compare(object x, object y)

       {

           --m_count;

           if (m_count >= 0 || x.Equals (y))

           {

               return 0;

           }

           else

           {

               return m_rnd.Next (-1, 2);

           }

       }

       private int m_count = 0;

       private Random m_rnd = new Random ();

   }

Usage:

       int[] numbers = new int[] { 0, 1, 2, 3, 4, 5, 6 };

       Array.Sort (numbers, new RandomComparer (numbers.GetLength (0)));

Probably not the best solution, but it's simple.

Leave a Comment

(required) 
(required) 
(optional)
(required)