0

i am currently doing leetcode to prepare for job interviews and i came across a shuffle challenge. I looked shuffles up and came across fisher yates shuffle method and i got curious to learn the basics.

so my question is, how does this work?

currently i figured that the random value takes the current index and adds a random value from 0 to 1 multiplied with the length of the array minus the current index.

Here i am curious about if the random generates a value between 0 and length and places the shuffled value at that index, or if it generates a value there? i am a bit confused as i want to learn it and memorize it for the future

this is the code:

static void Shuffle<T>(T[] array)
        {
            int n = array.Length;
            for (int i = 0; i < n; i++)
            {
                //_random.NextDouble() float >= 0 and less than 1 float >= 0 < 1
                // n = 4
                int random = i + (int)(_random.NextDouble() * (n - i)); // int random = 0 + randNext * (4-0) = [0,4]
                                                                        // int random = 1 + randNext * (4-1) = [1,3]
                                                                        //int random =  2 + randNext * (4-2) = [2,2]
                                                                        //random =      3 + randNext * (4-3) = [
                //Console.Write("rand is: " + random + " i: " + i + " next: " + (int)(_random.NextDouble()*(n-i)));
                T t = array[random];
                array[random] = array[i]; // array[0,4] = array[0] = array[2] = 1
                array[i] = t;
                Console.WriteLine(array[i]);
            }
        }

basically im curious if anyone can tell me if my understand is correct or im misunderstanding the algorithm :D thx a lot

Angelo
  • 1
  • 1
  • 1
    The code you have above is (slightly) broken. See [this answer](https://stackoverflow.com/a/110570) in the duplicate for a correct version. You should be able to tell just by studying the code exactly how it works. The short version: for each element in the array, it selects a random element from the remaining elements, and stores it in the current element. The value there is placed in that value's previous location, so it is still eligible for selection later. – Peter Duniho Feb 15 '21 at 08:54
  • 1
    The algorithm is explained quite well [on wikipedia](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) – Matthew Watson Feb 15 '21 at 08:59

0 Answers0