Sélectionnez N éléments aléatoires dans une liste <T> en C #

158

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

JC Grubbs
la source
12
Par aléatoire, voulez-vous dire inclusif ou exclusif? IOW, le même élément peut-il être sélectionné plus d'une fois? (vraiment aléatoire) Ou une fois qu'un élément est sélectionné, ne devrait-il plus être sélectionné dans le pool disponible?
Pretzel

Réponses:

127

Itérer à travers et pour chaque élément faire la probabilité de sélection = (nombre nécessaire) / (nombre à gauche)

Donc, si vous aviez 40 éléments, le premier aurait 5/40 de chances d'être sélectionné. Si c'est le cas, le suivant a une chance de 4/39, sinon il a une chance de 5/39. Au moment où vous arriverez à la fin, vous aurez vos 5 objets, et souvent vous les aurez tous avant cela.

Kyle Cronin
la source
33
Je pense que c'est subtilement faux. Il semble que le back-end de la liste sera choisi plus souvent que le front-end car le back-end verra des probabilités beaucoup plus grandes. Par exemple, si les 35 premiers numéros ne sont pas sélectionnés, les 5 derniers numéros doivent être sélectionnés. Le premier numéro ne verra jamais qu'une chance de 5/40, mais ce dernier numéro verra 1/1 plus souvent que 5/40 fois. Vous devrez d'abord randomiser la liste avant d'implémenter cet algorithme.
Ankur Goel
23
ok, j'ai exécuté cet algorithme 10 millions de fois sur une liste de 40 éléments, chacun avec un tir 5/40 (.125) pour être sélectionné, puis j'ai exécuté cette simulation plusieurs fois. Il s'avère que ce n'est pas réparti uniformément. Les éléments 16 à 22 sont sous-sélectionnés (16 = .123, 17 = .124), tandis que l'élément 34 est sur-sélectionné (34 = .129). Les éléments 39 et 40 sont également sous-sélectionnés mais pas autant (39 = .1247, 40 = .1246)
Ankur Goel
22
@Ankur: Je ne pense pas que ce soit statistiquement significatif. Je crois qu'il existe une preuve inductive que cela fournira une distribution uniforme.
récursif le
9
J'ai répété le même essai 100 millions de fois, et dans mon essai, l'élément le moins choisi a été choisi moins de 0,106% moins fréquemment que l'élément le plus fréquemment choisi.
récursif le
5
@recursive: La preuve est presque triviale. Nous savons comment sélectionner K éléments sur K pour tout K et comment sélectionner 0 élément sur N pour tout N. Supposons que nous connaissons une méthode pour sélectionner uniformément K ou K-1 éléments sur N-1> = K; Ensuite, nous pouvons sélectionner K éléments sur N en sélectionnant le premier élément avec la probabilité K / N, puis en utilisant la méthode connue pour sélectionner les éléments K ou K-1 encore nécessaires parmi les N-1 restants.
Ilmari Karonen
216

Utilisation de linq:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
la source
2
+1 Mais si deux éléments obtiennent le même nombre de rnd.Next () ou similaire, alors le premier sera sélectionné et le second ne le sera peut-être pas (si aucun autre élément n'est nécessaire). Cependant, il est suffisamment aléatoire en fonction de l'utilisation.
Lasse Espeholt
8
Je pense que l'ordre par est O (n log (n)), donc je choisirais cette solution si la simplicité du code est la principale préoccupation (c'est-à-dire avec de petites listes).
Guido
2
Mais n'est-ce pas énumérer et trier toute la liste? Sauf si, par "rapide", OP signifie "facile", pas "performant" ...
drzaus
2
Cela ne fonctionnera que si OrderBy () n'appelle le sélecteur de clé qu'une seule fois pour chaque élément. S'il l'appelle chaque fois qu'il veut effectuer une comparaison entre deux éléments, il récupérera une valeur différente à chaque fois, ce qui gâchera le tri. La [documentation] ( msdn.microsoft.com/en-us/library/vstudio/… ) ne dit pas ce qu'elle fait.
Oliver Bock
2
Faites attention s'il y YourLista beaucoup d'articles mais que vous ne voulez en sélectionner que quelques-uns. Dans ce cas, ce n'est pas une manière efficace de le faire.
Callum Watkins
39
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
vag
la source
27

C'est en fait un problème plus difficile qu'il n'y paraît, principalement parce que de nombreuses solutions mathématiquement correctes ne vous permettront pas d'atteindre toutes les possibilités (plus d'informations ci-dessous).

Tout d'abord, voici un générateur de nombres simples à mettre en œuvre, correct-si-vous-avez-un-vraiment-aléatoire:

(0) 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 par la deuxième coordonnée, et utilisez le premier k (pour vous, k = 5) indices pour obtenir votre sous-ensemble aléatoire. Je pense que c'est facile à mettre en œuvre, bien qu'il soit temps O (n log n).

(2) Initier une liste vide s = [] qui deviendra les indices de k éléments aléatoires. Choisissez un nombre r dans {0, 1, 2, ..., n-1} au hasard, r = rand% n, et ajoutez-le à s. Ensuite, prenez r = rand% (n-1) et restez dans s; ajoutez à r les # éléments inférieurs à s pour éviter les collisions. Ensuite, prenez r = rand% (n-2), et faites la même chose, etc. jusqu'à ce que vous ayez k éléments distincts dans s. Cela a le pire des cas d'exécution O (k ^ 2). Donc pour k << n, cela peut être plus rapide. Si vous gardez s trié et suivez les intervalles contigus dont il dispose, vous pouvez l'implémenter dans O (k log k), mais c'est plus de travail.

@Kyle - vous avez raison, après réflexion, je suis d'accord avec votre réponse. Je l'ai lu à la hâte au début, et j'ai cru à tort que vous indiquiez de choisir séquentiellement chaque élément avec une probabilité fixe k / n, ce qui aurait été faux - mais votre approche adaptative me semble correcte. Désolé pour ça.

Ok, et maintenant pour le kicker: asymptotiquement (pour k fixe, n croissant), il y a n ^ k / k! choix de k sous-ensemble d'éléments parmi n éléments [c'est une approximation de (n choisissent k)]. Si n est grand et k n'est pas très petit, alors ces nombres sont énormes. La meilleure durée de cycle que vous pouvez espérer dans tout générateur de nombres aléatoires standard de 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 qu'un générateur de nombres aléatoires standard atteigne toutes les possibilités. Cependant, tant que vous êtes d'accord avec un choix qui fonctionne bien pour des ensembles plus petits, et qui "semble" toujours aléatoire, alors ces algorithmes devraient être corrects.

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

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

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

Tyler
la source
2
pour (1) vous pouvez mélanger une liste plus rapidement que le tri, pour (2) vous allez biaiser votre distribution en utilisant%
jk.
Compte tenu de l'objection que vous avez soulevée au sujet de la durée du cycle d'un RNG, est - il possible que nous pouvons construire un algorithme qui choisira tous les jeux avec une probabilité égale?
Jonah du
Pour (1), pour améliorer le O (n log (n)), vous pouvez utiliser le tri par sélection pour trouver les k plus petits éléments. Cela fonctionnera en O (n * k).
Jared
@Jonah: Je pense que oui. Supposons que nous puissions combiner plusieurs générateurs de nombres aléatoires indépendants pour en créer un plus grand ( crypto.stackexchange.com/a/27431 ). Ensuite, vous avez juste besoin d'une plage suffisamment large pour gérer la taille de la liste en question.
Jared
16

Je pense que la réponse choisie est correcte et assez douce. Je l'ai implémenté différemment, car je voulais également le résultat dans un ordre aléatoire.

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

        Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();

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

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }
Frank Schwieterman
la source
IMPRESSIONNANT! M'a vraiment aidé!
Armstrongest
1
Avez-vous une raison de ne pas utiliser le nouveau Random () qui est basé sur Environment.TickCount vs DateTime.Now.Millisecond?
Lasse Espeholt
Non, je ne savais tout simplement pas que la valeur par défaut existait.
Frank Schwieterman
2
OK, un an de retard mais ... Cela ne correspond-il pas à la réponse plutôt courte de @ ersin, et n'échouera-t-il pas si vous obtenez un nombre aléatoire répété (où Ersin aura un biais vers le premier élément d'une paire répétée)
Andiih
1
Random random = new Random(DateTime.Now.Millisecond);à chaque appel est définitivement faux. La création d'une nouvelle instance de Randomchaque fois réduit le caractère aléatoire réel. Utilisez une static readonlyinstance de celui-ci, de préférence construite avec le constructeur par défaut.
jpmc26
12

Je viens de rencontrer ce problème, et quelques recherches supplémentaires sur Google m'ont amené au problème de la lecture aléatoire d'une liste: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Pour mélanger complètement au hasard votre liste (en place), procédez comme suit:

Pour mélanger un tableau a de n éléments (indices 0..n-1):

  for i from n  1 downto 1 do
       j  random integer with 0  j  i
       exchange a[j] and a[i]

Si vous n'avez besoin que des 5 premiers éléments, alors au lieu d'exécuter i complètement de n-1 à 1, il vous suffit de l'exécuter vers n-5 (c'est-à-dire: n-5)

Disons que vous avez besoin de k articles,

Cela devient:

  for (i = n  1; i >= n-k; i--)
  {
       j = random integer with 0  j  i
       exchange a[j] and a[i]
  }

Chaque élément sélectionné est permuté vers la fin du tableau, de sorte que les k éléments sélectionnés sont les k derniers éléments du tableau.

Cela prend du temps O (k), où k est le nombre d'éléments sélectionnés au hasard dont vous avez besoin.

De plus, si vous ne souhaitez pas modifier votre liste initiale, vous pouvez écrire tous vos swaps dans une liste temporaire, inverser cette liste et les appliquer à nouveau, effectuant ainsi l'ensemble inverse des swaps et vous renvoyant votre liste initiale sans changer le temps de fonctionnement O (k).

Enfin, pour le vrai stickler, si (n == k), vous devriez vous arrêter à 1, pas à nk, car l'entier choisi au hasard sera toujours 0.

Dhakim
la source
Je l'ai implémenté en utilisant C # dans mon article de blog: vijayt.com/post/random-select-using-fisher-yates-algorithm . J'espère que cela aide quelqu'un à la recherche de la méthode C #.
vijayst
9

Vous pouvez l'utiliser mais la commande se fera côté client

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Marwan Roushdy
la source
D'accord. Ce n'est peut-être pas le plus performant ou le plus aléatoire, mais pour la grande majorité des gens, ce sera suffisant.
Richiban
Évalué parce que les guides sont garantis uniques et non aléatoires .
Theodor Zoulias
8

From Dragons in the Algorithm , une interprétation en C #:

int k = 10; // items to select
var items = new List<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
var selected = new List<int>();
double needed = k;
double available = items.Count;
var rand = new Random();
while (selected.Count < k) {
   if( rand.NextDouble() < needed / available ) {
      selected.Add(items[(int)available-1])
      needed--;
   }
   available--;
}

Cet algorithme sélectionnera des indices uniques de la liste des éléments.

Spoulson
la source
N'obtenez que suffisamment d'éléments dans la liste, mais pas au hasard.
culithay
2
Cette implémentation est cassée car l'utilisation des varrésultats neededet les availabledeux étant des entiers, ce qui fait needed/availabletoujours 0.
Niko
1
Cela semble être une mise en œuvre de la réponse acceptée.
DCShannon
6

La sélection de N éléments aléatoires dans un groupe ne devrait rien avoir à voir avec l' ordre ! Le hasard est une question d'imprévisibilité et non de réorganisation des positions dans un groupe. Toutes les réponses qui traitent d'une sorte de commande sont forcément moins efficaces que celles qui ne le font pas. Puisque l'efficacité est la clé ici, je publierai quelque chose qui ne change pas trop l'ordre des éléments.

1) Si vous avez besoin de vraies valeurs aléatoires, ce qui signifie qu'il n'y a aucune restriction sur les éléments à choisir (c'est-à-dire qu'une fois que l'élément choisi peut être resélectionné):

public static List<T> GetTrueRandom<T>(this IList<T> source, int count, 
                                       bool throwArgumentOutOfRangeException = true)
{
    if (throwArgumentOutOfRangeException && count > source.Count)
        throw new ArgumentOutOfRangeException();

    var randoms = new List<T>(count);
    randoms.AddRandomly(source, count);
    return randoms;
}

Si vous désactivez l'indicateur d'exception, vous pouvez choisir des éléments aléatoires un nombre illimité de fois.

Si vous avez {1, 2, 3, 4}, alors il peut donner {1, 4, 4}, {1, 4, 3} etc pour 3 éléments ou même {1, 4, 3, 2, 4} pour 5 éléments!

Cela devrait être assez rapide, car il n'y a rien à vérifier.

2) Si vous avez besoin de membres individuels du groupe sans répétition, alors je me fierais à un dictionnaire (comme beaucoup l'ont déjà souligné).

public static List<T> GetDistinctRandom<T>(this IList<T> source, int count)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    if (count == source.Count)
        return new List<T>(source);

    var sourceDict = source.ToIndexedDictionary();

    if (count > source.Count / 2)
    {
        while (sourceDict.Count > count)
            sourceDict.Remove(source.GetRandomIndex());

        return sourceDict.Select(kvp => kvp.Value).ToList();
    }

    var randomDict = new Dictionary<int, T>(count);
    while (randomDict.Count < count)
    {
        int key = source.GetRandomIndex();
        if (!randomDict.ContainsKey(key))
            randomDict.Add(key, sourceDict[key]);
    }

    return randomDict.Select(kvp => kvp.Value).ToList();
}

Le code est un peu plus long que les autres approches de dictionnaire ici parce que je suis non seulement en train d'ajouter, mais aussi de supprimer de la liste, donc c'est un peu deux boucles. Vous pouvez voir ici que je n'ai rien réordonné du tout quand countdevient égal à source.Count. C'est parce que je pense que le hasard devrait être dans l' ensemble renvoyé dans son ensemble . Je veux dire si vous voulez 5 éléments aléatoires 1, 2, 3, 4, 5, il ne devrait pas question si son 1, 3, 4, 2, 5ou 1, 2, 3, 4, 5, mais si vous avez besoin de 4 articles de la même série, il devrait céder en imprévisiblement 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4etc. En second lieu , lorsque le nombre d'éléments aléatoires à renvoyé représente plus de la moitié du groupe d'origine, il est alors plus facile à supprimersource.Count - countéléments du groupe que d’ajouter des countéléments. Pour des raisons de performances, j'ai utilisé sourceau lieu de sourceDictpour obtenir un index aléatoire dans la méthode remove.

Donc, si vous avez {1, 2, 3, 4}, cela peut aboutir à {1, 2, 3}, {3, 4, 1} etc. pour 3 éléments.

3) Si vous avez besoin de valeurs aléatoires vraiment distinctes de votre groupe en prenant en compte les doublons dans le groupe d'origine, vous pouvez utiliser la même approche que ci-dessus, mais un HashSetsera plus léger qu'un dictionnaire.

public static List<T> GetTrueDistinctRandom<T>(this IList<T> source, int count, 
                                               bool throwArgumentOutOfRangeException = true)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    var set = new HashSet<T>(source);

    if (throwArgumentOutOfRangeException && count > set.Count)
        throw new ArgumentOutOfRangeException();

    List<T> list = hash.ToList();

    if (count >= set.Count)
        return list;

    if (count > set.Count / 2)
    {
        while (set.Count > count)
            set.Remove(list.GetRandom());

        return set.ToList();
    }

    var randoms = new HashSet<T>();
    randoms.AddRandomly(list, count);
    return randoms.ToList();
}

La randomsvariable est créée HashSetpour éviter l'ajout de doublons dans le plus rare des cas les plus rares où Random.Nextpeut produire la même valeur, en particulier lorsque la liste d'entrée est petite.

Donc {1, 2, 2, 4} => 3 éléments aléatoires => {1, 2, 4} et jamais {1, 2, 2}

{1, 2, 2, 4} => 4 éléments aléatoires => exception !! ou {1, 2, 4} selon le jeu d'indicateurs.

Certaines des méthodes d'extension que j'ai utilisées:

static Random rnd = new Random();
public static int GetRandomIndex<T>(this ICollection<T> source)
{
    return rnd.Next(source.Count);
}

public static T GetRandom<T>(this IList<T> source)
{
    return source[source.GetRandomIndex()];
}

static void AddRandomly<T>(this ICollection<T> toCol, IList<T> fromList, int count)
{
    while (toCol.Count < count)
        toCol.Add(fromList.GetRandom());
}

public static Dictionary<int, T> ToIndexedDictionary<T>(this IEnumerable<T> lst)
{
    return lst.ToIndexedDictionary(t => t);
}

public static Dictionary<int, T> ToIndexedDictionary<S, T>(this IEnumerable<S> lst, 
                                                           Func<S, T> valueSelector)
{
    int index = -1;
    return lst.ToDictionary(t => ++index, valueSelector);
}

Si tout est question de performances avec des dizaines de milliers d'éléments de la liste devant être répétés 10000 fois, vous voudrez peut-être avoir une classe aléatoire plus rapide que System.Random, mais je ne pense pas que ce soit un gros problème étant donné que ce dernier n'est probablement jamais un goulot d'étranglement, c'est assez rapide.

Edit: Si vous avez également besoin de réorganiser l'ordre des articles retournés, rien ne peut battre l' approche Fisher-Yates de Dhakim - bref, doux et simple.

nawfal
la source
6

Je pensais au commentaire de @JohnShedletsky sur la réponse acceptée concernant (paraphrase):

vous devriez pouvoir le faire en O (subset.Length), plutôt qu'en O (originalList.Length)

En gros, vous devriez pouvoir générer subsetdes indices aléatoires, puis les extraire de la liste d'origine.

La méthode

public static class EnumerableExtensions {

    public static Random randomizer = new Random(); // you'd ideally be able to replace this with whatever makes you comfortable

    public static IEnumerable<T> GetRandom<T>(this IEnumerable<T> list, int numItems) {
        return (list as T[] ?? list.ToArray()).GetRandom(numItems);

        // because ReSharper whined about duplicate enumeration...
        /*
        items.Add(list.ElementAt(randomizer.Next(list.Count()))) ) numItems--;
        */
    }

    // just because the parentheses were getting confusing
    public static IEnumerable<T> GetRandom<T>(this T[] list, int numItems) {
        var items = new HashSet<T>(); // don't want to add the same item twice; otherwise use a list
        while (numItems > 0 )
            // if we successfully added it, move on
            if( items.Add(list[randomizer.Next(list.Length)]) ) numItems--;

        return items;
    }

    // and because it's really fun; note -- you may get repetition
    public static IEnumerable<T> PluckRandomly<T>(this IEnumerable<T> list) {
        while( true )
            yield return list.ElementAt(randomizer.Next(list.Count()));
    }

}

Si vous vouliez être encore plus efficace, vous utiliseriez probablement l'un HashSetdes indices , pas les éléments de liste réels (au cas où vous auriez des types complexes ou des comparaisons coûteuses);

Le test unitaire

Et pour nous assurer que nous n'avons aucune collision, etc.

[TestClass]
public class RandomizingTests : UnitTestBase {
    [TestMethod]
    public void GetRandomFromList() {
        this.testGetRandomFromList((list, num) => list.GetRandom(num));
    }

    [TestMethod]
    public void PluckRandomly() {
        this.testGetRandomFromList((list, num) => list.PluckRandomly().Take(num), requireDistinct:false);
    }

    private void testGetRandomFromList(Func<IEnumerable<int>, int, IEnumerable<int>> methodToGetRandomItems, int numToTake = 10, int repetitions = 100000, bool requireDistinct = true) {
        var items = Enumerable.Range(0, 100);
        IEnumerable<int> randomItems = null;

        while( repetitions-- > 0 ) {
            randomItems = methodToGetRandomItems(items, numToTake);
            Assert.AreEqual(numToTake, randomItems.Count(),
                            "Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);
            if(requireDistinct) Assert.AreEqual(numToTake, randomItems.Distinct().Count(),
                            "Collisions (non-unique values) found, failed at {0} repetition--", repetitions);
            Assert.IsTrue(randomItems.All(o => items.Contains(o)),
                        "Some unknown values found; failed at {0} repetition--", repetitions);
        }
    }
}
drzaus
la source
2
Bonne idée, avec des problèmes. (1) Si votre liste plus grande est énorme (lue à partir d'une base de données, par exemple) alors vous réalisez la liste entière, qui peut dépasser la mémoire. (2) Si K est proche de N, vous vous débatterez beaucoup à la recherche d'un index non réclamé dans votre boucle, ce qui obligera le code à exiger un laps de temps imprévisible. Ces problèmes peuvent être résolus.
Paul Chernoch
1
Ma solution au problème de la raclée est la suivante: si K <N / 2, faites-le à votre façon. Si K> = N / 2, choisissez les indices qui ne doivent PAS être conservés, au lieu de ceux qui doivent être conservés. Il y a encore des raclées, mais beaucoup moins.
Paul Chernoch
A également remarqué que cela modifie l'ordre des éléments énumérés, ce qui peut être acceptable dans certaines situations, mais pas dans d'autres.
Paul Chernoch
En moyenne, pour K = N / 2 (le pire des cas pour l'amélioration suggérée par Paul), l'algorithme (amélioré) semble prendre ~ 0,693 * N itérations. Maintenant, faites une comparaison de vitesse. Est-ce mieux que la réponse acceptée? Pour quelles tailles d'échantillon?
mbomb007
6

J'ai combiné plusieurs des réponses ci-dessus pour créer une méthode d'extension évaluée par Lazily. Mes tests ont montré que l'approche de Kyle (Order (N)) est plusieurs fois plus lente que l'utilisation par drzaus d'un ensemble pour proposer les indices aléatoires à choisir (Order (K)). Le premier effectue beaucoup plus d'appels au générateur de nombres aléatoires, et effectue plusieurs itérations sur les éléments.

Les objectifs de ma mise en œuvre étaient:

1) Ne réalisez pas la liste complète si vous lui donnez un IEnumerable qui n'est pas un IList. Si on me donne une séquence d'un zillion d'articles, je ne veux pas manquer de mémoire. Utilisez l'approche de Kyle pour une solution en ligne.

2) Si je peux dire que c'est un IList, utilisez l'approche de drzaus, avec une torsion. Si K est plus de la moitié de N, je risque de me débattre car je choisis encore et encore de nombreux indices aléatoires et je dois les ignorer. Ainsi je compose une liste d'indices à NE PAS conserver.

3) Je vous garantis que les articles seront retournés dans le même ordre qu'ils ont été rencontrés. L'algorithme de Kyle n'a nécessité aucune modification. L'algorithme de drzaus exigeait que je n'émette pas les éléments dans l'ordre dans lequel les indices aléatoires sont choisis. Je rassemble tous les indices dans un SortedSet, puis émets les éléments dans l'ordre d'index trié.

4) Si K est grand par rapport à N et que j'inverse le sens de l'ensemble, alors j'énumère tous les éléments et teste si l'index n'est pas dans l'ensemble. Cela signifie que je perds le temps d'exécution de l'ordre (K), mais comme K est proche de N dans ces cas, je ne perds pas grand-chose.

Voici le code:

    /// <summary>
    /// Takes k elements from the next n elements at random, preserving their order.
    /// 
    /// If there are fewer than n elements in items, this may return fewer than k elements.
    /// </summary>
    /// <typeparam name="TElem">Type of element in the items collection.</typeparam>
    /// <param name="items">Items to be randomly selected.</param>
    /// <param name="k">Number of items to pick.</param>
    /// <param name="n">Total number of items to choose from.
    /// If the items collection contains more than this number, the extra members will be skipped.
    /// If the items collection contains fewer than this number, it is possible that fewer than k items will be returned.</param>
    /// <returns>Enumerable over the retained items.
    /// 
    /// See http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c-sharp for the commentary.
    /// </returns>
    public static IEnumerable<TElem> TakeRandom<TElem>(this IEnumerable<TElem> items, int k, int n)
    {
        var r = new FastRandom();
        var itemsList = items as IList<TElem>;

        if (k >= n || (itemsList != null && k >= itemsList.Count))
            foreach (var item in items) yield return item;
        else
        {  
            // If we have a list, we can infer more information and choose a better algorithm.
            // When using an IList, this is about 7 times faster (on one benchmark)!
            if (itemsList != null && k < n/2)
            {
                // Since we have a List, we can use an algorithm suitable for Lists.
                // If there are fewer than n elements, reduce n.
                n = Math.Min(n, itemsList.Count);

                // This algorithm picks K index-values randomly and directly chooses those items to be selected.
                // If k is more than half of n, then we will spend a fair amount of time thrashing, picking
                // indices that we have already picked and having to try again.   
                var invertSet = k >= n/2;  
                var positions = invertSet ? (ISet<int>) new HashSet<int>() : (ISet<int>) new SortedSet<int>();

                var numbersNeeded = invertSet ? n - k : k;
                while (numbersNeeded > 0)
                    if (positions.Add(r.Next(0, n))) numbersNeeded--;

                if (invertSet)
                {
                    // positions contains all the indices of elements to Skip.
                    for (var itemIndex = 0; itemIndex < n; itemIndex++)
                    {
                        if (!positions.Contains(itemIndex))
                            yield return itemsList[itemIndex];
                    }
                }
                else
                {
                    // positions contains all the indices of elements to Take.
                    foreach (var itemIndex in positions)
                        yield return itemsList[itemIndex];              
                }
            }
            else
            {
                // Since we do not have a list, we will use an online algorithm.
                // This permits is to skip the rest as soon as we have enough items.
                var found = 0;
                var scanned = 0;
                foreach (var item in items)
                {
                    var rand = r.Next(0,n-scanned);
                    if (rand < k - found)
                    {
                        yield return item;
                        found++;
                    }
                    scanned++;
                    if (found >= k || scanned >= n)
                        break;
                }
            }
        }  
    } 

J'utilise un générateur de nombres aléatoires spécialisé, mais vous pouvez simplement utiliser Random de C # si vous le souhaitez. ( FastRandom a été écrit par Colin Green et fait partie de SharpNEAT. Il a une période de 2 ^ 128-1, ce qui est mieux que de nombreux RNG.)

Voici les tests unitaires:

[TestClass]
public class TakeRandomTests
{
    /// <summary>
    /// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_Array_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials/20;
        var timesChosen = new int[100];
        var century = new int[100];
        for (var i = 0; i < century.Length; i++)
            century[i] = i;

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in century.TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount/100;
        AssertBetween(avg, expectedCount - 2, expectedCount + 2, "Average");
        //AssertBetween(min, expectedCount - allowedDifference, expectedCount, "Min");
        //AssertBetween(max, expectedCount, expectedCount + allowedDifference, "Max");

        var countInRange = timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    /// <summary>
    /// Ensure that when randomly choosing items from an IEnumerable that is not an IList, 
    /// all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_IEnumerable_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials / 20;
        var timesChosen = new int[100];

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in Range(0,100).TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount / 100;
        var countInRange =
            timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    private IEnumerable<int> Range(int low, int count)
    {
        for (var i = low; i < low + count; i++)
            yield return i;
    }

    private static void AssertBetween(int x, int low, int high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }

    private static void AssertBetween(double x, double low, double high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }
}
Paul Chernoch
la source
N'y a-t-il pas une erreur dans le test? Vous avez if (itemsList != null && k < n/2)ce qui signifie à l'intérieur du if invertSetest toujours falsece qui signifie que la logique n'est jamais utilisée.
NetMage
4

À partir de la réponse de @ ers, si l'on s'inquiète de possibles implémentations différentes de OrderBy, cela devrait être sûr:

// Instead of this
YourList.OrderBy(x => rnd.Next()).Take(5)

// Temporarily transform 
YourList
    .Select(v => new {v, i = rnd.Next()}) // Associate a random index to each entry
    .OrderBy(x => x.i).Take(5) // Sort by (at this point fixed) random index 
    .Select(x => x.v); // Go back to enumerable of entry
dur
la source
3

C'est le meilleur que je puisse trouver sur une première coupe:

public List<String> getRandomItemsFromList(int returnCount, List<String> list)
{
    List<String> returnList = new List<String>();
    Dictionary<int, int> randoms = new Dictionary<int, int>();

    while (randoms.Count != returnCount)
    {
        //generate new random between one and total list count
        int randomInt = new Random().Next(list.Count);

        // store this in dictionary to ensure uniqueness
        try
        {
            randoms.Add(randomInt, randomInt);
        }
        catch (ArgumentException aex)
        {
            Console.Write(aex.Message);
        } //we can assume this element exists in the dictonary already 

        //check for randoms length and then iterate through the original list 
        //adding items we select via random to the return list
        if (randoms.Count == returnCount)
        {
            foreach (int key in randoms.Keys)
                returnList.Add(list[randoms[key]]);

            break; //break out of _while_ loop
        }
    }

    return returnList;
}

Utiliser une liste de aléas dans une plage de 1 - le nombre total de listes, puis simplement extraire ces éléments de la liste semblait être le meilleur moyen, mais utiliser le dictionnaire pour garantir l'unicité est quelque chose que je réfléchis encore.

Notez également que j'ai utilisé une liste de chaînes, remplacez-la si nécessaire.

IanStallings
la source
1
A travaillé au premier coup!
sangam
3

La solution simple que j'utilise (probablement pas bonne pour les grandes listes): Copiez la liste dans une liste temporaire, puis sélectionnez en boucle un élément de la liste temporaire au hasard et placez-le dans la liste des éléments sélectionnés tout en le supprimant de la liste temporaire (donc il ne peut pas être resélectionné).

Exemple:

List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
            o = temp[rnd.Next(temp.Count)];
            selectedItems.Add(o);
            temp.Remove(o);
            i++;
 }
Tine M.
la source
Se retirer du milieu d'une liste si souvent sera coûteux. Vous pouvez envisager d'utiliser une liste chaînée pour un algorithme nécessitant autant de suppressions. Ou de manière équivalente, remplacez l'élément supprimé par une valeur nulle, mais vous vous débattrez un peu lorsque vous choisissez des éléments déjà supprimés et que vous devez les sélectionner à nouveau.
Paul Chernoch
3

Ici, vous avez une implémentation basée sur Fisher-Yates Shuffle dont la complexité de l'algorithme est O (n) où n est le sous-ensemble ou la taille de l'échantillon, au lieu de la taille de la liste, comme l'a souligné John Shedletsky.

public static IEnumerable<T> GetRandomSample<T>(this IList<T> list, int sampleSize)
{
    if (list == null) throw new ArgumentNullException("list");
    if (sampleSize > list.Count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
    var indices = new Dictionary<int, int>(); int index;
    var rnd = new Random();

    for (int i = 0; i < sampleSize; i++)
    {
        int j = rnd.Next(i, list.Count);
        if (!indices.TryGetValue(j, out index)) index = j;

        yield return list[index];

        if (!indices.TryGetValue(i, out index)) index = i;
        indices[j] = index;
    }
}
Jesús López
la source
2

Basé sur la réponse de Kyle, voici mon implémentation c #.

/// <summary>
/// Picks random selection of available game ID's
/// </summary>
private static List<int> GetRandomGameIDs(int count)
{       
    var gameIDs = (int[])HttpContext.Current.Application["NonDeletedArcadeGameIDs"];
    var totalGameIDs = gameIDs.Count();
    if (count > totalGameIDs) count = totalGameIDs;

    var rnd = new Random();
    var leftToPick = count;
    var itemsLeft = totalGameIDs;
    var arrPickIndex = 0;
    var returnIDs = new List<int>();
    while (leftToPick > 0)
    {
        if (rnd.Next(0, itemsLeft) < leftToPick)
        {
            returnIDs .Add(gameIDs[arrPickIndex]);
            leftToPick--;
        }
        arrPickIndex++;
        itemsLeft--;
    }

    return returnIDs ;
}
Tom Gullen
la source
2

Cette méthode peut être équivalente à celle de Kyle.

Disons que votre liste est de taille n et que vous voulez k éléments.

Random rand = new Random();
for(int i = 0; k>0; ++i) 
{
    int r = rand.Next(0, n-i);
    if(r<k) 
    {
        //include element i
        k--;
    }
} 

Fonctionne comme un charme :)

-Alex Gilbert

Alex Gilbert
la source
1
Cela me semble équivalent. Comparez avec le stackoverflow.com/a/48141/2449863
DCShannon
1

pourquoi pas quelque chose comme ça:

 Dim ar As New ArrayList
    Dim numToGet As Integer = 5
    'hard code just to test
    ar.Add("12")
    ar.Add("11")
    ar.Add("10")
    ar.Add("15")
    ar.Add("16")
    ar.Add("17")

    Dim randomListOfProductIds As New ArrayList

    Dim toAdd As String = ""
    For i = 0 To numToGet - 1
        toAdd = ar(CInt((ar.Count - 1) * Rnd()))

        randomListOfProductIds.Add(toAdd)
        'remove from id list
        ar.Remove(toAdd)

    Next
'sorry i'm lazy and have to write vb at work :( and didn't feel like converting to c#
Cameron A. Ellis
la source
1

Objectif: sélectionner N nombre d'éléments de la source de collecte sans duplication. J'ai créé une extension pour toute collection générique. Voici comment je l'ai fait:

public static class CollectionExtension
{
    public static IList<TSource> RandomizeCollection<TSource>(this IList<TSource> source, int maxItems)
    {
        int randomCount = source.Count > maxItems ? maxItems : source.Count;
        int?[] randomizedIndices = new int?[randomCount];
        Random random = new Random();

        for (int i = 0; i < randomizedIndices.Length; i++)
        {
            int randomResult = -1;
            while (randomizedIndices.Contains((randomResult = random.Next(0, source.Count))))
            {
                //0 -> since all list starts from index 0; source.Count -> maximum number of items that can be randomize
                //continue looping while the generated random number is already in the list of randomizedIndices
            }

            randomizedIndices[i] = randomResult;
        }

        IList<TSource> result = new List<TSource>();
        foreach (int index in randomizedIndices)
            result.Add(source.ElementAt(index));

        return result;
    }
}
Jesse Gador
la source
0

J'ai récemment fait cela sur mon projet en utilisant une idée similaire au point 1 de Tyler .
Je chargeais un tas de questions et en sélectionnais cinq au hasard. Le tri a été réalisé à l'aide d'un IComparer .
aToutes les questions ont été chargées dans une liste QuestionSorter, qui a ensuite été triée à l'aide de la fonction de tri de la liste et les k premiers éléments ont été sélectionnés.

    private class QuestionSorter : IComparable<QuestionSorter>
    {
        public double SortingKey
        {
            get;
            set;
        }

        public Question QuestionObject
        {
            get;
            set;
        }

        public QuestionSorter(Question q)
        {
            this.SortingKey = RandomNumberGenerator.RandomDouble;
            this.QuestionObject = q;
        }

        public int CompareTo(QuestionSorter other)
        {
            if (this.SortingKey < other.SortingKey)
            {
                return -1;
            }
            else if (this.SortingKey > other.SortingKey)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }

Usage:

    List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();

    // add the questions here

    unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);

    // select the first k elements
haute technologie
la source
0

Voici mon approche (texte intégral ici http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Il devrait fonctionner en O (K) au lieu de O (N), où K est le nombre d'éléments voulus et N est la taille de la liste à choisir:

public <T> List<T> take(List<T> source, int k) {
 int n = source.size();
 if (k > n) {
   throw new IllegalStateException(
     "Can not take " + k +
     " elements from a list with " + n +
     " elements");
 }
 List<T> result = new ArrayList<T>(k);
 Map<Integer,Integer> used = new HashMap<Integer,Integer>();
 int metric = 0;
 for (int i = 0; i < k; i++) {
   int off = random.nextInt(n - i);
   while (true) {
     metric++;
     Integer redirect = used.put(off, n - i - 1);
     if (redirect == null) {
       break;
     }
     off = redirect;
   }
   result.add(source.get(off));
 }
 assert metric <= 2*k;
 return result;
}
Kristofer
la source
0

Ce n'est pas aussi élégant ou efficace que la solution acceptée, mais c'est rapide à rédiger. Commencez par permuter le tableau de manière aléatoire, puis sélectionnez les K premiers éléments. En python,

import numpy

N = 20
K = 5

idx = np.arange(N)
numpy.random.shuffle(idx)

print idx[:K]
apdnu
la source
0

J'utiliserais une méthode d'extension.

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
    {
        var random = new Random();

        var internalList = elements.ToList();

        var selected = new List<T>();
        for (var i = 0; i < countToTake; ++i)
        {
            var next = random.Next(0, internalList.Count - selected.Count);
            selected.Add(internalList[next]);
            internalList[next] = internalList[internalList.Count - selected.Count];
        }
        return selected;
    }
Kvam
la source
0
public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
    {
        // Probably you should throw exception if count > list.Count
        count = Math.Min(list.Count, count);

        var selectedIndices = new SortedSet<int>();

        // Random upper bound
        int randomMax = list.Count - 1;

        while (selectedIndices.Count < count)
        {
            int randomIndex = random.Next(0, randomMax);

            // skip over already selected indeces
            foreach (var selectedIndex in selectedIndices)
                if (selectedIndex <= randomIndex)
                    ++randomIndex;
                else
                    break;

            yield return list[randomIndex];

            selectedIndices.Add(randomIndex);
            --randomMax;
        }
    }

Mémoire: ~ nombre
Complexité: O (nombre 2 )

Cardinal
la source
0

Lorsque N est très grand, la méthode normale qui mélange au hasard les N nombres et sélectionne, disons, les k premiers nombres, peut être prohibitive en raison de la complexité de l'espace. L'algorithme suivant ne nécessite que O (k) pour les complexités temporelles et spatiales.

http://arxiv.org/abs/1512.00501

def random_selection_indices(num_samples, N):
    modified_entries = {}
    seq = []
    for n in xrange(num_samples):
        i = N - n - 1
        j = random.randrange(i)

        # swap a[j] and a[i] 
        a_j = modified_entries[j] if j in modified_entries else j 
        a_i = modified_entries[i] if i in modified_entries else i

        if a_i != j:
            modified_entries[j] = a_i   
        elif j in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(j)

        if a_j != i:
            modified_entries[i] = a_j 
        elif i in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(i)
        seq.append(a_j)
    return seq
Dai
la source
0

Utilisation de LINQ avec de grandes listes (lorsqu'il est coûteux de toucher chaque élément) ET si vous pouvez vivre avec la possibilité de doublons:

new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))

Pour mon utilisation, j'avais une liste de 100.000 éléments, et à cause d'eux étant extraits d'une base de données, j'ai réduit de moitié (ou mieux) le temps par rapport à un rnd sur toute la liste.

Avoir une grande liste réduira considérablement les chances de doublons.

Loup5
la source
Cette solution peut avoir des éléments répétés !! Le hasard dans la liste des trous ne peut pas.
AxelWass
Hmm. Vrai. Là où je l'utilise, cela n'a pas d'importance. A modifié la réponse pour refléter cela.
Wolf5 du
-1

Cela résoudra votre problème

var entries=new List<T>();
var selectedItems = new List<T>();


                for (var i = 0; i !=10; i++)
                {
                    var rdm = new Random().Next(entries.Count);
                        while (selectedItems.Contains(entries[rdm]))
                            rdm = new Random().Next(entries.Count);

                    selectedItems.Add(entries[rdm]);
                }
Cyrille
la source
Bien que cela puisse répondre à la question, vous devez modifier votre réponse pour inclure une explication de la façon dont ce bloc de code répond à la question. Cela aide à fournir un contexte et rend votre réponse beaucoup plus utile aux futurs lecteurs.
Hoppeduppeanut