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

Mélangez une liste (I)List avec une méthode d’extension basée sur le shuffle Fisher-Yates :

 private static Random rng = new Random(); public static void Shuffle(this IList 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 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 suit:

 using System.Security.Cryptography; ... public static void Shuffle(this IList 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 simple comparaison 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 de ma comparaison. Ils ont bien sûr raison. Il n'y a rien de mal avec System.Random s'il est utilisé comme prévu. 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 doit être appelée à plusieurs resockets. Vous trouverez ci-dessous 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(ssortingng[] args) { var numbers = new List(Enumerable.Range(1, 75)); numbers.Shuffle(); Console.WriteLine("The winning numbers are: {0}", ssortingng.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(this IList 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 articles 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. Si vous allez sur Wikipedia, vous verrez une version de cet algorithme qui a pour boucle en marche arrière et beaucoup de gens ne semblent pas vraiment comprendre pourquoi c’est inversé. 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 les deux propriétés suivantes:

  1. Il accepte n comme paramètre d’entrée unique.
  2. Il renvoie le nombre de 0 à n inclus .

Cependant, le générateur de nombres aléatoires .Net ne satisfait pas à la propriété n ° 2. Random.Next(n) renvoie à la place un nombre compris entre 0 et n-1 inclus. Si vous essayez d’utiliser 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 a une autre fonction intéressante, Random.Next(a,b) qui renvoie a à b-1 inclus. Cela correspond parfaitement à l’implémentation de cet algorithme qui a une boucle normale. Donc, sans plus tarder, voici l’implémentation correcte, efficace et compacte:

 public static void Shuffle(this IList list, Random rnd) { for(var i=0; i < list.Count; i++) list.Swap(i, rnd.Next(i, list.Count)); } public static void Swap(this IList list, int i, int j) { var temp = list[i]; list[i] = list[j]; list[j] = temp; } 

Méthode d’extension pour IEnumerable:

 public static IEnumerable Randomize(this IEnumerable source) { Random rnd = new Random(); return source.OrderBy((item) => rnd.Next()); } 
  public static List Randomize(List list) { List randomizedList = new List(); 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; } 

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

 public static IEnumerable Shuffle( this IEnumerable 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 Random generator facultatif, si l’implémentation de base de Random n’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 Random cryptographiquement forte et thread-safe peut être trouvée dans cette réponse.


Voici une idée, étendez IList de manière efficace (espérons-le).

 public static IEnumerable Shuffle(this IList 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 réaliser cela en utilisant cette méthode d’extension simple

 public static class IEnumerableExtensions { public static IEnumerable Randomize(this IEnumerable 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 myList = new List { "hello", "random", "world", "foo", "bar", "bat", "baz" }; foreach (ssortingng s in myList.Randomize()) { Console.WriteLine(s); } 

J’utilise habituellement:

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

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 dans des positions aléatoires du tableau. Vous pouvez générer le mappage du numéro de liste avec l’index du tableau à l’aide du shuffle Fisher-Yates .

C’est ma méthode préférée de mélange quand il est souhaitable de ne pas modifier l’original. C’est une variante de l’ algorithme de Fisher-Yates “à l’envers” qui fonctionne sur toute séquence énumérable (la longueur de la source n’a pas besoin d’être connue au départ).

 public static IList NextList(this Random r, IEnumerable source) { var list = new List(); 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 - 1 et en épuisant aléatoirement les indices en intervertissant 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 chouette.

En ce qui concerne la classe Random , il s’agit d’un générateur de nombres à usage général (et si je courais à une loterie, j’envisagerais d’utiliser quelque chose de différent). Il s’appuie également sur une valeur de graine basée sur le temps par défaut. Une petite amélioration du problème consiste à RNGCryptoServiceProvider la classe Random avec le RNGCryptoServiceProvider ou à utiliser le RNGCryptoServiceProvider dans une méthode similaire (voir ci-dessous) pour générer des valeurs aléatoires doubles flottantes choisies uniformément. la nature de la source aléatoire.

 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 mettre à l’échelle une solution entière. Si vous avez besoin de choisir quelque chose dans une liste basée sur un double aléatoire, x va toujours être 0 <= x && x < 1 est simple.

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

Prendre plaisir!

Si cela ne vous dérange pas d’utiliser deux Lists , alors c’est probablement le moyen le plus simple de le faire, mais probablement pas le plus efficace ou le plus imprévisible:

 List xList = new List() { 1, 2, 3, 4, 5 }; List deck = new List(); foreach (int xInt in xList) deck.Insert(random.Next(0, deck.Count + 1), xInt); 

Voici un shuffler efficace qui renvoie un tableau d’octets de valeurs mélangées. Il ne mélange jamais plus que nécessaire. Il peut être redémarré à partir de là où il s’était arrêté auparavant. Mon implémentation réelle (non représentée) est un composant MEF qui autorise 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; } 

`

  public Deck(IEnumerable initialCards) { cards = new List(initialCards); public void Shuffle() } { List NewCards = new List(); while (cards.Count > 0) { int CardToMove = random.Next(cards.Count); NewCards.Add(cards[CardToMove]); cards.RemoveAt(CardToMove); } cards = NewCards; } public IEnumerable GetCardNames() { ssortingng[] CardNames = new ssortingng[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); } 

Voici un moyen sûr de faire ceci:

 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 Shuffle(this IEnumerable items) { return items.OrderBy (i => rng.Next()); } } 

Une simple modification de la réponse acceptée qui retourne une nouvelle liste au lieu de travailler sur place, et accepte le plus général IEnumerable comme beaucoup d’autres méthodes Linq.

 private static Random rng = new Random(); ///  /// Returns a new list where the elements are randomly shuffled. /// Based on the Fisher-Yates shuffle, which has O(n) complexity. ///  public static IEnumerable Shuffle(this IEnumerable list) { var source = list.ToList(); int n = source.Count; var shuffled = new List(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; } 

L’idée est d’obtenir un object anonyme avec un article et un ordre aléatoire, puis de réorganiser les éléments par 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() 

Ancien message pour vous, mais j’utilise juste un GUID.

 Items = Items.OrderBy(o => Guid.NewGuid().ToSsortingng()).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 nombre de swap 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