Selecione N elementos aleatórios em uma Lista <T> em C #

158

Eu preciso de um algoritmo rápido para selecionar 5 elementos aleatórios de uma lista genérica. Por exemplo, eu gostaria de obter 5 elementos aleatórios de a List<string>.

JC Grubbs
fonte
11
Por Random, você quer dizer Inclusivo ou Exclusivo? IOW, o mesmo elemento pode ser escolhido mais de uma vez? (verdadeiramente aleatório) Ou depois que um elemento é escolhido, ele não pode mais ser escolhido no pool disponível?
Pretzel

Respostas:

127

Repita e para cada elemento faça a probabilidade de seleção = (número necessário) / (número restante)

Portanto, se você tivesse 40 itens, o primeiro teria uma chance de 5/40 de ser selecionado. Se for, o próximo tem uma chance de 4/39, caso contrário, tem uma chance de 5/39. Quando você chegar ao final, você terá seus 5 itens e, muitas vezes, todos eles antes disso.

Kyle Cronin
fonte
33
Eu sinto que isso é sutilmente errado. Parece que o back-end da lista será escolhido com mais frequência do que o front-end, pois o back-end verá probabilidades muito maiores. Por exemplo, se os 35 primeiros números não forem escolhidos, os 5 últimos deverão ser escolhidos. O primeiro número verá apenas uma chance de 5/40, mas esse último número verá 1/1 com mais frequência do que 5/40 vezes. Você precisará aleatoriamente a lista antes de implementar esse algoritmo.
Ankur Goel
23
ok, eu executei esse algoritmo 10 milhões de vezes em uma lista de 40 elementos, cada um com uma chance de 5/40 (0,125) ao ser selecionado e, em seguida, executei a simulação várias vezes. Acontece que isso não é distribuído igualmente. Os elementos 16 a 22 são sub-selecionados (16 = 0,123, 17 = 0,124), enquanto o elemento 34 é super-selecionado (34 = 0,129). Elementos 39 e 40 também terá underselected mas não tanto (39 = 0,1247, 40 = 0,1246)
Ankur Goel
21
@Ankur: Não acredito que seja estatisticamente significativo. Acredito que haja uma prova indutiva de que isso proporcionará uma distribuição uniforme.
recursivo
9
Repeti o mesmo teste 100 milhões de vezes e, no meu teste, o item menos escolhido foi escolhido com menos de 0,106% menos do que o item mais frequentemente escolhido.
recursivo
5
@ recursivo: A prova é quase trivial. Sabemos como selecionar K itens de K para qualquer K e como selecionar 0 itens de N para qualquer N. Suponha que conhecemos um método para selecionar uniformemente K ou K-1 itens de N-1> = K; então, podemos selecionar K itens dentre N, selecionando o primeiro item com probabilidade K / N e, em seguida, usando o método conhecido para selecionar os itens K ou K-1 ainda necessários dentre os N-1 restantes.
Ilmari Karonen 7/03/12
216

Usando linq:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
fonte
2
+1 Mas se dois elementos obtiverem o mesmo número de rnd.Next () ou similar, o primeiro será selecionado e o segundo possivelmente não (se não forem necessários mais elementos). No entanto, é suficientemente aleatório, dependendo do uso.
Lasse Espeholt
7
Eu acho que a ordem é O (n log (n)), então eu escolheria essa solução se a simplicidade do código for a principal preocupação (ou seja, com pequenas listas).
Guido
2
Mas isso não enumera e classifica a lista inteira? A menos que, por "quick", OP significava "fácil", não "performance" ...
drzaus
2
Isso funcionará apenas se OrderBy () chamar o seletor de chave apenas uma vez para cada elemento. Se o chamar sempre que desejar realizar uma comparação entre dois elementos, ele receberá um valor diferente a cada vez, o que estragará a classificação. A [documentação] ( msdn.microsoft.com/en-us/library/vstudio/… ) não diz o que diz.
Oliver Bock
2
Cuidado se YourListhouver muitos itens, mas você só deseja selecionar alguns. Nesse caso, não é uma maneira eficiente de fazê-lo.
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
fonte
27

Na verdade, esse é um problema mais difícil do que parece, principalmente porque muitas soluções matematicamente corretas falharão ao permitir que você atinja todas as possibilidades (mais sobre isso abaixo).

Primeiro, aqui estão alguns geradores fáceis de implementar, corrija se você tiver um número verdadeiramente aleatório:

(0) A resposta de Kyle, que é O (n).

(1) Gere uma lista de n pares [(0, rand), (1, rand), (2, rand), ...], classifique-os pela segunda coordenada e use o primeiro k (para você, k = 5) índices para obter seu subconjunto aleatório. Eu acho que isso é fácil de implementar, embora seja hora O (n log n).

(2) Inicie uma lista vazia s = [] que crescerá para ser o índice de k elementos aleatórios. Escolha um número r em {0, 1, 2, ..., n-1} aleatoriamente, r = rand% n e adicione-o a s. Em seguida, pegue r = rand% (n-1) e cole em s; adicione r menos # elementos em s para evitar colisões. Em seguida, pegue r = rand% (n-2) e faça a mesma coisa etc. até ter k elementos distintos em s. Isso tem o pior tempo de execução O (k ^ 2). Portanto, para k << n, isso pode ser mais rápido. Se você mantiver a classificação e rastrear quais intervalos contíguos, poderá implementá-lo em O (k log k), mas é mais trabalhoso.

@ Kyle - você está certo, pensando bem, eu concordo com sua resposta. Eu li apressadamente a princípio e pensei erroneamente que você estava indicando a escolha seqüencial de cada elemento com probabilidade fixa k / n, o que estaria errado - mas sua abordagem adaptativa parece correta para mim. Me desculpe por isso.

Ok, e agora para o kicker: assintoticamente (para k, n crescente), existem n ^ k / k! opções do subconjunto de elementos k de n elementos [esta é uma aproximação de (n escolha k)]. Se n for grande ek não for muito pequeno, esses números serão enormes. O melhor comprimento de ciclo que você pode esperar em qualquer gerador de números aleatórios padrão de 32 bits é 2 ^ 32 = 256 ^ 4. Portanto, se temos uma lista de 1000 elementos e queremos escolher 5 aleatoriamente, não há como um gerador de números aleatórios padrão atingir todas as possibilidades. No entanto, desde que você esteja de acordo com uma opção que funcione bem para conjuntos menores e sempre "pareça" aleatória, esses algoritmos deverão estar ok.

Adendo : Depois de escrever isso, percebi que é complicado implementar a idéia (2) corretamente, então queria esclarecer esta resposta. Para obter o tempo O (k log k), você precisa de uma estrutura semelhante a uma matriz que suporte pesquisas e inserções O (log m) - uma árvore binária equilibrada pode fazer isso. Usando essa estrutura para criar uma matriz chamada s, aqui está um 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

Sugiro analisar alguns casos de amostra para ver como isso implementa com eficiência a explicação acima em inglês.

Tyler
fonte
2
para (1) você pode embaralhar uma lista mais rapidamente do que a classificação, pois (2) você estará influenciando sua distribuição usando%
jk.
Dada a objeção que levantou sobre a duração do ciclo de um RNG, existe alguma maneira nós podemos construir um algoritmo que vai escolher todos os conjuntos com igual probabilidade?
Jonah
Para (1), para melhorar o O (n log (n)), você pode usar a classificação de seleção para encontrar os k menores elementos. Isso será executado em O (n * k).
Jared
@Jonah: Eu acho que sim. Vamos supor que podemos combinar vários geradores de números aleatórios independentes para criar um maior ( crypto.stackexchange.com/a/27431 ). Então você só precisa de um intervalo grande o suficiente para lidar com o tamanho da lista em questão.
Jared
16

Eu acho que a resposta selecionada é correta e muito gentil. Eu o implementei de maneira diferente, pois também queria o resultado em ordem aleatória.

    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
fonte
IMPRESSIONANTE! Realmente me ajudou!
Armstrongest
1
Você tem algum motivo para não usar o novo Random () baseado em Environment.TickCount vs. DateTime.Now.Millisecond?
Lasse Espeholt
Não, apenas não sabia que o padrão existia.
22410 Frank Schwieterman
Uma melhoria da randomSortTable: randomSortTable = someTypes.ToDictionary (x => random.NextDouble (), y => y); Salva o loop foreach.
Keltex
2
OK, com um ano de atraso, mas ... Isso não corresponde à resposta um pouco mais curta de @ ersin, e não falhará se você receber um número aleatório repetido (o caso de Ersin terá uma tendência para o primeiro item de um par repetido)
Andiih 8/09/11
12

Acabei de encontrar esse problema, e mais algumas pesquisas no Google me levaram ao problema de embaralhar aleatoriamente uma lista: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Para embaralhar completamente aleatoriamente sua lista (no local), faça o seguinte:

Para embaralhar uma matriz a 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]

Se você precisa apenas dos 5 primeiros elementos, em vez de executar i de n-1 a 1, basta executá-lo para n-5 (ou seja: n-5)

Digamos que você precise de k itens,

Isso se torna:

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

Cada item selecionado é trocado no final da matriz, portanto, os k elementos selecionados são os últimos k elementos da matriz.

Isso leva tempo O (k), onde k é o número de elementos selecionados aleatoriamente que você precisa.

Além disso, se você não quiser modificar sua lista inicial, poderá anotar todos os seus swaps em uma lista temporária, reverter a lista e aplicá-los novamente, realizando o conjunto inverso de swaps e retornando sua lista inicial sem alterar O (k) tempo de execução.

Finalmente, para o verdadeiro defensor, se (n == k), você deve parar em 1, e não em nk, pois o número inteiro escolhido aleatoriamente sempre será 0.

dhakim
fonte
Eu o implementei usando C # na minha postagem no blog: vijayt.com/post/random-select-using-fisher-yates-algorithm . Espero que ajude alguém que procura o caminho C #.
vijayst
9

Você pode usar isso, mas a encomenda acontecerá no lado do cliente

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Marwan Roushdy
fonte
Acordado. Pode não ser o melhor desempenho ou o mais aleatório, mas para a grande maioria das pessoas isso será bom o suficiente.
Richiban
8

De Dragões no algoritmo , uma interpretação em 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 seleciona indicações exclusivas da lista de itens.

Spoulson
fonte
Apenas obtenha itens suficientes na lista, mas não obtenha aleatoriamente.
culithay
2
Esta implementação está interrompida porque o uso de varresultados needede availableambos são inteiros, o que resulta needed/availablesempre em zero.
Niko
1
Parece ser uma implementação da resposta aceita.
DCShannon
6

Selecionar N itens aleatórios de um grupo não deve ter nada a ver com ordem ! A aleatoriedade é sobre imprevisibilidade e não sobre a troca de posições em um grupo. Todas as respostas que lidam com alguns tipos de pedidos devem ser menos eficientes do que as que não são. Como a eficiência é a chave aqui, publicarei algo que não altera muito a ordem dos itens.

1) Se você precisar de valores aleatórios verdadeiros , significa que não há restrições sobre quais elementos escolher (ou seja, uma vez que o item escolhido pode ser selecionado novamente):

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

Se você desativar o sinalizador de exceção, poderá escolher itens aleatórios várias vezes.

Se você tiver {1, 2, 3, 4}, poderá fornecer {1, 4, 4}, {1, 4, 3} etc para 3 itens ou até {1, 4, 3, 2, 4} para 5 itens!

Isso deve ser bem rápido, pois não tem nada para verificar.

2) Se você precisar de membros individuais do grupo sem repetição, eu usaria um dicionário (como muitos já apontaram).

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

O código é um pouco mais longo do que outras abordagens de dicionário aqui, porque não estou apenas adicionando, mas também removendo da lista, portanto são dois loops. Você pode ver aqui que eu não reordenei nada quando countse tornou igual a source.Count. Isso porque acredito que a aleatoriedade deve estar no conjunto retornado como um todo . Quero dizer, se você quer 5 itens aleatórios a partir 1, 2, 3, 4, 5, não deve importa se a sua 1, 3, 4, 2, 5ou 1, 2, 3, 4, 5, mas se você precisar de 4 itens do mesmo conjunto, então ele deve imprevisível produzir em 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4etc. Em segundo lugar, quando a contagem de itens aleatórios para ser retornado é mais da metade do grupo original, então é mais fácil removersource.Count - countitens do grupo do que adicionar countitens. Por razões de desempenho, usei em sourcevez de sourceDictobter um índice aleatório no método remove.

Portanto, se você tiver {1, 2, 3, 4}, isso pode terminar em {1, 2, 3}, {3, 4, 1} etc para 3 itens.

3) Se você precisar de valores aleatórios verdadeiramente distintos do seu grupo, levando em consideração as duplicatas do grupo original, poderá usar a mesma abordagem acima, mas a HashSetserá mais leve que um dicionário.

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

A randomsvariável é criada HashSetpara evitar que duplicatas sejam adicionadas nos casos mais raros, em que Random.Nextpode gerar o mesmo valor, especialmente quando a lista de entrada é pequena.

Então {1, 2, 2, 4} => 3 itens aleatórios => {1, 2, 4} e nunca {1, 2, 2}

{1, 2, 2, 4} => 4 itens aleatórios => exceção !! ou {1, 2, 4}, dependendo do sinalizador definido.

Alguns dos métodos de extensão que usei:

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

Se tudo tem a ver com desempenho, com dezenas de milhares de itens na lista precisando ser repetidos 10000 vezes, convém ter uma classe aleatória mais rápida do que System.Random, mas não acho que isso seja importante, considerando que o último provavelmente nunca é um gargalo, é bastante rápido ..

Edit: Se você precisar reorganizar a ordem dos itens devolvidos também, não há nada que possa superar a abordagem de Fisher-Yates de dhakim - curta, doce e simples.

nawfal
fonte
6

Estava pensando no comentário de @JohnShedletsky na resposta aceita sobre (paráfrase):

você deve conseguir isso em O (subconjunto.Length), em vez de O (originalList.Length)

Basicamente, você deve ser capaz de gerar subsetíndices aleatórios e depois retirá-los da lista original.

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

}

Se você quisesse ser ainda mais eficiente, provavelmente usaria um HashSetdos índices , não os elementos da lista real (caso tenha tipos complexos ou comparações caras);

O teste de unidade

E para garantir que não tenhamos colisões, 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
fonte
2
Boa ideia, com problemas. (1) Se sua lista maior é enorme (lida em um banco de dados, por exemplo), você realiza toda a lista, que pode exceder a memória. (2) Se K estiver próximo de N, você pesquisará bastante um índice não reivindicado em seu loop, fazendo com que o código exija uma quantidade imprevisível de tempo. Esses problemas são solucionáveis.
Paul Chernoch
1
Minha solução para o problema de debulhar é a seguinte: se K <N / 2, faça do seu jeito. Se K> = N / 2, escolha os índices que NÃO devem ser mantidos, em vez dos que devem ser mantidos. Ainda há alguns problemas, mas muito menos.
Paul Chernoch
Também percebemos que isso altera a ordem dos itens que estão sendo enumerados, o que pode ser aceitável em algumas situações, mas não em outras.
Paul Chernoch
Em média, para K = N / 2 (o pior caso para a melhoria sugerida por Paul), o algoritmo (aprimorando a melhoria) parece levar ~ 0,693 * N iterações. Agora faça uma comparação de velocidade. Isso é melhor que a resposta aceita? Para quais tamanhos de amostra?
mbomb007
6

Combinei várias das respostas acima para criar um método de extensão avaliado preguiçosamente. Meus testes mostraram que a abordagem de Kyle (Ordem (N)) é muitas vezes mais lenta que o uso de um conjunto por drzaus para propor os índices aleatórios a serem escolhidos (Ordem (K)). O primeiro realiza muito mais chamadas para o gerador de números aleatórios, além de repetir mais vezes os itens.

Os objetivos da minha implementação foram:

1) Não realize a lista completa se receber um IEnumerable que não seja um IList. Se eu receber uma sequência de um zilhão de itens, não quero ficar sem memória. Use a abordagem de Kyle para uma solução on-line.

2) Se eu puder dizer que é um IList, use a abordagem do drzaus, com uma reviravolta. Se K é mais da metade de N, corro o risco de debater, pois escolho muitos índices aleatórios várias vezes e preciso ignorá-los. Assim, componho uma lista dos índices para NÃO manter.

3) Garanto que os itens serão devolvidos na mesma ordem em que foram encontrados. O algoritmo de Kyle não exigiu alterações. O algoritmo de drzaus exigia que eu não emitisse itens na ordem em que os índices aleatórios foram escolhidos. Reuni todos os índices em um SortedSet e emito itens na ordem de índice classificada.

4) Se K for grande em comparação com N e eu inverter o sentido do conjunto, enumerarei todos os itens e testarei se o índice não está no conjunto. Isso significa que eu perco o tempo de execução da Ordem (K), mas como K está próximo de N nesses casos, não perco muito.

Aqui está o 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;
                }
            }
        }  
    } 

Eu uso um gerador especializado de números aleatórios, mas você pode simplesmente usar o C # 's Random, se quiser. (O FastRandom foi escrito por Colin Green e faz parte do SharpNEAT. Ele possui um período de 2 ^ 128-1, melhor do que muitos RNGs.)

Aqui estão os testes de unidade:

[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
fonte
Não há um erro no teste? Você tem o if (itemsList != null && k < n/2)que significa dentro do if invertSeté sempre, o falseque significa que a lógica nunca é usada.
NetMage 20/08/19
4

Estendendo-se da resposta de @ers, se alguém estiver preocupado com possíveis implementações diferentes do OrderBy, isso deve 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
difícil
fonte
3

Este é o melhor que pude apresentar em um primeiro 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 uma lista de randoms dentro de um intervalo de 1 - contagem total da lista e simplesmente puxar esses itens da lista parecia ser a melhor maneira, mas usar o Dicionário para garantir a exclusividade é algo que ainda estou pensando.

Observe também que usei uma lista de cadeias, substitua conforme necessário.

IanStallings
fonte
1
Trabalhou no primeiro tiro!
sangam
3

A solução simples que eu uso (provavelmente não é boa para listas grandes): copie a lista para uma lista temporária e, em loop, selecione aleatoriamente Item da lista temp e coloque-a na lista de itens selecionados enquanto remove-a da lista temp (para que não possa ser remarcada).

Exemplo:

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.
fonte
Remover do meio de uma lista com tanta frequência será caro. Você pode considerar o uso de uma lista vinculada para um algoritmo que exige tantas remoções. Ou, de forma equivalente, substitua o item removido por um valor nulo, mas você agitará um pouco quando escolher itens já removidos e precisar escolher novamente.
Paul Chernoch
3

Aqui você tem uma implementação baseada no Fisher-Yates Shuffle cuja complexidade do algoritmo é O (n) em que n é o tamanho do subconjunto ou da amostra, em vez do tamanho da lista, como apontou 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
fonte
2

Baseado na resposta de Kyle, aqui está minha implementação 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
fonte
2

Este método pode ser equivalente ao de Kyle.

Digamos que sua lista seja do tamanho n e você queira 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 como um encanto :)

-Alex Gilbert

Alex Gilbert
fonte
1
Isso me parece equivalente. Compare com o stackoverflow.com/br/a/48141/2449863
DCShannon
1

por que não algo assim:

 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
fonte
1

Objetivo: selecione N número de itens da origem da coleção sem duplicação. Eu criei uma extensão para qualquer coleção genérica. Aqui está como eu fiz isso:

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
fonte
0

Recentemente, fiz isso no meu projeto usando uma ideia semelhante ao ponto 1 de Tyler .
Eu estava carregando um monte de perguntas e selecionando cinco aleatoriamente. A classificação foi realizada usando um IComparer .
Todas as perguntas foram carregadas na lista a QuestionSorter, que foi classificada com a função Classificação da lista e os primeiros k elementos selecionados.

    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
alta tecnologia
fonte
0

Aqui está minha abordagem (texto completo aqui http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Ele deve ser executado em O (K) em vez de O (N), onde K é o número de elementos desejados e N é o tamanho da lista para escolher:

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
fonte
0

Isso não é tão elegante ou eficiente quanto a solução aceita, mas é rápido escrever. Primeiro, permita a matriz aleatoriamente e, em seguida, selecione os primeiros K elementos. Em python,

import numpy

N = 20
K = 5

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

print idx[:K]
apdnu
fonte
0

Eu usaria um método de extensão.

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

Memória: ~ contagem
Complexidade: O (contagem 2 )

Cardeal
fonte
0

Quando N é muito grande, o método normal que aleatoriamente embaralha os números N e seleciona, digamos, os primeiros k números, pode ser proibitivo devido à complexidade do espaço. O algoritmo a seguir requer apenas O (k) para complexidades de tempo e espaço.

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
fonte
0

Usando o LINQ com listas grandes (quando caro tocar cada elemento) E se você puder viver com a possibilidade de duplicatas:

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

Para meu uso, eu tinha uma lista de 100.000 elementos e, por serem extraídos de um banco de dados, eu aproximadamente pela metade (ou melhor) do tempo comparado a um rnd na lista inteira.

Ter uma lista grande reduzirá muito as chances de duplicatas.

Wolf5
fonte
Esta solução pode ter elementos repetidos !! O aleatório na lista de furos pode não.
AxelWass
Hmm. Verdade. Onde eu o uso, isso não importa. Editou a resposta para refletir isso.
Wolf5
-1

Isso resolverá seu 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]);
                }
Cyrille
fonte
Embora isso possa responder à pergunta, você deve editar sua resposta para incluir uma explicação de como esse bloco de código responde à pergunta. Isso ajuda a fornecer contexto e torna sua resposta muito mais útil para futuros leitores.
Hoppeduppeanut