algorithm - La manera más eficiente de elegir al azar un conjunto de enteros distintos

random language-agnostic

Question

Estoy buscando el algoritmo más eficiente para elegir al azar un conjunto de n enteros distintos, donde todos los enteros están en algún rango [0..maxValue].

Restricciones:

• maxValue es mayor que n, y posiblemente mucho más grande
• No me importa si la lista de salida está ordenada o no
• todos los enteros deben ser elegidos con la misma probabilidad

Mi idea inicial fue construir una lista de los enteros [0..maxValue] y luego extraer n elementos al azar sin reemplazo. Pero eso parece bastante ineficiente, especialmente si maxValue es grande.

¿Alguna mejor solución?

Answer 1

Aquí hay un algoritmo óptimo, suponiendo que se nos permite usar hashmaps. Se ejecuta en O (n) tiempo y espacio (y no en O (maxValue) tiempo, que es demasiado caro).

Se basa en el algoritmo de muestra aleatorio de Floyd. Ver la publicación de mi blog sobre esto para más detalles. El código está en Java:

private static Random rnd = new Random();

public static Set<Integer> randomSample(int max, int n) {
    HashSet<Integer> res = new HashSet<Integer>(n);
    int count = max + 1;
    for (int i = count - n; i < count; i++) {
        Integer item = rnd.nextInt(i + 1);
        if (res.contains(item))
            res.add(i);
        else
            res.add(item);
    }
    return res;
}

Answer 2

El truco es usar una variación de shuffle o, en otras palabras, un shuffle parcial.

function random_pick( a, n ) 
{
  N = len(a);
  n = min(n, N);
  picked = array_fill(0, n, 0); backup = array_fill(0, n, 0);
  // partially shuffle the array, and generate unbiased selection simultaneously
  // this is a variation on fisher-yates-knuth shuffle
  for (i=0; i<n; i++) // O(n) times
  { 
    selected = rand( 0, --N ); // unbiased sampling N * N-1 * N-2 * .. * N-n+1
    value = a[ selected ];
    a[ selected ] = a[ N ];
    a[ N ] = value;
    backup[ i ] = selected;
    picked[ i ] = value;
  }
  // restore partially shuffled input array from backup
  // optional step, if needed it can be ignored
  for (i=n-1; i>=0; i--) // O(n) times
  { 
    selected = backup[ i ];
    value = a[ N ];
    a[ N ] = a[ selected ];
    a[ selected ] = value;
    N++;
  }
  return picked;
}

NOTA: el algoritmo es estrictamente O(n) tanto en tiempo como en espacio , produce selecciones imparciales (es una mezcla imparcial parcial ) y no necesita hasmaps (que pueden no estar disponibles y / o generalmente esconden una complejidad detrás de su implementación, por ejemplo, buscar el tiempo no es O(1) , incluso podría ser O(n) en el peor de los casos)

adaptado desde aquí

Answer 3

Generador congruencia lineal modulo maxValue + 1. Estoy seguro de haber escrito esta respuesta antes, pero no puedo encontrarla ...

Answer 4

Mi solución es la misma que la de Mark Byers. Toma O (n ^ 2) tiempo, por lo tanto es útil cuando n es mucho más pequeño que maxValue. Aquí está la implementación en Python:

def pick(n, maxValue):
    chosen = []
    for i in range(n):
        r = random.randint(0, maxValue - i)
        for e in chosen:
            if e <= r:
                r += 1
            else:
                break;
        bisect.insort(chosen, r)
    return chosen

Answer 5

Si selecciona M elementos de N , la estrategia cambia dependiendo de si M es del mismo orden que N o mucho menos (es decir, menos de aproximadamente N / log N).

Si son de un tamaño similar, revisa cada elemento de 1 a N Mantiene un registro de cuántos elementos tiene hasta ahora (llamémosle m elementos sacados de n que ha pasado), y luego toma el siguiente número con probabilidad (Mm)/(Nn) y deséchelo de otra manera. Luego actualiza m y n apropiadamente y continúa. Este es un algoritmo O(N) con bajo costo constante.

Si, por otro lado, M es significativamente menor que N , entonces una estrategia de remuestreo es buena. Aquí deberás ordenar M para que puedas encontrarlos rápidamente (y eso te costará O(M log M) tiempo - pégalos en un árbol, por ejemplo). Ahora selecciona números uniformemente de 1 a N e insértelos en su lista. Si encuentras una colisión, elige otra vez. Chocará a la M/N del tiempo (en realidad, se está integrando de 1 / N a M / N), lo que le obligará a volver a elegir (recursivamente), por lo que esperará tomar M/(1-M/N) selecciones para completar el proceso. Por lo tanto, su costo para este algoritmo es aproximadamente O(M*(N/(NM))*log(M)) .

Estos son métodos tan simples que puede implementar ambos, suponiendo que tenga acceso a un árbol ordenado, y elegir el que sea apropiado dada la fracción de números que se seleccionarán.

(Tenga en cuenta que seleccionar números es simétrico y no seleccionarlos, por lo que si M es casi igual a N , entonces puede usar la estrategia de remuestreo, pero elija esos números para no incluirlos, esto puede ser una ganancia, incluso si tiene que empujar todo casi N números alrededor, si su generación de números aleatorios es costosa).

Answer 6

Una forma de hacerlo sin generar la matriz completa.

Digamos que quiero un subconjunto de m elementos seleccionado al azar de un conjunto {x1, ..., xn} donde m <= n.

Considera el elemento x1. Agrego x1 a mi subconjunto con probabilidad m / n.

• Si agrego x1 a mi subconjunto, entonces reduzco mi problema a seleccionar (m - 1) ítems de {x2, ..., xn}.
• Si no agrego x1 a mi subconjunto, reduzco mi problema para seleccionar m elementos de {x2, ..., xn}.

Enjabona, enjuaga y repite hasta que m = 0.

Este algoritmo es O (n) donde n es el número de elementos que tengo que considerar.

Prefiero imaginar que hay un algoritmo O (m) donde en cada paso considera cuántos elementos eliminar del "frente" del conjunto de posibilidades, pero no me he convencido de una buena solución y tengo que hacer un poco ¡trabaja ahora!

Answer 7

ACTUALIZACIÓN: estoy equivocado. La salida de esto no está uniformemente distribuida. Detalles sobre por qué están aquí .

Creo que este algoritmo a continuación es óptimo . Es decir, no se puede obtener un mejor rendimiento que este.

Para elegir n números de m números, el mejor algoritmo ofrecido hasta ahora se presenta a continuación. Su peor complejidad de tiempo de ejecución es O (n) , y solo necesita una única matriz para almacenar los números originales. Mezcla parcialmente los primeros n elementos de la matriz original, y luego elige los primeros n números mezclados como su solución.

Este también es un programa de C en pleno funcionamiento. Lo que encuentras es:

• getrand función: Esto es solo un PRNG que devuelve un número desde 0 hasta upto .
• Función randselect : Esta es la función que randmoly elige n números únicos de m muchos números. De esto se trata esta pregunta.
• Función main : Esto es solo para demostrar un uso para otras funciones, para que pueda compilarlo en un programa y divertirse.

#include <stdio.h>
#include <stdlib.h>

int getrand(int upto) {
    long int r;
    do {
        r = rand();
    } while (r > upto);
    return r;
}

void randselect(int *all, int end, int select) {
    int upto = RAND_MAX - (RAND_MAX % end);
    int binwidth = upto / end;

    int c;
    for (c = 0; c < select; c++) {
        /* randomly choose some bin */
        int bin = getrand(upto)/binwidth;

        /* swap c with bin */
        int tmp = all[c];
        all[c] = all[bin];
        all[bin] = tmp;
    }
}

int main() {
    int end = 1000;
    int select = 5;

    /* initialize all numbers up to end */
    int *all = malloc(end * sizeof(int));
    int c;
    for (c = 0; c < end; c++) {
        all[c] = c;
    }

    /* select select unique numbers randomly */
    srand(0);
    randselect(all, end, select);
    for (c = 0; c < select; c++) printf("%d ", all[c]);
    putchar(''/n'');

    return 0;
}

Aquí está la salida de un código de ejemplo donde aleatoriamente obtengo 4 permutaciones de un grupo de 8 números por 100,000,000 muchas veces. Luego uso esas permutaciones para calcular la probabilidad de que ocurra cada permutación única. Luego los clasifico por esta probabilidad. Observa que los números son bastante cercanos, lo que creo que significa que está distribuido uniformemente. La probabilidad teórica debe ser 1/1680 = 0.000595238095238095 . Tenga en cuenta cómo la prueba empírica es cercana a la teórica.

Answer 8

Para valores pequeños de maxValue tales que es razonable generar una matriz de todos los enteros en la memoria, entonces puede usar una variación de la combinación aleatoria de Fisher-Yates, excepto que solo realiza los primeros n pasos.

Si n es mucho más pequeño que maxValue y no desea generar toda la matriz, puede usar este algoritmo:

1. Mantenga una lista ordenada del número elegido hasta ahora, inicialmente vacío.
2. Elija un número aleatorio x entre 0 y maxValue - (elementos en l )
3. Para cada número en l si es menor o igual a x , agregue 1 a x
4. Agregue el valor ajustado de x en la lista ordenada y repita.

Si n está muy cerca de maxValue entonces puedes elegir aleatoriamente los elementos que no están en el resultado y luego encontrar el complemento de ese conjunto.

Aquí hay otro algoritmo que es más simple pero que tiene un tiempo de ejecución potencialmente ilimitado:

1. Mantenga un conjunto de elementos seleccionados hasta ahora, inicialmente vacíos.
2. Elija un número al azar entre 0 y maxValue .
3. Si el número no está en s , agréguelo a s .
4. Regrese al paso 2 hasta que s tenga n elementos.

En la práctica, si n es pequeño y maxValue es grande, esto será lo suficientemente bueno para la mayoría de los propósitos.