algorithm - superponer - Eligiendo k de n

superponer graficas en r

Question

Quiero elegir k elementos uniformemente al azar de un posible n sin elegir el mismo número dos veces. Hay dos enfoques triviales para esto.

1. Haz una lista de todas las n posibilidades. Mezclarlos (no es necesario mezclar todos los n números, solo k de ellos realizando los primeros k pasos de Fisher Yates). Elige la primera k . Este enfoque toma tiempo O(k) (suponiendo que la asignación de una matriz de tamaño n toma tiempo O(1) ) y espacio O(n) . Esto es un problema si k es muy pequeño en relación a n .
2. Almacena un conjunto de elementos vistos. Elija un número al azar de [0, n-1] . Mientras el elemento está en el conjunto, elija un nuevo número. Este enfoque toma espacio O(k) . El tiempo de ejecución es un poco más complicado de analizar. Si k = theta(n) , el tiempo de ejecución es O(k*lg(k))=O(n*lg(n)) porque es el problema del colector de cupones . Si k es pequeño en relación con n entonces toma un poco más que O(k) debido a la probabilidad (aunque baja) de elegir el mismo número dos veces. Esto es mejor que la solución anterior en términos de espacio, pero peor en términos de tiempo de ejecución.

Mi pregunta:

¿hay un tiempo O(k) , un algoritmo de espacio O(k) para todos los k y n ?

Answer 1

Con una tabla hash O (1) , el método de Fisher-Yates parcial puede ejecutarse en tiempo y espacio O ( k ). El truco es simplemente almacenar solo los elementos modificados de la matriz en la tabla hash.

Aquí hay un ejemplo simple en Java:

public static int[] getRandomSelection (int k, int n, Random rng) {
    if (k > n) throw new IllegalArgumentException(
        "Cannot choose " + k + " elements out of " + n + "."
    );

    HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(2*k);
    int[] output = new int[k];

    for (int i = 0; i < k; i++) {
        int j = i + rng.nextInt(n - i);
        output[i] = (hash.containsKey(j) ? hash.remove(j) : j);
        if (j > i) hash.put(j, (hash.containsKey(i) ? hash.remove(i) : i));
    }
    return output;
}

Este código asigna un HashMap de 2 × k cubos para almacenar los elementos modificados (lo que debería ser suficiente para garantizar que la tabla hash nunca se reinicie), y solo ejecuta una mezcla parcial de Fisher-Yates en ella.

Aquí hay una prueba rápida en Ideone ; elige dos elementos de cada 30,000 veces y cuenta el número de veces que se elige cada par de elementos. Para una mezcla imparcial, cada par ordenado debe aparecer aproximadamente 5,000 veces (± 100 o más), excepto en los casos imposibles en que ambos elementos serían iguales.

Answer 2

Lo que podría usar es el siguiente algoritmo (usar javascript en lugar de pseudocódigo):

var k = 3;
var n = [1,2,3,4,5,6];

// O(k) iterations
for(var i = 0, tmp; i < k; ++i) {

    // Random index O(1)
    var index = Math.floor(Math.random() * (n.length - i));

    // Output O(1)
    console.log(n[index]);

    // Swap and lookup O(1)
    tmp = n[index];
    n[index] = n[n.length - i - 1];
    n[n.length - i - 1] = tmp;
}

En resumen, intercambiará el valor seleccionado con el último elemento y en la siguiente muestra de iteración del subconjunto reducido. Esto supone que su conjunto original es totalmente único.

El almacenamiento es O (n), si desea recuperar los números como un conjunto, solo consulte las últimas k entradas de n.

Answer 3

Su segundo enfoque no toma el tiempo Theta (k log k) en promedio, toma aproximadamente n / (n-k + 1) + n / (n-k + 2) + ... + n / n operaciones, lo cual es menor que k (n / (nk)) ya que tiene k términos que son cada uno más pequeños que n / (nk). Para k <= n / 2, toma en promedio 2 * k operaciones. Para k> n / 2, puede elegir un subconjunto aleatorio de tamaño nk y tomar el complemento. Por lo tanto, esto ya es un algoritmo de tiempo y espacio promedio O (k).