The most efficient way to randomly “shuffle” a list of integers in C #

Question

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

I am currently 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 Fisher-Yates shuffle .

One of the problems that you will find in the algorithm you have proposed is that when you get close to the end of the shuffle, your cycle will spend a lot of time looking for randomly selected elements that have not yet been replaced. This can take an indefinite period of time as soon as it reaches the last item to exchange.

Also, it looks like your algorithm will never end if there is an odd number of items 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 that implement IEnumerable

Answer 3

We can make an extension from this method to get a random enumerator for any set of IList

 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 Fisher-Yates reverse sorting in the indexes of the list that we want to randomly list. Its bit is of size hog (allocation of 4 * list.Count bytes), but works in O (n).

Answer 4

As Greg noted, the best approach would be a Fisher-Yates shuffle . Here is the implementation of the algorithm from Wikipedia:

 public static void shuffle (int[] array) { Random rng = new Random(); // ie, 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 is based on Random.nextInt (int) providing fairly random and unbiased results

Answer 5

I'm not sure about the efficiency ratio, but I used something similar to the following, if you don't mind 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 need to worry about an interchange.

Answer 6

To increase efficiency, you can save the set of values ​​/ indices that were replaced, rather than logical, to indicate that they were replaced. Select your randomized swap index from the remaining pool. When the pool is 0, or when you did it through the start list, you are done. You have no way to try to select a random swap index value.

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

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

Answer 7

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

Answer 8

The ICR response is very fast, but the resulting arrays are not distributed normally. If you want a normal distribution, here is 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; } 

Please note that in my tests this algorithm was 6 times slower than one ICR, however this is the only way to get a normal distribution of results

Answer 9

Wouldn’t it be like this job?

 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 think the last two lines should be interchangeable in Micah's answer. So the code may look like

  public static void shuffle(int[] array) { Random rng = new Random(); // ie, 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 to randomly sort the Hashtable natural key. Just 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