Question Randomiser une liste


Quelle est la meilleure façon de randomiser l'ordre d'une liste générique en C #? J'ai un ensemble fini de 75 nombres dans une liste que je voudrais assigner un ordre aléatoire, afin de les dessiner pour une application de type de loterie.


652
2017-11-07 19:28


origine


Réponses:


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

private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> list)  
{  
    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;  
    }  
}

Usage:

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

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

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 sur ce blog (Machine WayBack).

Edit: Depuis que j'ai écrit cette réponse il y a quelques années, beaucoup de gens m'ont commenté ou écrit pour souligner la grande faille dans ma comparaison. Ils ont bien sûr raison. System.Random ne présente aucun problème s'il est utilisé de la manière prévue. Dans mon premier exemple ci-dessus, j'instancie la variable rng à l'intérieur de la méthode Shuffle, ce qui pose problème si la méthode va être appelée plusieurs fois. Voici un exemple complet, basé sur un commentaire très utile reçu aujourd'hui de @weston ici sur SO.

Program.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;
      }
    }
  }
}

922
2017-08-11 20:07



Si nous avons seulement besoin de mélanger les é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 des éléments par guid ...

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

250
2017-11-23 23:34



Je suis un peu surpris par toutes les versions maladroites de cet algorithme simple ici. Fisher-Yates (ou Knuth shuffle) est un peu difficile mais très compact. Si vous allez sur Wikipédia, vous verrez une version de cet algorithme qui a une boucle inversée et beaucoup de gens ne semblent pas vraiment comprendre pourquoi c'est l'inverse. La raison principale est que cette version de l'algorithme suppose que le générateur de nombres aléatoires Random(n) à votre disposition a deux propriétés suivantes:

  1. Il accepte n comme paramètre d'entrée unique.
  2. Renvoie le nombre de 0 à n compris.

Cependant, le générateur de nombres aléatoires .Net ne satisfait pas la propriété # 2. le Random.Next(n) renvoie plutôt le nombre de 0 à n-1 inclusivement. Si vous essayez d'utiliser for-loop à l'envers, vous devrez appeler Random.Next(n+1) qui ajoute une opération supplémentaire.

Cependant, générateur de nombres aléatoires .Net a une autre fonction agréable Random.Next(a,b) ce qui renvoie a à b-1 inclusivement. Cela correspond parfaitement parfaitement à la mise en œuvre de cet algorithme qui a une boucle normale. Donc, sans plus tarder, voici la mise en œuvre 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;
}

85
2018-03-26 17:41



Méthode d'extension pour IEnumerable:

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

64
2017-08-11 08:54



    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;
    }

10
2017-11-07 21:18



MODIFIER le RemoveAt est une faiblesse dans ma version précédente. Cette solution surmonte cela.

public static IEnumerable<T> Shuffle<T>(
        this IEnumerable<T> source,
        Random generator = null)
{
    if (generator == null)
    {
        generator = new Random();
    }

    var elements = source.ToArray();
    for (var i = elements.Length - 1; i >= 0; i--)
    {
        var swapIndex = generator.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

Notez le facultatif Random generator, si la mise en œuvre du cadre de base de Random n'est pas thread-safe ou cryptographiquement assez fort pour vos besoins, vous pouvez injecter votre implémentation dans l'opération.

Une implémentation appropriée pour une sécurité cryptographique solide Randomla mise en œuvre peut être trouvée dans cette réponse.


Voici une idée, étendre IList d'une manière (espérons-le) efficace.

public static IEnumerable<T> Shuffle<T>(this IList<T> list)
{
    var choices = Enumerable.Range(0, list.Count).ToList();
    var rng = new Random();
    for(int n = choices.Count; n > 1; n--)
    {
        int k = rng.Next(n);
        yield return list[choices[k]];
        choices.RemoveAt(k);
    }

    yield return list[choices[0]];
}


8
2017-10-27 08:43



Vous pouvez réaliser cela en utilisant cette méthode d'extension simple

public static class IEnumerableExtensions
{

    public static IEnumerable<t> Randomize<t>(this IEnumerable<t> target)
    {
        Random r = new Random();

        return target.OrderBy(x=>(r.Next()));
    }        
}

et vous pouvez l'utiliser en faisant ce qui suit

// use this on any collection that implements IEnumerable!
// List, Array, HashSet, Collection, etc

List<string> myList = new List<string> { "hello", "random", "world", "foo", "bar", "bat", "baz" };

foreach (string s in myList.Randomize())
{
    Console.WriteLine(s);
}

6
2017-08-24 17:48



J'utilise habituellement:

var list = new List<T> ();
fillList (list);
var randomizedList = new List<T> ();
var rnd = new Random ();
while (list.Count != 0)
{
    var index = rnd.Next (0, list.Count);
    randomizedList.Add (list [index]);
    list.RemoveAt (index);
}

4
2017-11-07 19:35