Meilleur moyen de randomiser un tableau avec .NET

Quelle est la meilleure façon de randomiser un tableau de chaînes avec .NET? Mon tableau contient environ 500 chaînes et j'aimerais en créer une nouvelle Arrayavec les mêmes chaînes mais dans un ordre aléatoire.

Veuillez inclure un exemple C # dans votre réponse.

Si vous êtes sur .NET 3.5, vous pouvez utiliser la fraîcheur IEnumerable suivante (VB.NET, pas C #, mais l'idée doit être claire ...):

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();    

Edit: OK et voici le code VB.NET correspondant:

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

Deuxième modification, en réponse aux remarques selon lesquelles System.Random "n'est pas threadsafe" et "ne convient que pour les applications de jouets" en raison du retour d'une séquence temporelle: comme utilisé dans mon exemple, Random () est parfaitement thread-safe, sauf si vous permettez à la routine dans laquelle vous randomisez le tableau d'être ré-entrée, auquel cas vous aurez besoin de quelque chose comme de lock (MyRandomArray)toute façon afin de ne pas corrompre vos données, ce qui protégera rndégalement.

En outre, il faut bien comprendre que System.Random en tant que source d'entropie n'est pas très puissant. Comme indiqué dans la documentation MSDN , vous devez utiliser quelque chose dérivé de System.Security.Cryptography.RandomNumberGeneratorsi vous faites quelque chose lié à la sécurité. Par exemple:

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

L'implémentation suivante utilise l' algorithme Fisher-Yates AKA the Knuth Shuffle. Elle s'exécute en un temps O (n) et se mélange sur place, elle est donc plus performante que la technique de «tri aléatoire», bien qu'elle comporte plus de lignes de code. Voir ici pour quelques mesures de performances comparatives. J'ai utilisé System.Random, ce qui convient à des fins non cryptographiques. *

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

Usage:

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* Pour des tableaux plus longs, afin de rendre le nombre (extrêmement grand) de permutations également probable, il serait nécessaire d'exécuter un générateur de nombres pseudo-aléatoires (PRNG) à travers de nombreuses itérations pour chaque swap pour produire suffisamment d'entropie. Pour un tableau de 500 éléments, seule une très petite fraction des 500 possibles! il sera possible d'obtenir des permutations à l'aide d'un PRNG. Néanmoins, l'algorithme de Fisher-Yates est impartial et par conséquent, le mélange sera aussi bon que le RNG que vous utilisez.

Vous recherchez un algorithme de brassage, non?

D'accord, il y a deux façons de le faire: l'intelligent-mais-les-gens-semblent toujours-mal comprendre-et-se tromper-alors-peut-être-ce-pas-si-intelligent-après-tout façon, et la manière stupide-comme-roches-mais-qui-s'en soucie-parce-que-cela-fonctionne.

Manière stupide

• Créez un double de votre premier tableau, mais marquez chaque chaîne avec un nombre aléatoire.
• Triez le tableau en double par rapport au nombre aléatoire.

Cet algorithme fonctionne bien, mais assurez-vous que votre générateur de nombres aléatoires est peu susceptible de marquer deux chaînes avec le même numéro. En raison du soi-disant paradoxe d'anniversaire , cela se produit plus souvent que vous ne le pensez. Sa complexité temporelle est O ( n log n ).

Manière intelligente

Je vais décrire cela comme un algorithme récursif:

Pour mélanger un tableau de taille n (index dans la plage [0 .. n -1]):

si n = 0

• ne fais rien

si n > 0

• (étape récursive) mélange les n -1 premiers éléments du tableau
• choisissez un index aléatoire, x , dans la plage [0 .. n -1]
• permuter l'élément à l'index n -1 avec l'élément à l'index x

L'équivalent itératif est de parcourir un itérateur dans le tableau, en échangeant avec des éléments aléatoires au fur et à mesure, mais notez que vous ne pouvez pas échanger avec un élément après celui vers lequel l'itérateur pointe. Il s'agit d'une erreur très courante et conduit à un mélange biaisé.

La complexité temporelle est O ( n ).

Cet algorithme est simple mais pas efficace, O (N ² ). Tous les algorithmes «order by» sont typiquement O (N log N). Cela ne fait probablement pas de différence en dessous de centaines de milliers d'éléments, mais ce serait le cas pour de grandes listes.

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

La raison pour laquelle c'est O (N ² ) est subtile: List.RemoveAt () est une opération O (N) sauf si vous supprimez dans l'ordre à partir de la fin.

Vous pouvez également créer une méthode d'extension avec Matt Howells. Exemple.

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

Ensuite, vous pouvez simplement l'utiliser comme:

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

La randomisation du tableau est intensive car vous devez déplacer un groupe de chaînes. Pourquoi ne pas simplement lire au hasard à partir du tableau? Dans le pire des cas, vous pouvez même créer une classe wrapper avec un getNextString (). Si vous avez vraiment besoin de créer un tableau aléatoire, vous pouvez faire quelque chose comme

for i = 0 -> i= array.length * 5
   swap two strings in random places

Le * 5 est arbitraire.

En pensant simplement du haut de ma tête, vous pouvez faire ceci:

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

Générez un tableau de nombres flottants ou entiers aléatoires de même longueur. Triez ce tableau et effectuez les échanges correspondants sur votre tableau cible.

Cela donne un tri vraiment indépendant.

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

Jacco, votre solution est un IComparer personnalisé n'est pas sûr. Les routines de tri exigent que le comparateur se conforme à plusieurs exigences pour fonctionner correctement. Le premier d'entre eux est la cohérence. Si le comparateur est appelé sur la même paire d'objets, il doit toujours renvoyer le même résultat. (la comparaison doit également être transitive).

Le non-respect de ces exigences peut entraîner un certain nombre de problèmes dans la routine de tri, y compris la possibilité d'une boucle infinie.

En ce qui concerne les solutions qui associent une valeur numérique aléatoire à chaque entrée, puis trient par cette valeur, elles conduisent à un biais inhérent à la sortie car chaque fois que deux entrées se voient attribuer la même valeur numérique, le caractère aléatoire de la sortie sera compromis. (Dans une routine de tri "stable", celui qui est le premier dans l'entrée sera le premier dans la sortie. Array.Sort n'est pas stable, mais il y a toujours un biais basé sur le partitionnement effectué par l'algorithme Quicksort).

Vous devez réfléchir au niveau d'aléa dont vous avez besoin. Si vous exploitez un site de poker où vous avez besoin de niveaux cryptographiques d'aléatoire pour vous protéger contre un attaquant déterminé, vous avez des exigences très différentes de celles de quelqu'un qui veut juste randomiser une playlist de chansons.

Pour la lecture aléatoire de la liste de chansons, il n'y a aucun problème à utiliser un PRNG prédéfini (comme System.Random). Pour un site de poker, ce n'est même pas une option et vous devez penser au problème beaucoup plus dur que quiconque ne le fera pour vous sur stackoverflow. (l'utilisation d'un RNG cryptographique n'est que le début, vous devez vous assurer que votre algorithme n'introduit pas de biais, que vous disposez de sources d'entropie suffisantes et que vous n'exposez aucun état interne qui compromettrait le hasard ultérieur).

Ce message a déjà été assez bien répondu - utilisez une implémentation Durstenfeld du shuffle Fisher-Yates pour un résultat rapide et impartial. Certaines implémentations ont même été publiées, même si je note que certaines sont en fait incorrectes.

J'ai écrit quelques articles il y a quelque temps sur la mise en œuvre de mélanges complets et partiels à l'aide de cette technique , et (ce deuxième lien est l'endroit où j'espère ajouter de la valeur) également un article de suivi sur la façon de vérifier si votre implémentation est impartiale , qui peut être utilisé pour vérifier n'importe quel algorithme de lecture aléatoire. Vous pouvez voir à la fin du deuxième message l'effet d'une simple erreur dans la sélection de nombres aléatoires peut faire.

Ok, c'est clairement une bosse de mon côté (s'excuse ...), mais j'utilise souvent une méthode assez générale et cryptographiquement forte.

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

Shuffle () est une extension sur n'importe quel IEnumerable donc obtenir, par exemple, des nombres de 0 à 1000 dans un ordre aléatoire dans une liste peut être fait avec

Enumerable.Range(0,1000).Shuffle().ToList()

Cette méthode ne donnera pas non plus de surprises en matière de tri, car la valeur de tri est générée et mémorisée exactement une fois par élément de la séquence.

Vous n'avez pas besoin d'algorithmes compliqués.

Juste une ligne simple:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

Notez que nous devons convertir le premier en Arrayun Listpremier, si vous ne l'utilisez pas Listen premier lieu.

Notez également que ce n'est pas efficace pour les très grands tableaux! Sinon, c'est propre et simple.

Il s'agit d'une solution de console de travail complète basée sur l'exemple fourni ici :

class Program
{
    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };

    static void Main()
    {
        var result = Shuffle(words1);
        foreach (var i in result)
        {
            Console.Write(i + " ");
        }
        Console.ReadKey();
    }

   static string[] Shuffle(string[] wordArray) {
        Random random = new Random();
        for (int i = wordArray.Length - 1; i > 0; i--)
        {
            int swapIndex = random.Next(i + 1);
            string temp = wordArray[i];
            wordArray[i] = wordArray[swapIndex];
            wordArray[swapIndex] = temp;
        }
        return wordArray;
    }         
}

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();

Voici un moyen simple d'utiliser OLINQ:

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }  
    return sortedList;
}