Rendre aléatoire une liste <T>

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 numéros dans une liste à laquelle je voudrais attribuer un ordre aléatoire, afin de les dessiner pour une application de type loterie.

Mélangez tout (I)Listavec une méthode d'extension basée sur le mélange 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 les candidats à l'é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 (WayBack Machine).

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 le gros défaut idiot 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 manière prévue. Dans mon premier exemple ci-dessus, j'instancie la variable rng à l'intérieur de la méthode Shuffle, qui demande des problèmes si la méthode va être appelée à plusieurs reprises. Ci-dessous est un exemple fixe et complet basé sur un commentaire vraiment 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;
      }
    }
  }
}

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 commande les éléments par guid ...

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

Je suis un peu surpris par toutes les versions maladroites de cet algorithme simple ici. Fisher-Yates (ou Knuth shuffle) est un peu délicat mais très compact. Pourquoi est-ce difficile? Parce que vous devez faire attention à ce que votre générateur de nombres aléatoires r(a,b)renvoie une valeur où best inclus ou exclusif. J'ai également modifié la description de Wikipedia afin que les gens ne suivent pas aveuglément le pseudocode et créent des bogues difficiles à détecter. Pour .Net, Random.Next(a,b)renvoie un numéro exclusif de bso sans plus tarder, voici comment il peut être implémenté en C # /. Net:

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

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

Essayez ce code .

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

L'idée est d'obtenir un objet anonyme avec un article et un ordre aléatoire, puis de réorganiser les articles en fonction de cet ordre et de renvoyer la valeur:

var result = items.Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList()

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

EDITER C'est RemoveAtune faiblesse de ma version précédente. Cette solution permet de surmonter 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 l'option Random generator, si l'implémentation du framework de base Randomn'est pas thread-safe ou cryptographiquement assez forte pour vos besoins, vous pouvez injecter votre implémentation dans l'opération.

Une implémentation appropriée pour une implémentation cryptographique forte thread-safe Randompeut ê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]];
}

Vous pouvez y parvenir 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 procédant comme 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);
}

C'est ma méthode préférée de lecture aléatoire lorsqu'il est souhaitable de ne pas modifier l'original. C'est une variante de l' algorithme "inside-out" de Fisher – Yates qui fonctionne sur n'importe quelle séquence énumérable (la longueur de sourcen'a pas besoin d'être connue depuis le début).

public static IList<T> NextList<T>(this Random r, IEnumerable<T> source)
{
  var list = new List<T>();
  foreach (var item in source)
  {
    var i = r.Next(list.Count + 1);
    if (i == list.Count)
    {
      list.Add(item);
    }
    else
    {
      var temp = list[i];
      list[i] = item;
      list.Add(temp);
    }
  }
  return list;
}

Cet algorithme peut également être implémenté en allouant une plage de 0à length - 1et en épuisant aléatoirement les indices en échangeant l'index choisi au hasard avec le dernier index jusqu'à ce que tous les indices aient été choisis exactement une fois. Ce code ci-dessus accomplit exactement la même chose mais sans l'allocation supplémentaire. Ce qui est plutôt soigné.

En ce qui concerne la Randomclasse, c'est un générateur de nombres à usage général (et si je dirigeais une loterie, j'envisagerais d'utiliser quelque chose de différent). Il s'appuie également sur une valeur de départ basée sur le temps par défaut. Un petit soulagement du problème consiste à amorcer la Randomclasse avec le RNGCryptoServiceProviderou vous pouvez utiliser le RNGCryptoServiceProviderdans une méthode similaire à celle-ci (voir ci-dessous) pour générer des valeurs doubles à virgule flottante aléatoires uniformément choisies, mais le fonctionnement d'une loterie nécessite à peu près la compréhension du caractère aléatoire et de la nature de la source de hasard.

var bytes = new byte[8];
_secureRng.GetBytes(bytes);
var v = BitConverter.ToUInt64(bytes, 0);
return (double)v / ((double)ulong.MaxValue + 1);

Le but de générer un double aléatoire (entre 0 et 1 exclusivement) est d'utiliser pour évoluer vers une solution entière. Si vous devez choisir quelque chose dans une liste basée sur un double aléatoire, xce sera toujours 0 <= x && x < 1simple.

return list[(int)(x * list.Count)];

Prendre plaisir!

Si cela ne vous dérange pas d'en utiliser deux Lists, c'est probablement la façon la plus simple de le faire, mais probablement pas la plus efficace ou imprévisible:

List<int> xList = new List<int>() { 1, 2, 3, 4, 5 };
List<int> deck = new List<int>();

foreach (int xInt in xList)
    deck.Insert(random.Next(0, deck.Count + 1), xInt);

Si vous avez un nombre fixe (75), vous pouvez créer un tableau avec 75 éléments, puis énumérer votre liste, en déplaçant les éléments vers des positions aléatoires dans le tableau. Vous pouvez générer le mappage du numéro de liste à l'index du tableau à l'aide du shuffle Fisher-Yates .

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

    List<T> OriginalList = new List<T>();
    List<T> TempList = new List<T>();
    Random random = new Random();
    int length = OriginalList.Count;
    int TempIndex = 0;

    while (length > 0) {
        TempIndex = random.Next(0, length);  // get random value between 0 and original length
        TempList.Add(OriginalList[TempIndex]); // add to temp list
        OriginalList.RemoveAt(TempIndex); // remove from original list
        length = OriginalList.Count;  // get new list <T> length.
    }

    OriginalList = new List<T>();
    OriginalList = TempList; // copy all items from temp list to original list.

Voici un Shuffler efficace qui retourne un tableau d'octets de valeurs mélangées. Il ne mélange jamais plus que nécessaire. Il peut être redémarré là où il s'était précédemment arrêté. Mon implémentation réelle (non illustrée) est un composant MEF qui permet un shuffler de remplacement spécifié par l'utilisateur.

    public byte[] Shuffle(byte[] array, int start, int count)
    {
        int n = array.Length - start;
        byte[] shuffled = new byte[count];
        for(int i = 0; i < count; i++, start++)
        {
            int k = UniformRandomGenerator.Next(n--) + start;
            shuffled[i] = array[k];
            array[k] = array[start];
            array[start] = shuffled[i];
        }
        return shuffled;
    }

"

Voici un moyen sûr pour les threads:

public static class EnumerableExtension
{
    private static Random globalRng = new Random();

    [ThreadStatic]
    private static Random _rng;

    private static Random rng 
    {
        get
        {
            if (_rng == null)
            {
                int seed;
                lock (globalRng)
                {
                    seed = globalRng.Next();
                }
                _rng = new Random(seed);
             }
             return _rng;
         }
    }

    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> items)
    {
        return items.OrderBy (i => rng.Next());
    }
}

 public Deck(IEnumerable<Card> initialCards) 
    {
    cards = new List<Card>(initialCards);
    public void Shuffle() 
     }
    {
        List<Card> NewCards = new List<Card>();
        while (cards.Count > 0) 
        {
            int CardToMove = random.Next(cards.Count);
            NewCards.Add(cards[CardToMove]);
            cards.RemoveAt(CardToMove);
        }
        cards = NewCards;
    }

public IEnumerable<string> GetCardNames() 

{
    string[] CardNames = new string[cards.Count];
    for (int i = 0; i < cards.Count; i++)
    CardNames[i] = cards[i].Name;
    return CardNames;
}

Deck deck1;
Deck deck2;
Random random = new Random();

public Form1() 
{

InitializeComponent();
ResetDeck(1);
ResetDeck(2);
RedrawDeck(1);
 RedrawDeck(2);

}



 private void ResetDeck(int deckNumber) 
    {
    if (deckNumber == 1) 
{
      int numberOfCards = random.Next(1, 11);
      deck1 = new Deck(new Card[] { });
      for (int i = 0; i < numberOfCards; i++)
           deck1.Add(new Card((Suits)random.Next(4),(Values)random.Next(1, 14)));
       deck1.Sort();
}


   else
    deck2 = new Deck();
 }

private void reset1_Click(object sender, EventArgs e) {
ResetDeck(1);
RedrawDeck(1);

}

private void shuffle1_Click(object sender, EventArgs e) 
{
    deck1.Shuffle();
    RedrawDeck(1);

}

private void moveToDeck1_Click(object sender, EventArgs e) 
{

    if (listBox2.SelectedIndex >= 0)
    if (deck2.Count > 0) {
    deck1.Add(deck2.Deal(listBox2.SelectedIndex));

}

    RedrawDeck(1);
    RedrawDeck(2);

}

Une simple modification de la réponse acceptée qui renvoie une nouvelle liste au lieu de travailler sur place, et accepte la plus générale IEnumerable<T>comme le font de nombreuses autres méthodes Linq.

private static Random rng = new Random();

/// <summary>
/// Returns a new list where the elements are randomly shuffled.
/// Based on the Fisher-Yates shuffle, which has O(n) complexity.
/// </summary>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
    var source = list.ToList();
    int n = source.Count;
    var shuffled = new List<T>(n);
    shuffled.AddRange(source);
    while (n > 1) {
        n--;
        int k = rng.Next(n + 1);
        T value = shuffled[k];
        shuffled[k] = shuffled[n];
        shuffled[n] = value;
    }
    return shuffled;
}

J'ai trouvé une solution intéressante en ligne.

Courtoisie: https://improveandrepeat.com/2018/08/a-simple-way-to-shuffle-your-lists-in-c/

var shuffled = myList.OrderBy (x => Guid.NewGuid ()). ToList ();

Ancien poste à coup sûr, mais j'utilise juste un GUID.

Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();

Un GUID est toujours unique et puisqu'il est régénéré à chaque fois que le résultat change à chaque fois.

Une approche très simple de ce type de problème consiste à utiliser un certain nombre de permutation d'éléments aléatoires dans la liste.

En pseudo-code, cela ressemblerait à ceci:

do 
    r1 = randomPositionInList()
    r2 = randomPositionInList()
    swap elements at index r1 and index r2 
for a certain number of times