Seleccione N elementos aleatorios de una Lista <T> en C #

158

Necesito un algoritmo rápido para seleccionar 5 elementos aleatorios de una lista genérica. Por ejemplo, me gustaría obtener 5 elementos aleatorios de a List<string>.

JC Grubbs
fuente
12
Por aleatorio, ¿te refieres a inclusivo o exclusivo? IOW, ¿se puede elegir el mismo elemento más de una vez? (realmente aleatorio) O una vez que se selecciona un elemento, ¿ya no se puede elegir del grupo disponible?
Pretzel

Respuestas:

127

Iterar a través y para cada elemento hacer la probabilidad de selección = (número necesario) / (número restante)

Entonces, si tuviera 40 artículos, el primero tendría una probabilidad de 5/40 de ser seleccionado. Si es así, el siguiente tiene una probabilidad de 4/39, de lo contrario tiene una probabilidad de 5/39. Cuando llegue al final, tendrá sus 5 artículos, y a menudo los tendrá todos antes de eso.

Kyle Cronin
fuente
33
Siento que esto está sutilmente mal. Parece que el back-end de la lista se elegirá con más frecuencia que el front-end ya que el back-end verá probabilidades mucho mayores. Por ejemplo, si no se seleccionan los primeros 35 números, se deben elegir los últimos 5 números. El primer número solo verá una probabilidad de 5/40, pero ese último número verá 1/1 con más frecuencia que 5/40 veces. Tendrá que aleatorizar la lista primero antes de implementar este algoritmo.
Ankur Goel
23
ok, ejecuté este algoritmo 10 millones de veces en una lista de 40 elementos, cada uno con un disparo de 5/40 (.125) para ser seleccionado, y luego ejecuté esa simulación varias veces. Resulta que esto no está distribuido uniformemente. Los elementos 16 a 22 se deseleccionan (16 = .123, 17 = .124), mientras que el elemento 34 se sobreselecciona (34 = .129). Los elementos 39 y 40 también se deseleccionan pero no tanto (39 = .1247, 40 = .1246)
Ankur Goel
22
@Ankur: No creo que sea estadísticamente significativo. Creo que hay una prueba inductiva de que esto proporcionará una distribución uniforme.
recursivo
9
He repetido la misma prueba 100 millones de veces, y en mi prueba, el elemento menos elegido fue elegido con menos del 0.106% con menos frecuencia que el elemento elegido con más frecuencia.
recursivo
55
@recursive: la prueba es casi trivial. Sabemos cómo seleccionar K elementos de K para cualquier K y cómo seleccionar 0 elementos de N para cualquier N. Supongamos que conocemos un método para seleccionar uniformemente elementos K o K-1 de N-1> = K; entonces podemos seleccionar K ítems de N seleccionando el primer ítem con probabilidad K / N y luego usando el método conocido para seleccionar los ítems K o K-1 aún necesarios del N-1 restante.
Ilmari Karonen
216

Usando linq:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
fuente
2
+1 Pero si dos elementos obtienen el mismo número de rnd.Next () o similar, entonces se seleccionará el primero y posiblemente el segundo no (si no se necesitan más elementos). Sin embargo, es lo suficientemente aleatorio según el uso.
Lasse Espeholt
8
Creo que el orden por es O (n log (n)), por lo que elegiría esta solución si la simplicidad del código es la principal preocupación (es decir, con listas pequeñas).
Guido
2
Pero, ¿no enumera y ordena la lista completa? A menos que, por "rápido", OP signifique "fácil", no "performante" ...
drzaus
2
Esto solo funcionará si OrderBy () solo llama al selector de teclas una vez para cada elemento. Si lo llama cada vez que desea realizar una comparación entre dos elementos, obtendrá un valor diferente cada vez, lo que arruinará el orden. La [documentación] ( msdn.microsoft.com/en-us/library/vstudio/… ) no dice cuál es.
Oliver Bock
2
Tenga cuidado si YourListtiene muchos elementos, pero solo desea seleccionar algunos. En este caso no es una forma eficiente de hacerlo.
Callum Watkins
39
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
vag
fuente
27

Este es en realidad un problema más difícil de lo que parece, principalmente porque muchas soluciones matemáticamente correctas no le permitirán alcanzar todas las posibilidades (más sobre esto a continuación).

Primero, aquí hay algunos generadores fáciles de implementar, correctos si tienes un número verdaderamente aleatorio:

(0) La respuesta de Kyle, que es O (n).

(1) Genere una lista de n pares [(0, rand), (1, rand), (2, rand), ...], ordénelos por la segunda coordenada y use la primera k (para usted, k = 5) índices para obtener su subconjunto aleatorio. Creo que esto es fácil de implementar, aunque es tiempo O (n log n).

(2) Inicie una lista vacía s = [] que crecerá para ser los índices de k elementos aleatorios. Elija un número r en {0, 1, 2, ..., n-1} al azar, r = rand% n, y agregue esto a s. Luego tome r = rand% (n-1) y pegue s; agregue a r los # elementos menos que en s para evitar colisiones. Luego tome r = rand% (n-2), y haga lo mismo, etc. hasta que tenga k elementos distintos en s. Esto tiene el peor tiempo de ejecución O (k ^ 2). Entonces, para k << n, esto puede ser más rápido. Si mantiene ordenado y realiza un seguimiento de los intervalos contiguos que tiene, puede implementarlo en O (k log k), pero es más trabajo.

@Kyle: tienes razón, pensándolo bien, estoy de acuerdo con tu respuesta. Al principio lo leí apresuradamente y pensé erróneamente que estabas indicando que elegías secuencialmente cada elemento con probabilidad fija k / n, lo que habría estado mal, pero tu enfoque adaptativo me parece correcto. Lo siento por eso.

Ok, y ahora para el pateador: asintóticamente (para k fijo, n creciendo), ¡hay n ^ k / k! opciones de k elemento subconjunto de n elementos [esta es una aproximación de (n elegir k)]. Si n es grande yk no es muy pequeño, entonces estos números son enormes. La mejor duración de ciclo que puede esperar en cualquier generador de números aleatorios estándar de 32 bits es 2 ^ 32 = 256 ^ 4. Entonces, si tenemos una lista de 1000 elementos y queremos elegir 5 al azar, no hay forma de que un generador de números aleatorios estándar alcance todas las posibilidades. Sin embargo, siempre y cuando esté bien con una opción que funcione bien para conjuntos más pequeños y siempre "parezca" al azar, entonces estos algoritmos deberían estar bien.

Anexo : Después de escribir esto, me di cuenta de que es difícil implementar la idea (2) correctamente, por lo que quería aclarar esta respuesta. Para obtener el tiempo O (k log k), necesita una estructura tipo matriz que admita búsquedas e inserciones O (log m); un árbol binario equilibrado puede hacer esto. Usando tal estructura para construir una matriz llamada s, aquí hay algunos 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

Sugiero revisar algunos casos de muestra para ver cómo esto implementa de manera eficiente la explicación en inglés anterior.

Tyler
fuente
2
para (1) puede barajar una lista más rápido que la clasificación, para (2) sesgará su distribución utilizando%
jk.
Dada la objeción que planteó sobre la duración del ciclo de un rng, ¿hay alguna forma de que podamos construir un algoritmo que elija todos los conjuntos con la misma probabilidad?
Jonás
Para (1), para mejorar el O (n log (n)), puede usar la ordenación por selección para encontrar los k elementos más pequeños. Eso se ejecutará en O (n * k).
Jared
@ Jonás: eso creo. Supongamos que podemos combinar múltiples generadores independientes de números aleatorios para crear uno más grande ( crypto.stackexchange.com/a/27431 ). Entonces solo necesita un rango lo suficientemente grande como para manejar el tamaño de la lista en cuestión.
Jared
16

Creo que la respuesta seleccionada es correcta y bastante dulce. Sin embargo, lo implementé de manera diferente, ya que también quería el resultado en orden aleatorio.

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

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

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

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }
Frank Schwieterman
fuente
¡INCREÍBLE! ¡Realmente me ayudó!
Armstrongest
1
¿Tiene alguna razón para no usar el nuevo Random () que se basa en Environment.TickCount vs. DateTime.Now.Millisecond?
Lasse Espeholt
No, simplemente no sabía que existía el incumplimiento.
Frank Schwieterman
2
Está bien un año tarde, pero ... ¿Esto no se aplica a la respuesta más corta de @ersin, y no fallará si obtiene un número aleatorio repetido (donde Ersin tendrá un sesgo hacia el primer elemento de un par repetido)
Andiih
1
Random random = new Random(DateTime.Now.Millisecond);en cada llamada definitivamente está mal. Crear una nueva instancia de Randomcada vez reduce la aleatoriedad real. Use una static readonlyinstancia de este, preferiblemente construida con el constructor predeterminado.
jpmc26
12

Acabo de encontrarme con este problema, y ​​algunas búsquedas más en Google me llevaron al problema de barajar aleatoriamente una lista: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Para barajar completamente al azar su lista (en su lugar), haga esto:

Para barajar una matriz de n elementos (índices 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 solo necesita los primeros 5 elementos, en lugar de ejecutar i desde n-1 a 1, solo necesita ejecutarlo a n-5 (es decir: n-5)

Digamos que necesitas k artículos,

Esto se convierte en:

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

Cada elemento que se selecciona se intercambia hacia el final de la matriz, por lo que los k elementos seleccionados son los últimos k elementos de la matriz.

Esto lleva tiempo O (k), donde k es el número de elementos seleccionados al azar que necesita.

Además, si no desea modificar su lista inicial, puede escribir todos sus swaps en una lista temporal, invertir esa lista y aplicarlos nuevamente, realizando así el conjunto inverso de swaps y devolviéndole su lista inicial sin cambiar el tiempo de ejecución de O (k).

Finalmente, para el stickler real, if (n == k), debe detenerse en 1, no nk, ya que el entero elegido al azar siempre será 0.

dhakim
fuente
Lo implementé usando C # en mi publicación de blog: vijayt.com/post/random-select-using-fisher-yates-algorithm . Espero que ayude a alguien que busca la forma C #.
vijayst
9

Puede usar esto, pero el pedido se realizará en el lado del cliente

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Marwan Roushdy
fuente
Convenido. Puede que no sea el mejor rendimiento o el más aleatorio, pero para la gran mayoría de las personas será lo suficientemente bueno.
Richiban
Voto negativo porque se garantiza que los Guías serán únicos, no aleatorios .
Theodor Zoulias
8

De Dragons in the Algorithm , una interpretación 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--;
}

Este algoritmo seleccionará indicios únicos de la lista de elementos.

Spoulson
fuente
Solo obtenga suficientes elementos en la lista, pero no los obtenga al azar.
culithay
2
Esta implementación está rota porque el uso de varresultados neededy availableambos son enteros, lo que hace que needed/availablesiempre sea 0.
Niko
1
Esto parece ser una implementación de la respuesta aceptada.
DCShannon
6

¡Seleccionar N elementos aleatorios de un grupo no debería tener nada que ver con el pedido ! La aleatoriedad se trata de imprevisibilidad y no de barajar posiciones en un grupo. Todas las respuestas que tratan con algún tipo de ordenamiento seguramente serán menos eficientes que las que no lo hacen. Dado que la eficiencia es la clave aquí, publicaré algo que no cambie demasiado el orden de los artículos.

1) Si necesita valores aleatorios verdaderos , lo que significa que no hay restricciones sobre qué elementos elegir (es decir, una vez que el elemento elegido se puede volver a seleccionar):

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 desactiva la marca de excepción, puede elegir elementos aleatorios cualquier cantidad de veces.

Si tiene {1, 2, 3, 4}, entonces puede dar {1, 4, 4}, {1, 4, 3} etc. para 3 artículos o incluso {1, 4, 3, 2, 4} para 5 artículos!

Esto debería ser bastante rápido, ya que no tiene nada que verificar.

2) Si necesita miembros individuales del grupo sin repetición, entonces confiaría en un diccionario (como muchos ya han señalado).

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

El código es un poco más largo que otros enfoques de diccionario aquí porque no solo estoy agregando, sino también eliminando de la lista, por lo que son un poco dos bucles. Puedes ver aquí que no he reordenado nada en absoluto cuando countes igual a source.Count. Eso es porque creo que la aleatoriedad debería estar en el conjunto devuelto como un todo . Quiero decir que si quieres 5 elementos aleatorios 1, 2, 3, 4, 5, no debería importar si es 1, 3, 4, 2, 5o 1, 2, 3, 4, 5, pero si necesitas 4 elementos del mismo conjunto, entonces debería producir 1, 2, 3, 4, de forma impredecible 1, 3, 5, 2,2, 3, 5, 4 etc. En segundo lugar, cuando el número de elementos al azar que se devuelto es más de la mitad del grupo original, entonces es más fácil de eliminarsource.Count - countelementos del grupo que agregar countelementos. Por razones de rendimiento, he utilizado en sourcelugar de sourceDictobtener un índice aleatorio en el método remove.

Entonces, si tiene {1, 2, 3, 4}, esto puede terminar en {1, 2, 3}, {3, 4, 1}, etc. para 3 elementos.

3) Si necesita valores aleatorios verdaderamente distintos de su grupo teniendo en cuenta los duplicados en el grupo original, entonces puede usar el mismo enfoque que el anterior, pero HashSetserá más ligero que un diccionario.

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 se hace HashSetpara evitar que se agreguen duplicados en los casos más raros en los que Random.Nextpuede producir el mismo valor, especialmente cuando la lista de entrada es pequeña.

Entonces {1, 2, 2, 4} => 3 elementos aleatorios => {1, 2, 4} y nunca {1, 2, 2}

¡{1, 2, 2, 4} => 4 elementos aleatorios => excepción !! o {1, 2, 4} dependiendo del conjunto de banderas.

Algunos de los métodos de extensión que he usado:

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 todo se trata de rendimiento con decenas de miles de elementos en la lista que tienen que repetirse 10000 veces, entonces es posible que desee tener una clase aleatoria más rápida que System.Random, pero no creo que sea un gran problema teniendo en cuenta que lo último probablemente nunca sea un cuello de botella, es bastante rápido ...

Editar: si necesita reorganizar el orden de los artículos devueltos también, entonces no hay nada que pueda vencer el enfoque de Fisher-Yates de dhakim : breve, dulce y simple.

nawfal
fuente
6

Estaba pensando en el comentario de @JohnShedletsky sobre la respuesta aceptada con respecto a (paráfrasis):

debería poder hacer esto en O (subset.Length), en lugar de O (originalList.Length)

Básicamente, deberías poder generar subset índices aleatorios y luego extraerlos de la lista original.

El método

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 quisieras ser aún más eficiente, probablemente usarías uno HashSetde los índices , no los elementos de la lista real (en caso de que tenga tipos complejos o comparaciones costosas);

La prueba unitaria

Y para asegurarnos de que no tenemos colisiones, etc.

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

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

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

        while( repetitions-- > 0 ) {
            randomItems = methodToGetRandomItems(items, numToTake);
            Assert.AreEqual(numToTake, randomItems.Count(),
                            "Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);
            if(requireDistinct) Assert.AreEqual(numToTake, randomItems.Distinct().Count(),
                            "Collisions (non-unique values) found, failed at {0} repetition--", repetitions);
            Assert.IsTrue(randomItems.All(o => items.Contains(o)),
                        "Some unknown values found; failed at {0} repetition--", repetitions);
        }
    }
}
drzaus
fuente
2
Buena idea, con problemas. (1) Si su lista más grande es enorme (leer de una base de datos, por ejemplo), entonces se da cuenta de la lista completa, que puede exceder la memoria. (2) Si K está cerca de N, entonces se moverá mucho buscando un índice no reclamado en su bucle, haciendo que el código requiera una cantidad de tiempo impredecible. Estos problemas tienen solución.
Paul Chernoch
1
Mi solución para el problema de la paliza es esta: si K <N / 2, hágalo a su manera. Si K> = N / 2, elija los índices que NO deberían mantenerse, en lugar de los que deberían mantenerse. Todavía hay algunos golpes, pero mucho menos.
Paul Chernoch
También noté que esto altera el orden de los elementos que se enumeran, lo que puede ser aceptable en algunas situaciones, pero no en otras.
Paul Chernoch
En promedio, para K = N / 2 (el peor de los casos para la mejora sugerida por Paul), el algoritmo (mejorando) parece tomar ~ 0,693 * N iteraciones. Ahora haz una comparación de velocidad. ¿Es esto mejor que la respuesta aceptada? ¿Para qué tamaños de muestra?
mbomb007
6

Combiné varias de las respuestas anteriores para crear un método de extensión evaluado con pereza. Mi prueba mostró que el enfoque de Kyle (Orden (N)) es muchas veces más lento que el uso de un conjunto de drzaus para proponer los índices aleatorios para elegir (Orden (K)). El primero realiza muchas más llamadas al generador de números aleatorios, además de iterar más veces sobre los elementos.

Los objetivos de mi implementación fueron:

1) No realice la lista completa si recibe un IEnumerable que no es una IList. Si me dan una secuencia de millones de elementos, no quiero quedarme sin memoria. Use el enfoque de Kyle para una solución en línea.

2) Si puedo decir que es una IList, use el enfoque de drzaus, con un giro. Si K es más de la mitad de N, me arriesgo a dar vueltas porque elijo muchos índices aleatorios una y otra vez y tengo que omitirlos. Por lo tanto, compongo una lista de los índices que NO debo guardar.

3) Le garantizo que los artículos serán devueltos en el mismo orden en que fueron encontrados. El algoritmo de Kyle no requirió alteración. El algoritmo de drzaus requería que no emitiera elementos en el orden en que se eligen los índices aleatorios. Reúno todos los índices en un conjunto ordenado, luego emito elementos en orden de índice ordenado.

4) Si K es grande en comparación con N e invierto el sentido del conjunto, enumero todos los elementos y pruebo si el índice no está en el conjunto. Esto significa que pierdo el tiempo de ejecución de la Orden (K), pero dado que K está cerca de N en estos casos, no pierdo mucho.

Aquí está el código:

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

Utilizo un generador especializado de números aleatorios, pero puedes usar Aleatorio de C # si lo deseas. ( FastRandom fue escrito por Colin Green y es parte de SharpNEAT. Tiene un período de 2 ^ 128-1 que es mejor que muchos RNG).

Aquí están las pruebas unitarias:

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

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

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

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

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

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

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

    private static void AssertBetween(double x, double low, double high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }
}
Paul Chernoch
fuente
¿No hay un error en la prueba? Tienes lo if (itemsList != null && k < n/2)que significa que if invertSetsiempre está dentro, lo falseque significa que la lógica nunca se usa.
NetMage
4

Extendiendo la respuesta de @ ers, si uno está preocupado por posibles implementaciones diferentes de OrderBy, esto debería ser seguro:

// 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
duro
fuente
3

Esto es lo mejor que se me ocurrió en un primer corte:

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

Usar una lista de randoms dentro de un rango de 1 - conteo total de la lista y luego simplemente extraer esos elementos en la lista parecía ser la mejor manera, pero usar el Diccionario para garantizar la unicidad es algo que todavía estoy reflexionando.

También tenga en cuenta que usé una lista de cadenas, reemplace según sea necesario.

IanStallings
fuente
1
Trabajó en el primer tiro!
sangam
3

La solución simple que uso (probablemente no es buena para listas grandes): copie la lista en una lista temporal, luego, en bucle, seleccione aleatoriamente el elemento de la lista temporal y colóquelo en la lista de elementos seleccionados mientras lo elimina de la lista temporal (por lo que no puede ser reseleccionado).

Ejemplo:

List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
            o = temp[rnd.Next(temp.Count)];
            selectedItems.Add(o);
            temp.Remove(o);
            i++;
 }
Tine M.
fuente
Eliminar del medio de una lista con tanta frecuencia será costoso. Puede considerar usar una lista vinculada para un algoritmo que requiera tantas eliminaciones. O, de manera equivalente, reemplace el elemento eliminado con un valor nulo, pero luego golpeará un poco a medida que elija los elementos ya eliminados y tenga que volver a elegir.
Paul Chernoch
3

Aquí tiene una implementación basada en Fisher-Yates Shuffle cuya complejidad de algoritmo es O (n) donde n es el subconjunto o el tamaño de la muestra, en lugar del tamaño de la lista, como señaló John Shedletsky.

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

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

        yield return list[index];

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

Según la respuesta de Kyle, aquí está mi implementación de C #.

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

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

    return returnIDs ;
}
Tom Gullen
fuente
2

Este método puede ser equivalente al de Kyle.

Digamos que su lista es de tamaño ny quiere k elementos.

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

Funciona de maravilla :)

-Alex Gilbert

Alex Gilbert
fuente
1
Eso me parece equivalente. Compare con el stackoverflow.com/a/48141/2449863
DCShannon
1

¿Por qué no algo como esto?

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

    Dim randomListOfProductIds As New ArrayList

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

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

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

Objetivo: seleccionar N cantidad de elementos del origen de la colección sin duplicación. Creé una extensión para cualquier colección genérica. Así es como lo hice:

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

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

            randomizedIndices[i] = randomResult;
        }

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

        return result;
    }
}
Jesse Gador
fuente
0

Recientemente hice esto en mi proyecto usando una idea similar al punto 1 de Tyler .
Estaba cargando un montón de preguntas y seleccionando cinco al azar. La clasificación se logró utilizando un IComparer .
Todas las preguntas se cargaron en la lista de QuestionSorter, que luego se ordenó utilizando función Ordenar de lista y los primeros k elementos donde se seleccionaron.

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

Uso:

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

    // add the questions here

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

    // select the first k elements
hitec
fuente
0

Aquí está mi enfoque (texto completo aquí http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Debe ejecutarse en O (K) en lugar de O (N), donde K es el número de elementos deseados y N es el tamaño de la lista para elegir:

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

Esto no es tan elegante o eficiente como la solución aceptada, pero es rápido de escribir. Primero, permuta la matriz al azar, luego selecciona los primeros K elementos. En python

import numpy

N = 20
K = 5

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

print idx[:K]
apdnu
fuente
0

Yo usaría un método de extensión.

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

        var internalList = elements.ToList();

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

        var selectedIndices = new SortedSet<int>();

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

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

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

            yield return list[randomIndex];

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

Memoria: ~
complejidad de conteo : O (conteo 2 )

Cardenal
fuente
0

Cuando N es muy grande, el método normal que baraja aleatoriamente los N números y selecciona, digamos, los primeros k números, puede ser prohibitivo debido a la complejidad del espacio. El siguiente algoritmo requiere solo O (k) para las complejidades de tiempo y espacio.

http://arxiv.org/abs/1512.00501

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

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

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

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

Usando LINQ con listas grandes (cuando es costoso tocar cada elemento) Y si puede vivir con la posibilidad de duplicados:

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

Para mi uso, tenía una lista de 100.000 elementos, y debido a que fueron extraídos de un DB, aproximadamente la mitad (o mejor) del tiempo en comparación con un rnd en toda la lista.

Tener una lista grande reducirá en gran medida las probabilidades de duplicados.

Lobo5
fuente
¡Esta solución puede tener elementos repetidos! El azar en la lista de agujeros no puede.
AxelWass
Hmm Cierto. Sin embargo, donde lo uso, eso no importa. Editó la respuesta para reflejar eso.
Wolf5
-1

Esto resolverá tu problema

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]);
                }
Cirilo
fuente
Si bien esto podría responder la pregunta, debe editar su respuesta para incluir una explicación de cómo este bloque de código responde la pregunta. Esto ayuda a proporcionar contexto y hace que su respuesta sea mucho más útil para futuros lectores.
Hoppeduppeanut