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

https://stackoverflow.com/questions/48087

09-06-2019
|

Question

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 d'un List<string>.

La solution

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

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

Autres conseils

Utilisation de Linq :

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

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

Il s’agit en fait d’un problème plus difficile qu’il n’y paraît, principalement parce que de nombreuses solutions mathématiquement correctes ne parviendront pas à vous permettre d’exploiter toutes les possibilités (plus d’informations à ce sujet ci-dessous).

Tout d’abord, voici quelques générateurs de nombres vraiment aléatoires faciles à mettre en œuvre et corrects si vous disposez d’un générateur de nombres vraiment aléatoires :

(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 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, même si c'est un temps O(n log n).

(2) Initialisez 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 collez s ;ajoutez à r les # éléments inférieurs à s pour éviter les collisions.Prenez ensuite r = rand % (n-2), et faites la même chose, etc.jusqu'à ce que vous ayez k éléments distincts dans s.Dans le pire des cas, le temps d'exécution est O (k ^ 2).Donc pour k << n, cela peut être plus rapide.Si vous gardez s triés et suivez les intervalles contigus dont il dispose, vous pouvez l'implémenter dans O(k log k), mais cela demande 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 pensé à 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 du sous-ensemble de k éléments sur n éléments [il s'agit d'une approximation de (n choisir k)].Si n est grand et 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 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 est impossible 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 convenir.

Addenda:Après avoir écrit ceci, j'ai réalisé qu'il était difficile de mettre en œuvre correctement l'idée (2), j'ai donc voulu 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 met en œuvre efficacement l'explication anglaise ci-dessus.

Je pense que la réponse sélectionnée est correcte et plutôt intéressante.Je l'ai implémenté différemment, car je voulais également que le résultat soit 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);
    }

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

Pour mélanger votre liste de manière complètement aléatoire (sur 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 de n-1 à 1, il vous suffit de l'exécuter jusqu'à n-5 (c'est-à-dire :n-5)

Disons que vous avez besoin de k éléments,

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 échangé 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 noter 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 la modifier. le temps d'exécution O(k).

Enfin, pour les vrais pointilleux, si (n == k), vous devez vous arrêter à 1, pas à n-k, car l'entier choisi au hasard sera toujours 0.

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

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);

Depuis Dragons dans l'algorithme, 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 d'éléments.

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

vous devriez pouvoir le faire dans O(subset.Length), plutôt que O(originalList.Length)

En gros, vous devriez pouvoir générer subset indices aléatoires, puis extrayez-les 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 un HashSet de la 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 s'assurer qu'il n'y ait pas de collisions, 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);
        }
    }
}

Sélection de N aléatoire les éléments d'un groupe ne devraient rien avoir à voir avec commande!Le hasard est une question d’imprévisibilité et non de brassage des positions dans un groupe.Toutes les réponses qui traitent d'un certain type d'ordre 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 vrai valeurs aléatoires, ce qui signifie qu'il n'y a aucune restriction sur les éléments parmi lesquels choisir (c'est-à-dire qu'une fois l'élément choisi, il 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 certain nombre de fois.

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

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

2) Si vous avez besoin individuel membres du groupe sans répétition, alors je m'appuierais sur 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 car je n'ajoute pas seulement, mais je supprime également de la liste, donc c'est un peu deux boucles.Vous pouvez voir ici que je n'ai pas réorganisé n'importe quoi quand count devient égal à source.Count.C'est parce que je crois le hasard devrait être dans le ensemble retourné dans son ensemble.Je veux dire, si tu veux 5 objets aléatoires de 1, 2, 3, 4, 5, cela ne devrait pas avoir d'importance si c'est 1, 3, 4, 2, 5 ou 1, 2, 3, 4, 5, mais si tu as besoin 4 éléments du même ensemble, alors il devrait céder de manière imprévisible 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4 etc.Deuxièmement, lorsque le nombre d'éléments aléatoires à renvoyer est supérieur à la moitié du groupe d'origine, il est alors plus facile de les supprimer source.Count - count éléments du groupe que d'ajouter count articles.Pour des raisons de performances, j'ai utilisé source au lieu de sourceDict pour obtenir ensuite 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 alors utiliser la même approche que ci-dessus, mais une HashSet sera 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();
}

Le randoms la variable est transformée en HashSet pour éviter l'ajout de doublons dans les cas les plus rares où Random.Next peut donner la même valeur, surtout 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 dans la liste devant être itérés 10 000 fois, alors vous souhaiterez peut-être avoir 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.

Modifier: Si vous devez également réorganiser l'ordre des articles retournés, il n'y a rien de mieux que l'approche Fisher-Yates de Dhakim - court, doux et simple..

La solution simple que j'utilise (probablement pas bonne pour les grandes listes) :Copiez la liste dans la liste temporaire, puis en boucle, sélectionnez au hasard l'élément de la liste temporaire et placez-le dans la liste des éléments sélectionnés tout en le supprimant de la liste temporaire (afin qu'il ne puisse 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++;
 }

J'ai combiné plusieurs des réponses ci-dessus pour créer une méthode d'extension évaluée paresseusement.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 itère plus de fois sur les éléments.

Les objectifs de ma mise en œuvre étaient :

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

2) Si je peux dire qu'il s'agit d'un IList, utilisez l'approche de Drzaus, avec une touche d'originalité.Si K est supérieur à la moitié de N, je risque de me battre car je choisis encore et encore de nombreux indices aléatoires et je dois les ignorer.Je compose ainsi une liste des indices à NE PAS conserver.

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

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 C# Aléatoire si tu veux.(RapideAléatoire a été écrit par Colin Green et fait partie de SharpNEAT.Il a une période de 2 ^ 128-1, ce qui est meilleur 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));
    }
}

Ici vous avez une implémentation basée sur Mélange Fisher-Yates dont la complexité de l'algorithme est O(n) où n est la taille du sous-ensemble ou 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;
    }
}

Sur la base de 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 ;
}

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

Supposons que votre liste soit de taille n et que vous souhaitiez 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 à merveille :)

-Alex Gilbert

Dans le prolongement de la réponse de @ers, si l'on s'inquiète des différentes implémentations possibles 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

C'est le meilleur que j'ai pu trouver sur un premier montage :

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 données aléatoires dans une plage de 1 - nombre total de liste, 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.

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#

C'est beaucoup plus difficile qu'on pourrait le penser.Voir le excellent article "Shuffling" de Jeff.

J'ai écrit un très court article sur ce sujet comprenant du code C# :
Renvoie un sous-ensemble aléatoire de N éléments d'un tableau donné

But:Sélectionnez 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 j'ai procédé :

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;
    }
}

J'ai récemment fait cela sur mon projet en utilisant une idée similaire à Le point de Tyler 1.
Je chargeais un tas de questions et en sélectionnais cinq au hasard.Le tri a été réalisé à l'aide d'un IComparateur.
aToutes les questions ont été chargées dans une liste QuestionSorter, qui a ensuite été triée à l'aide du 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

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

Il doit s'exécuter en O(K) au lieu de O(N), où K est le nombre d'éléments recherchés et N est la taille de la liste parmi laquelle 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;
}

Ce n’est pas aussi élégant ou efficace que la solution acceptée, mais c’est rapide à rédiger.Tout d’abord, permutez 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]

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;
    }

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:~compter
Complexité:O(compte²)

Lorsque N est très grand, la méthode normale qui mélange aléatoirement les N nombres et sélectionne, disons, k premiers nombres, peut s'avérer prohibitive en raison de la complexité spatiale.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

Utiliser LINQ avec de grandes listes (quand 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 comme ils étaient 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 risques de doublons.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow