Most efficient way to randomly “sort” (Shuffle) a list of integers in C#

Question

I need to randomly 'sort' a list of integers (0-1999) in the most efficient way possible. Any ideas?

Currently, I am doing something like this:

bool[] bIndexSet = new bool[iItemCount];

for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++)
{
    int iSwapIndex = random.Next(iItemCount);
    if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex)
    {
        int iTemp = values[iSwapIndex];
        values[iSwapIndex] = values[iCurIndex];
        values[iCurIndex] = values[iSwapIndex];
        bIndexSet[iCurIndex] = true;
        bIndexSet[iSwapIndex] = true;
    }
}

Answer 1

A good linear-time shuffling algorithm is the Fisher-Yates shuffle.

One problem you'll find with your proposed algorithm is that as you near the end of the shuffle, your loop will spend a lot of time looking for randomly chosen elements that have not yet been swapped. This may take an indeterminate amount of time once it gets to the last element to swap.

Also, it looks like your algorithm will never terminate if there are an odd number of elements to sort.

Answer 2

static Random random = new Random();

public static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> sequence)
{
    T[] retArray = sequence.ToArray();


    for (int i = 0; i < retArray.Length - 1; i += 1)
    {
        int swapIndex = random.Next(i, retArray.Length);
        if (swapIndex != i) {
            T temp = retArray[i];
            retArray[i] = retArray[swapIndex];
            retArray[swapIndex] = temp;
        }
    }

    return retArray;
}

modified to handle lists or other objects implementing IEnumerable

Answer 3

We can make an extension method out of this to get a Random enumerator for any IList collection

class Program
{
    static void Main(string[] args)
    {
        IList<int> l = new List<int>();
        l.Add(7);
        l.Add(11);
        l.Add(13);
        l.Add(17);

        foreach (var i in l.AsRandom())
            Console.WriteLine(i);

        Console.ReadLine();
    }
}


public static class MyExtensions
{
    public static IEnumerable<T> AsRandom<T>(this IList<T> list)
    {
        int[] indexes = Enumerable.Range(0, list.Count).ToArray();
        Random generator = new Random();

        for (int i = 0; i < list.Count; ++i )
        {
            int position = generator.Next(i, list.Count);

            yield return list[indexes[position]];

            indexes[position] = indexes[i];
        }
    }
}   

This uses a reverse Fisher-Yates shuffle on the indexes of the list we want to randomly enumerate through. Its a bit of a size hog (allocating 4*list.Count bytes), but runs in O(n).

Answer 4

As Greg pointed out the Fisher-Yates shuffle would be the best approach. Here is an implementation of the algorithm from Wikipedia:

public static void shuffle (int[] array)
{
   Random rng = new Random();   // i.e., java.util.Random.
   int n = array.length;        // The number of items left to shuffle (loop invariant).
   while (n > 1)
   {
      int k = rng.nextInt(n);  // 0 <= k < n.
      n--;                     // n is now the last pertinent index;
      int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
      array[n] = array[k];
      array[k] = temp;
   }
}

The implementation above relies on Random.nextInt(int) providing sufficiently random and unbiased results

Answer 5

I am not sure of the efficiency factor, but I have used something similar to the following, if you aren't opposed to using an ArrayList:

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }

    return sortedList;
}

Using this, you do not have to worry about the intermediate swapping.

Answer 6

To improve your efficiency you can keep a set of values/indices that have been swapped rather than a boolean for indicating they were swapped. Pick your randomized swap index from the remaining pool. When the pool is 0, or when you made it through the initial list then you are done. You don't have the potential to try to select a random swap index value.

When you do a swap, just remove them from the pool.

For the size of data you are looking at it is no big deal.

Answer 7

itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList()

Answer 8

ICR's answer is very fast, but the resulting arrays aren't distributed normally. If you want a normal distribution, here's the code:

    public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> sequence, int start,int end)
    {
        T[] array = sequence as T[] ?? sequence.ToArray();

        var result = new T[array.Length];

        for (int i = 0; i < start; i++)
        {
            result[i] = array[i];
        }
        for (int i = end; i < array.Length; i++)
        {
            result[i] = array[i];
        }

        var sortArray=new List<KeyValuePair<double,T>>(array.Length-start-(array.Length-end));
        lock (random)
        {
            for (int i = start; i < end; i++)
            {
                sortArray.Add(new KeyValuePair<double, T>(random.NextDouble(), array[i]));
            }
        }

        sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key));

        for (int i = start; i < end; i++)
        {
            result[i] = sortArray[i - start].Value;
        }

        return result;
    }

Note that in my tests, this algorithm was 6 times slower than the one ICR provided, however this is the only way I could come up with to get a normal result distribution

Answer 9

Wouldn't something like this work?

var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
var random = new Random();
list.Sort((a,b)=>random.Next(-1,1));

Answer 10

I guess the last two lines must be interchanged in Micah's answer. So, the code might look like

 public static void shuffle(int[] array) {
        Random rng = new Random();   // i.e., java.util.Random.
        int n = array.Length;        // The number of items left to shuffle (loop invariant).
        while (n > 1) {
            int k = rng.Next(n);  // 0 <= k < n.
            n--;                     // n is now the last pertinent index;
            int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
            array[n] = array[k];
            array[k] = temp;

        }
    }

Answer 11

what about :

System.Array.Sort(arrayinstance, RandomizerMethod);
...
//any evoluated random class could do it !
private static readonly System.Random Randomizer = new System.Random();

private static int RandomizerMethod<T>(T x, T y)
    where T : IComparable<T>
{
    if (x.CompareTo(y) == 0)
        return 0;

    return Randomizer.Next().CompareTo(Randomizer.Next());
}

voila!

Answer 12

I made a method using a temporary Hashtable, allowing the Hashtable's natural key sort to randomize. Simply add, read and discard.

int min = 1;
int max = 100;
Random random;
Hashtable hash = new Hashtable();
for (int x = min; x <= max; x++)
{
    random = new Random(DateTime.Now.Millisecond + x);
    hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x);
}
foreach (int key in hash.Keys)
{
    HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key);
}
hash.Clear(); // cleanup