0

everyone. So I was trying to practice C# today, but I was stuck in figuring out how I can use the Random class to simply shuffle an array

like this for example:

using System;
                    
    public class Program
    {
        public static void Main()
        {
            int[] arr = {1,2,3,4,5};
        
            Random rand = new Random();
        
            for(int i =0; i < arr.Length; i++){
                int shuffle = rand.Next(arr[i]);
                Console.WriteLine(arr[shuffle]);
            }
            
        }
    }

As you can see I tried to use this int shuffle = rand.Next(arr[i]); as a shuffler, but I guess it just duplicates some elements in the array.I'm still noob at this, thanks in advance for the response.

Glen
  • 13
  • 2

3 Answers3

2

You can try implementing Fisher-Yates shuffling algorithm: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

    Random random = new Random();

    ...

    for (int i = 0; i < array.Length - 1; ++i) 
    {
        int r = random.Next(i, array.Length);
        (array[r], array[i]) = (array[i], array[r]);
    }

I suggest extracting a method for this:

// Easiest, but not thread safe
private static Random random = new Random();

private static void Shuffle<T>(T[] array) 
{
    if (array is null)
        throw new ArgumentNullException(nameof(array));
    
    for (int i = 0; i < array.Length - 1; ++i) 
    {
        int r = random.Next(i, array.Length);
        (array[r], array[i]) = (array[i], array[r]);
    }
}

And you can call it from Main:

Shuffle(array);

You can fiddle with the algorithm.

Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
  • This is nice. And I especially like how you are swapping the array elements `(array[r], array[i]) = (array[i], array[r]);` – jet_24 Oct 09 '21 at 11:14
0

There are a few solutions out there, but the one I had used it to create a random array and sort based on that

static class Program
{
    static void Main(string[] args)
    {
        var array = new[] { "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat" };

        Shuffle(ref array);

        foreach (var item in array)
        {
            Console.WriteLine(item);
        }
        // Fri
        // Wed
        // Sat
        // Thu
        // Mon
        // Sun
        // Tue

    }

    static readonly Random rng = new Random();

    public static void Shuffle<T>(ref T[] array)
    {
        double[] key = new double[array.Length];
        for (int i = 0; i < key.Length; i++)
        {
            key[i] = rng.NextDouble();
        }

        Array.Sort(key, array);
    }
}

An alternative is to use the following 1 liner LINQ statement

    static void Main(string[] args)
    {
        var array = new[] { "Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat" };

        var result = array.OrderBy((item) => rng.NextDouble()).ToArray();

     }
John Alexiou
  • 28,472
  • 11
  • 77
  • 133
  • Why allocate a new array and why call `NextDouble()` raqther than just `Next()`? Both seem inefficient to me. – Enigmativity Oct 09 '21 at 06:22
  • @Enigmativity - `NextDouble()` is needed for equal probabilities as they ara have flat probability distribution between `[0,1)`. Unfortunately, you can't do that will next unless the range is `int.MaxValue` which is exactly what `NextDouble()` does. – John Alexiou Oct 09 '21 at 06:48
  • A `double` uses 8 bytes and `int` 4. It's got to be more expensive to produce a random `double` - and `Next()` does return a random value to `int.MaxValue`. – Enigmativity Oct 09 '21 at 06:54
  • @Enigmativity - you can choose what you want, but are the limits you are putting on `.Next()`. Also this seems like micro-optimization something not discussed on the question. – John Alexiou Oct 09 '21 at 07:11
-1

This type of shuffling is going to require seeding the Randomn class to the size of the array. And with each pass in the for loop, it's going to swap the current number with a random other number in the array.

Here is a sample of what the shuffle can look like:

int[] arr = {1,2,3,4,5};

Random rand = new Random();

for(int i = 0; i < arr.Length; i++){
  int shuffle = rand.Next(arr.Length);
  int n = arr[i];
  arr.SetValue(arr[shuffle], i);
  arr.SetValue(n, shuffle);
}

Console.Write('[' + arr[0].ToString());
for(int i = 1; i < arr.Length; i++){
  Console.Write("," + arr[i]);
}
Console.Write("]");
jet_24
  • 598
  • 3
  • 8
  • You can use shorter code: `Console.Write($"[{string.Join(", ", arr[i])}]");` to provide demo output – Dmitry Bychenko Oct 09 '21 at 06:00
  • This algorithm introduces a bias. You must use Fisher-Yates to get it right. The value for `shuffle` must always be equal to or greater than the loop value (in this case `i`). – Enigmativity Oct 09 '21 at 06:21
  • See https://stackoverflow.com/questions/67888049/bug-in-nets-random-class – Enigmativity Oct 09 '21 at 06:47
  • @Enigmativity that's news to me about seeded Random's inherent flaw. Thanks for sharing. The bias appears to be more prevalent in very large sets.. not this set of 5 we're dealing with here in this young lad's HW assignment. And the Yates algo does not shuffle enough for me. With each pass of the set, its pool of available numbers decreases until eventually n = set size and there is no randomness. The algo works, but its designed more for saving CPU on very large sets. – jet_24 Oct 09 '21 at 11:54
  • @JosephTroy - I think you've misunderstood what I was saying. Your algorithm is an incorrectly implemented Fisher-Yates - unless you correct it, it has the bias. You only need one pass of Fisher-Yates to completely randomize - there is no need for multiple passes. And finally, the bias of the `Random` class is astronomically miniscule compared to the bias introduced by the incorrect Fisher-Yates you have in your answer. – Enigmativity Oct 09 '21 at 21:44
  • The Fisher-Price algo iterates across a set of size `n` where `i` = iteration (pass). As `i` approaches `n`, the randomness diminishes until eventually `i = n = rng.Next(i, n) = i = n` => there is no randomness. It is statistically more probable to "de-shuffle" a Bill-Yates shuffled set as opposed to just allowing each pass to random generate between 0 and n. @Enigmativity – jet_24 Oct 10 '21 at 00:42
  • @JosephTroy - No, it's not. Fisher-Yates is perfectly distributed. The `0` to `n` version has a bias and a bias is what makes it statistically more probably to "de-shuffle". That's what a bias is. – Enigmativity Oct 10 '21 at 00:45
  • @Enigmativity It has a bias only because of the defective Random() class. I did notice your research that illustrated this "rainbow" distribution. It is indeed insightful. So assuming that flaw didn't exist, then let's take an example. 5 numbers first pass you have a 20% chance of guessing which number will be produced on both algos. 2nd pass FY-25%, 3rd pass FY-33%, 4th pass FY-50%, 5th pass FY-100%. Where all the while the (0, n) algo you have 20% each pass of guessing what number will be produced. – jet_24 Oct 10 '21 at 01:08
  • @JosephTroy - The bias in the `0` to `n` is a flaw of the algorithm. The `Random` class bias is miniscule compared to the badly implemented Fisher-Yates. The "Bad implementation" image in the link I gave you shows how bad the `0` to `n` algorithm is. – Enigmativity Oct 10 '21 at 01:27
  • @JosephTroy - Your fiddle shows that if you select for numbers near the end of the list then the distribution of numbers is greater at the end. That has nothing to do with the final distribution of the Fisher-Yates algorithm. – Enigmativity Oct 10 '21 at 02:46
  • @Enigmativity that's exactly what the FY algo does... it forces a random number between `i` and `n`. Am I missing the elephant in the room here? And what do you have to say about the non-FY results you see in the fiddle? Does that look flawed? – jet_24 Oct 10 '21 at 02:55
  • @JosephTroy - Please read https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Na%C3%AFve_method – Enigmativity Oct 10 '21 at 03:50