Randomiser une liste<T> en C#

Question

Quelle est la meilleure façon de rendre aléatoire l'ordre d'une liste générique en C# ? J'ai un ensemble fini de 75 numéros dans une liste à laquelle je voudrais attribuer un ordre aléatoire, afin de les tirer au sort pour une application de type loterie.

Answer 1

Mélangez n'importe quel (I)List avec une méthode d'extension basée sur le Le remaniement Fisher-Yates :

public static void Shuffle<T>(this IList<T> list)  
{  
    Random rng = new Random();  
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

Utilisation :

List<Product> products = GetProducts();
products.Shuffle();

Le code ci-dessus utilise la méthode très critiquée System.Random pour sélectionner les candidats à l'échange. C'est rapide mais pas aussi aléatoire que cela devrait l'être. Si vous avez besoin d'une meilleure qualité d'aléatoire dans vos mélanges, utilisez le générateur de nombres aléatoires dans System.Security.Cryptography comme suit :

using System.Security.Cryptography;
...
public static void Shuffle<T>(this IList<T> list)
{
    RNGCryptoServiceProvider provider = new RNGCryptoServiceProvider();
    int n = list.Count;
    while (n > 1)
    {
        byte[] box = new byte[1];
        do provider.GetBytes(box);
        while (!(box[0] < n * (Byte.MaxValue / n)));
        int k = (box[0] % n);
        n--;
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}

Une comparaison simple est disponible à l'adresse suivante http://thegrenade.blogspot.com/2010/02/when-random-is-too-consistent.html

Edit : Depuis que j'ai écrit cette réponse il y a quelques années, de nombreuses personnes m'ont fait des commentaires ou m'ont écrit pour souligner le gros défaut stupide de ma comparaison. Ils ont bien sûr raison. Il n'y a rien de mal avec System.Random s'il est utilisé de la façon dont il a été conçu. Dans mon premier exemple ci-dessus, j'instancie la variable rng à l'intérieur de la méthode Shuffle, ce qui pose des problèmes si la méthode est appelée à plusieurs reprises. Vous trouverez ci-dessous un exemple complet et corrigé basé sur un commentaire très utile reçu aujourd'hui de @weston ici sur SO.

Programme.cs :

using System;
using System.Collections.Generic;
using System.Threading;

namespace SimpleLottery
{
  class Program
  {
    private static void Main(string[] args)
    {
      var numbers = new List<int>(Enumerable.Range(1, 75));
      numbers.Shuffle();
      Console.WriteLine("The winning numbers are: {0}", string.Join(",  ", numbers.GetRange(0, 5)));
    }
  }

  public static class ThreadSafeRandom
  {
      [ThreadStatic] private static Random Local;

      public static Random ThisThreadsRandom
      {
          get { return Local ?? (Local = new Random(unchecked(Environment.TickCount * 31 + Thread.CurrentThread.ManagedThreadId))); }
      }
  }

  static class MyExtensions
  {
    public static void Shuffle<T>(this IList<T> list)
    {
      int n = list.Count;
      while (n > 1)
      {
        n--;
        int k = ThreadSafeRandom.ThisThreadsRandom.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
      }
    }
  }
}

Answer 2

Si nous avons seulement besoin de mélanger des éléments dans un ordre complètement aléatoire (juste pour mélanger les éléments dans une liste), je préfère ce code simple mais efficace qui ordonne les éléments par guid...

var shuffledcards = cards.OrderBy(a => Guid.NewGuid());

Answer 3

Je suis un peu surpris par toutes les versions maladroites de ce simple algorithme ici. Fisher-Yates (ou Knuth shuffle) est un peu délicat mais très compact. Si vous allez sur Wikipedia (ou dans les livres d'algorithmes standards tels que CLRS), vous verrez une version de cet algorithme qui a la boucle for inversée et beaucoup de gens ne semblent pas vraiment comprendre pourquoi elle est inversée. La raison principale est que cette version de l'algorithme suppose que le générateur de nombres aléatoires à votre disposition possède les deux propriétés suivantes :

1. Il accepte n comme unique paramètre d'entrée.
2. Il renvoie un nombre de 0 à n inclusivement .

Cependant, le générateur de nombres aléatoires .Net ne satisfait pas la propriété #2. Le site Random.Next(n) renvoie à la place un nombre compris entre 0 et n-1 inclus. Si vous essayez d'utiliser le for-loop en sens inverse, vous devrez appeler Random.Next(n+1) qui ajoute une opération supplémentaire.

Cependant, le générateur de nombres aléatoires .Net possède une autre fonction intéressante. Random.Next(a,b) qui retourne a à b-1 inclus. Cela correspond en fait parfaitement à l'implémentation de cet algorithme qui a une boucle for normale. Donc, sans plus attendre, voici l'implémentation correcte, efficace et compacte :

public static void Shuffle<T>(this IList<T> list, Random rnd)
{
    for(var i=0; i < list.Count; i++)
        list.Swap(i, rnd.Next(i, list.Count));
}

public static void Swap<T>(this IList<T> list, int i, int j)
{
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

Answer 4

Méthode étendue pour IEnumerable :

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

Answer 5

    public static List<T> Randomize<T>(List<T> list)
    {
        List<T> randomizedList = new List<T>();
        Random rnd = new Random();
        while (list.Count > 0)
        {
            int index = rnd.Next(0, list.Count); //pick a random item from the master list
            randomizedList.Add(list[index]); //place it at the end of the randomized list
            list.RemoveAt(index);
        }
        return randomizedList;
    }