Choisissez un élément de tableau aléatoire satisfaisant certains biens

Question

Supposons que j'ai une liste, appelée elements, dont chacun fait ou ne satisfait pas certains p de propriété booléenne. Je veux choisir l'un des éléments qui satisfait p par hasard avec une distribution uniforme. Je ne sais pas à l'avance combien d'éléments satisfont à cette p de propriété.

Est-ce que le code suivant faire:?

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) renvoie un k int aléatoire avec 0 <= k < n.)

Answer 1

Il fonctionne mathématiquement. Peut être prouvé par induction.

fonctionne Il est clair que pour n = 1 élément satisfaisant p.

Pour n + 1 éléments, nous choisirons l'élément n + 1 avec une probabilité 1 / (n + 1), de sorte que sa probabilité est OK. Mais comment cet effet la probabilité de fin de choisir l'un des n éléments précédents?

Chacun des n avant ont eu la chance d'être sélectionnés avec une probabilité 1 / n, jusqu'à ce que nous avons trouvé l'élément n + 1. Maintenant, après avoir trouvé n + 1, il y a un 1 / (n + 1) chance que l'élément n + 1 est choisi, donc il y a un n / (n + 1) chance que l'élément choisi précédemment reste choisi. Ce qui signifie que la probabilité finale d'être choisie après la n + 1 trouve est 1 / n * (n / n + 1) = 1 / n + 1 - qui est la probabilité que nous voulons pour tous les n + 1 éléments pour une distribution uniforme.

Si cela fonctionne pour n = 1, et il fonctionne pour n + 1 n donné, cela fonctionne pour tout n.

Answer 2

Oui, je le crois.

La première fois que vous rencontrez un élément correspondant, vous choisissez certainement. La prochaine fois, vous choisissez la nouvelle valeur avec une probabilité de 1/2, donc chacun des deux éléments ont une chance égale. La prochaine fois, vous choisissez la nouvelle valeur avec une probabilité de 1/3, laissant chacun des autres éléments avec une probabilité de 1/2 * 2/3 = 1/3 ainsi.

Je suis en train de trouver un article de Wikipedia sur cette stratégie, mais à ce jour ne ...

Notez que plus généralement, vous il suffit de prendre un échantillon aléatoire sur une séquence de longueur inconnue. Votre séquence arrive à générer en prenant une séquence initiale et le filtrage, mais l'algorithme ne nécessite pas partie du tout.

Je pensais que je suis un opérateur LINQ dans MoreLINQ de le faire, mais je ne peux pas le trouver dans le référentiel ... EDIT: Heureusement, il existe encore de cette réponse :

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

La pratique de la programmation , p. 70, (La chaîne de Markov Algorithm), il existe un algorithme similaire à ce qui suit:

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

  

"Notez l'algorithme de sélection d'un   point au hasard quand on ne sait pas comment   de nombreux articles il y a. la variable   nmatch compte le nombre de matches que   la liste est numérisée. L'expression

rand() % ++nmatch == 0

     

incréments nmatch et est donc vrai   avec la probabilité 1 / nmatch. "

Answer 4

decowboy a une belle preuve que cela fonctionne sur TopCoder

Answer 5

Par souci de clarté, je voudrais essayer:

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

Pour moi, cela rend beaucoup plus clairement ce que vous essayez de faire et est autodocumenté. En plus de cela, il est plus simple et plus élégant, et il est maintenant évident que chacun seront sélectionnés avec une distribution uniforme.