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

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>.

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.

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

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.

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

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.

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

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

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.

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.

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

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

À 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

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.

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

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

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

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

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 ne le pense. Voir le grand article "Shuffling" de Jeff.

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

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

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

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

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]

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

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

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.

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