Best way to randomize an array with NET

Question

What is the best way to randomize an array of strings with  NET  My array contains about 500 strings and I d like to create a new Array with the same strings but in a random order   Please include a C  example in your answer

User · Answer

The following implementation uses the Fisher-Yates algorithm AKA the Knuth Shuffle. It runs in O(n) time and shuffles in place, so is better performing than the 'sort by random' technique, although it is more lines of code. See here for some comparative performance measurements. I have used System.Random, which is fine for non-cryptographic purposes.*

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

Usage:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* For longer arrays, in order to make the (extremely large) number of permutations equally probable it would be necessary to run a pseudo-random number generator (PRNG) through many iterations for each swap to produce enough entropy. For a 500-element array only a very small fraction of the possible 500! permutations will be possible to obtain using a PRNG. Nevertheless, the Fisher-Yates algorithm is unbiased and therefore the shuffle will be as good as the RNG you use.

User · Answer

Randomizing the array is intensive as you have to shift around a bunch of strings   Why not just randomly read from the array   In the worst case you could even create a wrapper class with a getNextString     If you really do need to create a random array then you could do something like  for i   0 - gt  i  array length   5    swap two strings in random places   The  5 is arbitrary

User · Answer

If you re on  NET 3 5  you can use the following IEnumerable coolness  Random rnd new Random    string   MyRandomArray   MyArray OrderBy x   gt  rnd Next    ToArray         Edit  and here s the corresponding VB NET code  Dim rnd As New System Random Dim MyRandomArray   MyArray OrderBy Function   rnd Next    ToArray    Second edit  in response to remarks that System Random  quot isn t threadsafe quot  and  quot only suitable for toy apps quot  due to returning a time-based sequence  as used in my example  Random   is perfectly thread-safe  unless you re allowing the routine in which you randomize the array to be re-entered  in which case you ll need something like lock  MyRandomArray  anyway in order not to corrupt your data  which will protect rnd as well  Also  it should be well-understood that System Random as a source of entropy isn t very strong  As noted in the MSDN documentation  you should use something derived from System Security Cryptography RandomNumberGenerator if you re doing anything security-related  For example  using System Security Cryptography       RNGCryptoServiceProvider rnd   new RNGCryptoServiceProvider    string   MyRandomArray   MyArray OrderBy x   gt  GetNextInt32 rnd   ToArray         static int GetNextInt32 RNGCryptoServiceProvider rnd                byte   randomInt   new byte 4           rnd GetBytes randomInt           return Convert ToInt32 randomInt 0

User · Answer

This algorithm is simple but not efficient  O N2   All the  order by  algorithms are typically O N log N   It probably doesn t make a difference below hundreds of thousands of elements but it would for large lists   var stringlist          add your values to stringlist  var r   new Random     var res   new List lt string gt  stringlist Count    while  stringlist Count  gt 0       var i   r Next stringlist Count      res Add stringlist i       stringlist RemoveAt i       The reason why it s O N2  is subtle  List RemoveAt   is a O N  operation unless you remove in order from the end

User · Answer

Jacco  your solution ising a custom IComparer isn t safe   The Sort routines require the comparer to conform to several requirements in order to function properly   First among them is consistency   If the comparer is called on the same pair of objects  it must always return the same result    the comparison must also be transitive    Failure to meet these requirements can cause any number of problems in the sorting routine including the possibility of an infinite loop     Regarding the solutions that associate a random numeric value with each entry and then sort by that value  these are lead to an inherent bias in the output because any time two entries are assigned the same numeric value  the randomness of the output will be compromised    In a  stable  sort routine  whichever is first in the input will be first in the output   Array Sort doesn t happen to be stable  but there is still a bias based on the partitioning done by the Quicksort algorithm    You need to do some thinking about what level of randomness you require   If you are running a poker site where you need cryptographic levels of randomness to protect against a determined attacker you have very different requirements from someone who just wants to randomize a song playlist   For song-list shuffling  there s no problem using a seeded PRNG  like System Random    For a poker site  it s not even an option and you need to think about the problem a lot harder than anyone is going to do for you on stackoverflow   using a cryptographic RNG is only the beginning  you need to ensure that your algorithm doesn t introduce a bias  that you have sufficient sources of entropy  and that you don t expose any internal state that would compromise subsequent randomness

User · Answer

Ok  this is clearly a bump from my side  apologizes      but I often use a quite general and cryptographically strong method   public static class EnumerableExtensions       static readonly RNGCryptoServiceProvider RngCryptoServiceProvider   new RNGCryptoServiceProvider        public static IEnumerable lt T gt  Shuffle lt T gt  this IEnumerable lt T gt  enumerable                var randomIntegerBuffer   new byte 4           Func lt int gt  rand        gt                                                                  RngCryptoServiceProvider GetBytes randomIntegerBuffer                                    return BitConverter ToInt32 randomIntegerBuffer  0                                           return from item in enumerable                let rec   new  item  rnd   rand                   orderby rec rnd                select rec item            Shuffle   is an extension on any IEnumerable so getting  say  numbers from 0 to 1000 in random order in a list can be done with  Enumerable Range 0 1000  Shuffle   ToList     This method also wont give any surprises when it comes to sorting  since the sort value is generated and remembered exactly once per element in the sequence

User · Answer

This is a complete working Console solution based on the example provided in here   class Program       static string   words1   new string      brown    jumped    the    fox    quick          static void Main                 var result   Shuffle words1           foreach  var i in result                        Console Write i                           Console ReadKey              static string   Shuffle string   wordArray            Random random   new Random            for  int i   wordArray Length - 1  i  gt  0  i--                        int swapIndex   random Next i   1               string temp   wordArray i               wordArray i    wordArray swapIndex               wordArray swapIndex    temp                    return wordArray

User · Answer

Just thinking off the top of my head  you could do this   public string   Randomize string   input      List lt string gt  inputList   input ToList      string   output   new string input Length     Random randomizer   new Random      int i   0     while  inputList Count  gt  0          int index   r Next inputList Count       output i      inputList index       inputList RemoveAt index          return  output

User · Answer

You re looking for a shuffling algorithm  right   Okay  there are two ways to do this  the clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-all way  and the dumb-as-rocks-but-who-cares-because-it-works way   Dumb way        Create a duplicate of your first array  but tag each string should with a random number    Sort the duplicate array with respect to the random number       This algorithm works well  but make sure that your random number generator is unlikely to tag two strings with the same number   Because of the so-called Birthday Paradox  this happens more often than you might expect   Its time complexity is O n log n    Clever way  I ll describe this as a recursive algorithm      To shuffle an array of size n  indices in the range  0  n-1         if n   0         do nothing         if n   0          recursive step  shuffle the first n-1 elements of the array   choose a random index  x  in the range  0  n-1    swap the element at index n-1 with the element at index x      The iterative equivalent is to walk an iterator through the array  swapping with random elements as you go along  but notice that you cannot swap with an element after the one that the iterator points to   This is a very common mistake  and leads to a biased shuffle   Time complexity is O n

User · Answer

Generate an array of random floats or ints of the same length   Sort that array  and do corresponding swaps on your target array   This yields a truly independent sort

User · Answer

int   numbers    0 1 2 3 4 5 6 7 8 9           List lt int gt  numList   new List lt int gt             numList AddRange numbers            Console WriteLine  Original Order            for  int i   0  i  lt  numList Count  i                          Console Write String Format   0    numList i                        Random random   new Random            Console WriteLine   n nRandom Order            for  int i   0  i  lt  numList Capacity  i                          int randomIndex   random Next numList Count               Console Write String Format   0     numList randomIndex                 numList RemoveAt randomIndex                     Console ReadLine

User · Answer

Here s a simple way using OLINQ      Input array List lt String gt  lst   new List lt string gt     for  int i   0  i  lt  500  i    1  lst Add i ToString         Output array List lt String gt  lstRandom   new List lt string gt         Randomize Random rnd   new Random    lstRandom AddRange from s in lst orderby rnd Next 100  select s

User · Answer

You don t need complicated algorithms   Just one simple line   Random random   new Random    array ToList   Sort  x  y    gt  random Next -1  1   ToArray      Note that we need to convert the Array to a List first  if you don t use List in the first place   Also  mind that this is not efficient for very large arrays  Otherwise it s clean  amp  simple

User · Answer

private ArrayList ShuffleArrayList ArrayList source        ArrayList sortedList   new ArrayList        Random generator   new Random         while  source Count  gt  0                int position   generator Next source Count           sortedList Add source position            source RemoveAt position               return sortedList

User · Answer

Random r   new Random    List lt string gt  list   new List originalArray   List lt string gt  randomStrings   new List     while list Count  gt  0    int i   r Random list Count   randomStrings Add list i    list RemoveAt i

User · Answer

This post has already been pretty well answered - use a Durstenfeld implementation of the Fisher-Yates shuffle for a fast and unbiased result  There have even been some implementations posted  though I note some are actually incorrect   I wrote a couple of posts a while back about implementing full and partial shuffles using this technique  and  this second link is where I m hoping to add value  also a follow-up post about how to check whether your implementation is unbiased  which can be used to check any shuffle algorithm  You can see at the end of the second post the effect of a simple mistake in the random number selection can make

User · Answer

You can also make an extention method out of Matt Howells  Example      namespace System               public static class MSSystemExtenstions                       private static Random rng   new Random                public static void Shuffle lt T gt  this T   array                                rng   new Random                    int n   array Length                  while  n  gt  1                                        int k   rng Next n                       n--                      T temp   array n                       array n    array k                       array k    temp                                                    Then you can just use it like            string   names   new string                      Aaron Moline1                     Aaron Moline2                     Aaron Moline3                     Aaron Moline4                     Aaron Moline5                     Aaron Moline6                     Aaron Moline7                     Aaron Moline8                     Aaron Moline9                           names Shuffle lt string gt

[c#] Best way to randomize an array with .NET

Examples related to c#

Examples related to .net

Examples related to algorithm

Examples related to sorting

Examples related to random