Sélectionner N éléments aléatoires à partir d'une List<T> en C#

Question

J'ai besoin d'un algorithme rapide pour sélectionner 5 éléments aléatoires à partir d'une liste générique. Par exemple, j'aimerais obtenir 5 éléments aléatoires d'une List.

Answer 1

Utilisation de Linq :

VotreListe.OrderBy(x => rnd.Next()).Take(5)

Answer 2

Parcourir et pour chaque élément, la probabilité de sélection = (nombre nécessaire)/(nombre restant)

Donc, si vous aviez 40 éléments, le premier aurait une chance de 5/40 d'être sélectionné. S'il l'est, le suivant a une chance de 4/39, sinon il a une chance de 5/39. À la fin, vous aurez vos 5 éléments, et souvent vous les aurez tous avant cela.

Cette technique est appelée échantillonnage de sélection, un cas particulier de Échantillonnage du réservoir. Elle est similaire en performance au mélange des données d'entrée, mais bien sûr permet à l'échantillon d'être généré sans modifier les données originales.

Answer 3

public static List GetRandomElements(this IEnumerable liste, int elementsCount)
{
    return liste.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}

Answer 4

C'est en fait un problème plus difficile que cela ne semble, principalement parce que de nombreuses solutions mathématiquement correctes échoueront à vous permettre d'atteindre toutes les possibilités (plus d'informations ci-dessous).

Tout d'abord, voici quelques solutions faciles à implémenter, correctes si vous disposez d'un générateur de nombres vraiment aléatoire :

(0) La réponse de Kyle, qui est O(n).

(1) Générez une liste de n paires [(0, rand), (1, rand), (2, rand), ...], triez-les selon la deuxième coordonnée, et utilisez les k premiers (pour vous, k=5) indices pour obtenir votre sous-ensemble aléatoire. Je pense que c'est facile à implémenter, bien que cela prenne du temps en O(n log n).

(2) Initialisez une liste vide s = [] qui contiendra les indices de k éléments aléatoires. Choisissez un nombre r dans {0, 1, 2, ..., n-1} de manière aléatoire, r = rand % n, et ajoutez-le à s. Ensuite, prenez r = rand % (n-1) et insérez-le dans s ; ajoutez à r le nombre d'éléments inférieurs à lui dans s pour éviter les collisions. Puis prenez r = rand % (n-2), et faites la même chose, etc. jusqu'à obtenir k éléments distincts dans s. Cela a un temps d'exécution dans le pire des cas de O(k^2). Donc pour k << n, cela peut être plus rapide. Si vous gardez s trié et suivez les intervalles contigus qu'il contient, vous pouvez l'implémenter en O(k log k), mais cela demande plus de travail.

@Kyle - tu as raison, poussé par l'erreur, je suis d'accord avec ta réponse. Je l'ai rapidement lue au début, et j'ai pensé à tort que tu indiquais de choisir séquentiellement chaque élément avec une probabilité fixe k/n, ce qui aurait été faux - mais ton approche adaptative me semble correcte. Désolé pour ça.

D'accord, et maintenant, pour la surprise : asymptotiquement (pour k fixé, n croissant), il y a n^k/k! choix de sous-ensemble de k éléments parmi n éléments [c'est une approximation de (n choose k)]. Si n est grand et que k n'est pas très petit, alors ces nombres sont énormes. La meilleure longueur de cycle que vous pouvez espérer dans n'importe quel générateur de nombres aléatoires standard sur 32 bits est 2^32 = 256^4. Donc si nous avons une liste de 1000 éléments et que nous voulons en choisir 5 au hasard, il n'y a aucun moyen pour un générateur de nombres aléatoires standard d'atteindre toutes les possibilités. Cependant, tant que vous acceptez un choix qui fonctionne bien pour des ensembles plus petits, et qui semble toujours aléatoire, alors ces algorithmes devraient être bons.

Addendum : Après avoir écrit cela, j'ai réalisé qu'il est difficile de mettre en œuvre l'idée (2) correctement, donc je voulais clarifier cette réponse. Pour obtenir un temps en O(k log k), vous avez besoin d'une structure de type tableau qui prend en charge des recherches et des insertions en O(log m) - un arbre binaire équilibré peut le faire. En utilisant une telle structure pour construire un tableau appelé s, voici un pseudocode en python :

# Retourne un conteneur s avec k nombres aléatoires distincts de {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # Peut être 0, doit être < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # C'est la recherche.
    s.InsertInOrder(q ? r + q : r + len(s))   # Insère juste avant q.
  return s

Je suggère de parcourir quelques cas d'exemple pour voir comment cela implémente efficacement l'explication ci-dessus en anglais.

Answer 5

Je pense que la réponse sélectionnée est correcte et assez astucieuse. Cependant, je l'ai implémentée différemment, car je voulais aussi que le résultat soit dans un ordre aléatoire.

    static IEnumerable PickSomeInRandomOrder(
        IEnumerable someTypes,
        int maxCount)
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary randomSortTable = new Dictionary();

        foreach(SomeType someType in someTypes)
            randomSortTable[random.NextDouble()] = someType;

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }