“Shuffle” an IEnumerable

By | November 13, 2012

Working on a current project, had a need to do this. It’s a pretty brute-force way of doing things because frankly, I’m not a brainiac :)

Interested in what my readers think.

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> collection)
		{
			var r = new Random();
			var enumerable = collection as T[] ?? collection.ToArray();
			int numItems = enumerable.Count();
			// Create a new spot to put 'em
			var retVal = new T[numItems];

			// Know which ones we've put in
			var addedIndices = new int[numItems];

			for (int i = 0; i < numItems; i++)
			{
				if (i == numItems - 1)
				{   // Last item, don't waste any time just pick the last one available
					retVal[i] = enumerable.Except(retVal).First();
				}
				else
				{
					// Pick one from the source that we haven't picked yet
					int chosenIndex;
					do
					{
						chosenIndex = r.Next(numItems);
					} while (addedIndices.Contains(chosenIndex));

					retVal[i] = enumerable[chosenIndex];
					addedIndices[i] = chosenIndex;
				}
			}

			return retVal;
		}
  • ArchieCoder

    I found this last year:

    public static class Shuffler
    {
    #region Methods

    public static void Shuffle(this IList list)
    {
    Random random = new Random();
    int n = list.Count;

    while (n > 1)
    {
    byte[] box = new byte[1];

    do
    {
    random.NextBytes(box);

    } while (!(box[0] < n * (Byte.MaxValue / n)));

    int k = (box[0] % n);
    n–;

    T value = list[k];
    list[k] = list[n];
    list[n] = value;
    }
    }

    #endregion
    }

    • Brandon

      That’s interesting. I wonder why the usage of Random w/ Bytes and the byte stuff? I see the “in place” shuffling, which is something I did consider.

      One of my buddies, @ananthonline suggested a way to do this w/ one line of LINQ, believe it or not!

      https://twitter.com/ananthonline/status/268611833760456704 :
      simpler to do “enumerable.Orderby(e => Guid.NewGuid())”, should also be a better uniform distribution. Still O(N) though. Hmmmm…

      I had to think about this a bit to figure out why it works… Basically, you’re telling LINQ to order the Enumerable, then giving it a new GUID, which is very unique and very random. Therefore for each value in your enumerable, you’re basically associating it, within the LINQ execution, with a random GUID and then telling it to sort by that. Pretty ingenious :)

  • Joe

    My eyes, the goggles do nothing.

    for i = 0 to N-1, pick a random number k from i to N – 1 (inclusive). Swap the element at index i with the element at index k. O(n), and it is actually random.

    • Brandon

      I think that would leave the last element always in the last spot, would it not?

      • Joe

        No – because if N – 1 is chosen as the random number at any point, the last element is moved to the front.

        Put another way, in each iteration of the loop, each of the remaining elements is equally likely to be chosen next.

  • I figured that there should be a way to do it using “Sort” or “OrderBy.” Rather than getting creative, I just did a Bing/Google search on this (yeah, lazy me):

    http://bolsterweb.com/2010/05/random-sort-on-ienumerable-object/

    public static IEnumerable Random(this IEnumerable source)
    {
    return source.OrderBy(x => Guid.NewGuid());
    }