Sélectionnez N éléments aléatoires d'une liste en C#

utilisant 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 vous permettront pas réellement de frapper toutes les possibilités (plus sur ce ci-dessous).

tout d'Abord, voici quelques facile à mettre en œuvre correcte-si-vous-avez-un-vrai-générateur de nombres aléatoires:

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

(1) Générer une liste de n paires [(0, rand), (1, rand), (2, rand), ...], de les trier 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 le moment O(N log n).

(2) contient 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 ceci à S. Prendre ensuite r = rand % (n-1) et Coller en s; ajouter à r Les # éléments moins qu'en s pour éviter les collisions. Prise suivante r = rand % (n-2), et faire la même chose, etc. jusqu'à ce que vous ayez k éléments distincts à l'art. Dans le pire des cas, il s'agit de la durée O(K^2). Donc pour k << n, cela peut être plus rapide. Si vous gardez s trié et la piste quels intervalles contigus il a, vous pouvez l'implémenter dans O(K log k), mais c'est plus de travail.

@Kyle-vous avez raison, à la 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é mal - mais votre approche adaptative me semble correcte. Désolé à ce sujet.

Ok, et maintenant pour le kicker: asymptotiquement (pour K fixe, n croissant), il y a n^k/k! choix du sous-ensemble d'éléments k parmi 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 nous voulons 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 les ensembles plus petits, et toujours "regarde" aléatoire, alors ces algorithmes devraient être ok.

Addendum : après avoir écrit ceci, j'ai réalisé qu'il était difficile de mettre en œuvre l'idée (2) correctement, donc j'ai voulu clarifier cette réponse. Pour obtenir O(K log k) temps, vous avez besoin d'un structure de type tableau qui supporte les recherches O(log m) et les inserts - un arbre binaire équilibré peut faire cela. En utilisant une telle structure pour construire un tableau appelé s, voici un certain 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 passer en revue quelques exemples pour voir comment cela implémente efficacement l'explication anglaise ci-dessus.

je pense que la réponse choisie est correcte et assez douce. Je l'ai mis en œuvre différemment cependant, comme je voulais aussi le résultat dans l'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 tomber sur ce problème, et une recherche plus google m'a amené au problème de mélanger au hasard une liste: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

pour mélanger complètement au hasard votre liste (en place) vous faites ceci:

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 all the way de n-1 à 1, il vous suffit de le lancer pour la n-5 (ie: n-5)

disons que vous avez besoin de K items,

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 éléments K sélectionnés sont les derniers éléments k du tableau.

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

plus loin, si vous ne voulez pas modifiez 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 de swaps et vous retournant votre liste initiale sans changer le temps D'exécution O(k).

enfin, pour le vrai stickler, si (n == k), vous devez vous arrêter à 1, Pas n-k, car l'entier choisi au hasard sera toujours 0.

à Partir de Dragons dans l'Algorithme de , 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>();
var needed = k;
var available = items.Count;
var rand = new Random();
while (selected.Count < k) {
   if( rand.NextDouble() < needed / available ) {
      selected.Add(items[available-1])
      needed--;
   }
   available--;
}

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

vous pouvez utiliser ceci mais la commande se fera du côté du client

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

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

vous devriez être en mesure de de ce en O(sous-ensemble.Longueur), plutôt que O(originalList.Longueur)

en gros, vous devriez être en mesure de générer des indices aléatoires subset et ensuite les extraire de la liste originale.

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 des indices , pas les éléments de liste réels (dans le cas où vous avez des types complexes ou des comparaisons coûteuses);

L'Unité De Test

et pour s'assurer que nous n'avons 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 N aléatoire des éléments d'un groupe ne devrait pas avoir quelque chose à voir avec ordre ! Le caractère aléatoire est une question d'imprévisibilité et non de mélange 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 sont pas. Puisque l'efficacité est la clé ici, je vais poster quelque chose qui ne change pas trop l'ordre des articles.

1) si vous avez besoin vrai valeurs aléatoires qui signifie qu'il n'ya pas de restriction sur les éléments à choisir (c'est à dire, une fois choisi, l'élément peut être resélectionnés):

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 le drapeau d'exception, vous pouvez choisir des éléments aléatoires n'importe quel nombre de fois.

Si vous avez { 1, 2, 3, 4 }, ensuite, il peut donner { 1, 4, 4 }, { 1, 4, 3 } etc pour 3 articles ou même { 1, 4, 3, 2, 4 } pour 5 articles!

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

2) Si vous avez besoin de individual membres du groupe sans répétition, alors je compterais 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 d'autres approches de dictionnaire ici parce que je ne suis pas seulement l'ajout, mais aussi la suppression de la liste, donc son genre deux boucles. Vous pouvez voir ici que je n'ai pas modifié n'importe quoi quand count devient égal à source.Count . C'est parce que je crois que aléatoire devrait être dans le ensemble retourné comme un ensemble . Je veux dire, si vous voulez 5 articles aléatoires de 1, 2, 3, 4, 5 , il ne devrait pas se soucier si son 1, 3, 4, 2, 5 ou 1, 2, 3, 4, 5 , mais si vous avez besoin 4 articles du même ensemble, alors il devrait rendement imprévisible en 1, 2, 3, 4 , 1, 3, 5, 2 , 2, 3, 5, 4 etc. Deuxièmement, lorsque le nombre d'articles à retourner au hasard est supérieur à la moitié du groupe d'origine, il est plus facile de supprimer source.Count - count du groupe que d'ajouter count . Pour des raisons de performance j'ai utilisé source au lieu de sourceDict pour obtenir alors l'index aléatoire dans la méthode remove.

Donc si vous avez { 1, 2, 3, 4 }, cela peut se retrouver dans { 1, 2, 3 }, { 3, 4, 1 } etc pour 3 articles.

3) Si vous avez besoin de valeurs aléatoires vraiment distinctes de votre groupe en tenant compte des doublons dans le groupe original, alors vous pouvez utiliser la même approche que ci-dessus, mais un 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();
}

la variable randoms est transformée en HashSet pour éviter l'ajout de doublons dans les cas les plus rares où Random.Next peut donner le même résultat. valeur, surtout quand la liste d'entrées est petite.

Donc { 1, 2, 2, 4 } => 3 articles au hasard => { 1, 2, 4 } et jamais { 1, 2, 2}

{ 1, 2, 2, 4 } => 4 articles au hasard => exception!! ou { 1, 2, 4 } selon le drapeau.

quelques-unes 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 son tout sur la performance avec des dizaines de milliers d'articles dans la liste doit être iterated 10000 fois , alors vous pouvez vouloir avoir plus rapide classe aléatoire que System.Random , mais je ne pense pas que ce soit une grosse affaire considérant ce dernier n'est probablement jamais un goulot d'étranglement, son assez rapide..

Edit: Si vous avez besoin de ré-arranger l'ordre des articles retournés ainsi, alors il n'y a rien qui peut battre dhakim de Fisher-Yates approche - court, doux et simple..

la solution simple que j'utilise (probablement pas bon pour les grandes listes): Copiez la liste dans la liste temporaire, puis en boucle, sélectionnez au hasard un élément de la liste temporaire et mettez-le dans la liste des éléments sélectionnés tout en le retirant de la liste temporaire (de sorte qu'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++;
 }

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 (ordre(N)) est beaucoup plus lente que l'utilisation par drzaus d'un ensemble pour proposer les indices aléatoires à choisir (ordre(K)). Le premier effectue beaucoup plus d'appels vers le générateur de nombres aléatoires, plus itérates plus de fois sur les articles.

les objectifs de ma mise en œuvre étaient:

1) Ne pas réaliser la liste complète si donné un IEnumerable qui n'est pas un IList. Si je me suis donné une séquence d'un tas d'éléments, je ne veux pas manquer de mémoire. Utilisez L'approche de Kyle pour trouver 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 frapper comme je choisis beaucoup d'indices aléatoires encore et encore et doivent les sauter. Ainsi je compose une liste des indices à ne pas garder.

3) je garantis que les articles seront ils sont revenus dans l'ordre où ils ont été rencontrés. Kyle algorithme requis aucune altération. l'algorithme de drzaus exigeait que je n'émette pas d'items dans l'ordre où les indices aléatoires sont choisis. Je ramasse tous les indices dans un ensemble sorted, puis j'émets les articles dans l'ordre d'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 je teste si l'indice n'est pas dans l'ensemble. Cela signifie que Je perds le temps D'exécution de L'ordre(K) , mais puisque K est proche de N dans ces cas, je ne perds pas beaucoup.

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 /q/select-n-random-elements-from-a-list-in-c-65954/"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));
    }
}

vous avez ici 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 C# implementation.

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

dites que votre liste est de taille n et que vous voulez des éléments K.

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

C'est le mieux que j'ai pu 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;
}

L'utilisation d'une liste de randoms dans une gamme de 1 - Total liste count et puis tout simplement tirer ces éléments dans la liste semble être la meilleure façon, mais l'utilisation du dictionnaire pour assurer l'unicité est quelque chose que je suis encore à réfléchir.

aussi noter que j'ai utilisé une liste de chaînes de caractères, Remplacer 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#

Il 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 le code C# :

de Retour de sous-ensemble aléatoire de N éléments d'un tableau donné

but: sélectionner N nombre d'articles de la collection source sans duplication. J'ai créé une extension pour n'importe quelle 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 ceci sur mon projet en utilisant une idée similaire à Tyler point 1 .

Je chargeais un tas de questions et en sélectionnais cinq au hasard. Le tri a été réalisé à l'aide d'un IComparer .

toutes les questions ont été chargées dans la liste a QuestionSorter, qui a ensuite été triée en utilisant la fonction de tri de la liste et les premiers éléments k 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;
            }
        }
    }

Utilisation:

    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 complet ici http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

il doit être exécuté en O(K) au lieu de O (N), où K est le nombre d'éléments recherchés et N 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 à écrire. Tout d'abord, permuter le tableau au hasard, puis sélectionner les premiers K é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: ~le comte

Complexité: ² )

quand N est très grand, la méthode normale qui mélange au hasard les nombres N et sélectionne, disons, les premiers nombres k, peut être prohibitive en raison de la complexité de l'espace. L'algorithme suivant ne requiert O (k) que 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

utilisant 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 usage j'ai eu une liste de 100.000 éléments, et à cause d'eux étant tiré d'un DB j'ai environ halfed (ou mieux) le temps par rapport à un rnd sur l'ensemble de la liste.

avoir une grande liste réduira considérablement les chances pour les doublons.

en partant 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