Elegir al azar elemento de la matriz que satisface ciertas propiedades

Question

Supongamos que tengo una lista, llamada elements, cada uno de los cuales hace o no satisface alguna p propiedad booleana. Quiero elegir uno de los elementos que satisfacen p por azar con una distribución uniforme. No sé de antemano cuántos elementos satisfacen esta p propiedad.

¿El siguiente código hacer esto:?

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) devuelve un k int azar con 0 <= k < n.)

Answer 1

Funciona matemáticamente. Puede ser probado por inducción.

claramente funciona para n = 1 elemento satisfacer p.

Para n + 1 elementos, elegiremos el elemento n + 1 con una probabilidad de 1 / (n + 1), por lo que su probabilidad es OK. Pero ¿cómo que la probabilidad de efecto final de la elección de uno de los n elementos anteriores?

Cada uno de los n antes tenían una probabilidad de ser seleccionado con probabilidad 1 / n, hasta que encontramos elemento n + 1. Ahora, después de encontrar n + 1, hay un / (n + 1) probabilidad de 1 elemento que n + 1 se elige, por lo que hay a n / (n + 1) de que el elemento elegido previamente permanece elegido. Lo que significa que su probabilidad final de ser el elegido después de n + 1 hallazgos es 1 / n * (n / n + 1) = 1 / n + 1 - que es la probabilidad que queremos para todos + 1 n elementos para la distribución uniforme.

Si funciona para n = 1, y funciona para n + 1 n dado, entonces funciona para todo n.

Answer 2

Sí, creo que sí.

La primera vez que se encuentra un elemento coincidente, que sin duda recogerlo. La próxima vez, te va a recoger el nuevo valor con una probabilidad de 1/2, por lo que cada uno de los dos elementos tienen la misma oportunidad. La siguiente vez, tienes que elegir el nuevo valor con una probabilidad de 1/3, dejando a cada uno de los otros elementos con una probabilidad de 1/2 * 2/3 = 1/3 también.

Estoy tratando de encontrar un artículo de Wikipedia sobre esta estrategia, pero no tan lejos ...

Tenga en cuenta que en general, sólo está recogiendo una muestra aleatoria de una secuencia de longitud desconocida. Su secuencia pasa a ser generada mediante la adopción de una secuencia inicial y filtrarla, pero el algoritmo no requiere que una parte del todo.

pensé que había conseguido un operador de LINQ en MoreLINQ para hacer esto, pero no puedo encontrar en el repositorio ... EDIT: Afortunadamente, todavía existe desde esta respuesta :

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 práctica de la programación , pág. 70, (El Markov Chain Algorithm) existe un algoritmo similar para que:

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

  

"Observe el algoritmo para la selección de uno   artículo al azar cuando no sabemos cómo   muchos artículos que hay. La variable   nmatch cuenta el número de coincidencias mientras   la lista se escanea. La expresión

rand() % ++nmatch == 0

     

incrementos nmatch y es entonces la verdadera   con una probabilidad de 1 / nmatch. "

Answer 4

decowboy tiene una buena prueba de que esto funciona en TopCoder

Answer 5

Para mayor claridad, me gustaría probar:

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 mí, eso hace que sea mucho más clara de lo que estás tratando de hacer y es auto-documentado. Además de eso, es más simple y elegante, y ahora es obvio que cada uno será elegido con una distribución uniforme.