Escolha elemento da matriz aleatório satisfazer determinada propriedade

Question

Suponha que eu tenho uma lista, chamada elements, cada um dos quais tem ou não satisfazer algumas p propriedade booleana. Quero escolher um dos elementos que satisfaz p por aleatória com distribuição uniforme. Eu não sei de antemão como muitos itens satisfazer esta propriedade p.

Será o seguinte código fazer isso:?

pickRandElement(elements, p)
     randElement = null
     count = 0
     foreach element in elements
          if (p(element))
               count = count + 1
               if (randInt(count) == 0)
                    randElement = element

     return randElement

(randInt(n) retorna um k int aleatório com 0 <= k < n.)

Answer 1

Ele funciona matematicamente. Pode ser provado por indução.

É evidente que funciona para n = 1 elemento satisfazendo p.

Para n + 1 elementos, vamos escolher o elemento n + 1 com probabilidade 1 / (n + 1), pelo que a sua probabilidade é OK. Mas como é que esse efeito a probabilidade fim de escolher um dos elementos antes n?

cada um dos N antes tinham uma probabilidade de ser seleccionado com probabilidade 1 / n, até que encontramos elemento n + 1. Agora, depois de encontrar n + 1, não é um / (n + 1) uma possibilidade de que o elemento n + 1 é escolhida, para que haja uma possibilidade n / (n + 1) que os restos de elementos previamente escolhidos escolhido. O que significa que a sua probabilidade final de ser o escolhido após n + 1 encontra é 1 / n * (n / n + 1) = 1 / n + 1 - que é a probabilidade de que queremos para todos + 1 n elementos para distribuição uniforme.

Se ele funciona para n = 1, e ele funciona para n + 1 dado n, então ele funciona para todos n.

Answer 2

Sim, eu acredito que sim.

A primeira vez que você encontrar um elemento correspondente, você definitivamente buscá-lo. A próxima vez, você escolhe o novo valor com uma probabilidade de 1/2, então cada um dos dois elementos têm uma chance igual. O tempo seguinte, você escolhe o novo valor com uma probabilidade de 1/3, deixando cada um dos outros elementos com uma probabilidade de 1/2 * 2/3 = 1/3 bem.

Eu estou tentando encontrar um artigo da Wikipedia sobre esta estratégia, mas não tão longe ...

Note que mais geralmente, você está apenas pegando uma amostra aleatória de uma sequência de comprimento desconhecido. Sua seqüência acontece a ser gerado por tomar uma seqüência inicial e filtrá-la, mas o algoritmo não exige que parte em tudo.

Eu pensei que eu tenho um operador LINQ em MoreLINQ para fazer isso, mas eu não posso encontrá-lo no repositório ... EDIT: Felizmente, ele ainda existe a partir de esta resposta :

public static T RandomElement<T>(this IEnumerable<T> source,
                                 Random rng)
{
    T current = default(T);
    int count = 0;
    foreach (T element in source)
    {
        count++;
        if (rng.Next(count) == 0)
        {
            current = element;
        }            
    }
    if (count == 0)
    {
        throw new InvalidOperationException("Sequence was empty");
    }
    return current;
}

Answer 3

Em The Practice of Programming , pg. 70, (A Cadeias de Markov Algorithm) há um algoritmo semelhante para isso:

[...]
  nmatch = 0;
  for ( /* iterate list */ )
    if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
      w = suf->word;
[...]

"Aviso o algoritmo para selecionar um item em aleatória quando não sabemos como muitos itens existem. a variável contagens nmatch o número de correspondências como a lista é digitalizado. A expressão

rand() % ++nmatch == 0

incrementos nmatch e depois é verdadeira com probabilidade 1 / nmatch ".

Answer 4

decowboy tem uma prova de bom que isso funciona no TopCoder

Answer 5

Por uma questão de clareza, gostaria de tentar:

pickRandElement(elements, p)
     OrderedCollection coll = new OrderedCollection
     foreach element in elements
          if (p(element))
               coll.add(element)
     if (coll.size == 0) return null
     else return coll.get(randInt(coll.size))

Para mim, isso faz com que seja muito mais claro o que você está tentando fazer e é auto-documentado. Além disso, é mais simples e mais elegante, e é agora óbvio que cada um vai ser pego com uma distribuição uniforme.