Meilleure façon de randomiser un tableau de chaînes avec .NET

Question

Quel est le meilleur moyen de randomiser un tableau de chaînes avec .NET? Mon tableau contient environ 500 chaînes et j'aimerais créer un nouveau Array avec les mêmes chaînes mais dans un ordre aléatoire.

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

Answer 1

La suite de la mise en œuvre utilise le Fisher-Yates algorithme. Il s'exécute en O(n) le temps et le mélange en place, donc, est plus performant que le tri par hasard, à la technique, même si c'est plus de lignes de code. Voir ici pour quelques comparative des mesures de performances. J'ai utilisé le Système.Aléatoire, ce qui est bien pour les 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;
        }
    }
}

Utilisation:

var array = new int[] {1, 2, 3, 4};
new Random().Shuffle(array);

* Pour plus de tableaux, afin de rendre le (très grand) nombre de permutations tout aussi probable qu'il serait nécessaire d'exécuter un générateur de nombres pseudo aléatoires (PRNG) à travers un nombre d'itérations pour chaque swap de produire suffisamment d'entropie. Pour un de 500 éléments de la matrice de seulement une très petite fraction de la possible 500! permutations sera possible d'obtenir l'aide d'un GÉNÉRATEUR. Néanmoins, l'étude de Fisher-Yates algorithme est impartial et, par conséquent, le shuffle sera aussi bon que le RNG que vous utilisez.

Answer 2

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

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

Edit: OK et voici le code C# correspondant:

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

Seconde édition, en réponse à des remarques de ce Système.Au hasard "n'est pas thread-safe" et "ne convient que pour jouet apps" en raison de retour d'un temps-en fonction de la séquence: comme utilisé dans mon exemple, Random() est parfaitement thread-safe, sauf si vous êtes en permettant la routine dans laquelle vous rendre aléatoire le tableau de saisir de nouveau, dans ce cas, vous aurez besoin de quelque chose comme lock (MyRandomArray) de toute façon, afin de ne pas corrompre vos données, ce qui permettra de protéger rnd .

Aussi, il convient de bien comprendre ce Système.Aléatoire comme source d'entropie n'est pas très forte. Comme indiqué dans la documentation MSDN, vous devriez utiliser quelque chose dérivée d' System.Security.Cryptography.RandomNumberGenerator si vous faites quoi que ce soit 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]);
    }

Answer 3

Voir les articles de Jeff Atwood sur le brassage et celui où il a trouvé une erreur dans son propre code de brassage naïf

Cela doit me gagner une certaine réputation;)

Answer 4

Vous êtes à la recherche d'un réarrangement de l'algorithme, droit?

Bon, il y a deux façons de le faire: l'clever-but-people-always-seem-to-misunderstand-it-and-get-it-wrong-so-maybe-its-not-that-clever-after-de toutes façon, et le muet-comme-les rochers-mais-qui-fout-car-il-d'œuvres.

Muet façon

• Créer un double de votre premier tableau, mais étiquette de chaque chaîne doit avec un nombre aléatoire.
• Trier les doublons tableau concernant le nombre aléatoire.

Cet algorithme fonctionne bien, mais assurez-vous que votre générateur de nombre aléatoire est peu probable que la balise de deux chaînes avec le même numéro. En raison de la soi-disant Paradoxe d'Anniversaire, ce qui arrive plus souvent que vous pourriez vous attendre. Son temps de la complexité est O(n log n).

Manière intelligente

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

Mélanger un tableau de taille n (indices dans l'intervalle [0..n-1]):

si n = 0

• ne rien faire

si n > 0

• (récursif étape) shuffle le premier n-1 éléments du tableau
• choisissez un hasard index, x, dans l'intervalle [0..n-1]
• swap de l'élément à l'indice n-1 avec l'élément à l'indice de x

L'itératif est équivalent à marcher un itérateur à travers le tableau, en l'échangeant avec des éléments aléatoires comme vous allez le long, mais notez que vous ne pouvez pas permuter avec un élément après l'un que l'itérateur pointe. C'est une erreur très commune, et conduit à la partialité de l'aléatoire.

Le temps de la complexité est O(n).

Answer 5

List<string> stringlist = new List<string>();

// add your values to stringlist

Random r = new Random();

List<string> res = new List<string>();

while (stringlist.Length >0)
{
   int i = r.GetNext(stringlist.Length);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}