with - statistics python

¿Cómo muestrear incrementalmente sin reemplazo?

Question

Python tiene my_sample = random.sample(range(100), 10) para muestrear aleatoriamente sin reemplazo de [0, 100) .

Supongamos que he muestreado n tales números y ahora quiero muestrear uno más sin reemplazo (sin incluir ninguno de los n muestreados anteriormente), ¿cómo hacerlo de manera súper eficiente?

actualización: cambiado de "razonablemente eficiente" a "súper eficiente" (pero ignorando factores constantes)

Answer 1

El camino corto

Si el número muestreado es mucho menor que la población, solo muestree, verifique si ha sido elegido y repítalo mientras tanto. Esto puede parecer una tontería, pero tienes una posibilidad decreciente exponencial de elegir el mismo número, por lo que es mucho más rápido que O(n) si tienes un pequeño porcentaje sin elegir.

El largo camino

Python utiliza un Mersenne Twister como su PRNG, que es bueno adequate . Podemos usar otra cosa completamente para poder generar números no superpuestos de una manera predecible.

Aquí está el secreto:

• Los residuos cuadráticos, x² mod p , son únicos cuando 2x < p y p son primos.

• Si "volteas" el residuo, p - (x² % p) , dado este tiempo también que p = 3 mod 4 , los resultados serán los espacios restantes.

• Esta no es una dispersión numérica muy convincente, por lo que puede aumentar la potencia, agregar algunas constantes de fudge y luego la distribución es bastante buena.

Primero necesitamos generar primos:

from itertools import count
from math import ceil
from random import randrange

def modprime_at_least(number):
    if number <= 2:
        return 2

    number = (number // 4 * 4) + 3
    for number in count(number, 4):
        if all(number % factor for factor in range(3, ceil(number ** 0.5)+1, 2)):
            return number

Usted podría preocuparse por el costo de generar los números primos. Para elementos de 10⁶ esto toma una décima de milisegundo. Ejecutar [None] * 10**6 toma más tiempo que eso, y como solo se calcula una vez, esto no es un problema real.

Además, el algoritmo no necesita un valor exacto para el primo; solo necesita algo que, como mucho, sea un factor constante mayor que el número de entrada. Esto es posible guardando una lista de valores y buscándolos. Si realiza una exploración lineal, eso es O(log number) y si realiza una búsqueda binaria es O(log number of cached primes) . De hecho, si utiliza el galloping , puede bajar esto a O(log log number) , que es básicamente constante ( log log googol = 2 ).

Luego implementamos el generador.

def sample_generator(up_to):
    prime = modprime_at_least(up_to+1)

    # Fudge to make it less predictable
    fudge_power = 2**randrange(7, 11)
    fudge_constant = randrange(prime//2, prime)
    fudge_factor = randrange(prime//2, prime)

    def permute(x):
        permuted = pow(x, fudge_power, prime) 
        return permuted if 2*x <= prime else prime - permuted

    for x in range(prime):
        res = (permute(x) + fudge_constant) % prime
        res = permute((res * fudge_factor) % prime)

        if res < up_to:
            yield res

Y comprueba que funciona:

set(sample_generator(10000)) ^ set(range(10000))
#>>> set()

Ahora, lo bueno de esto es que si ignora la prueba de primacía, que es aproximadamente O(√n) donde n es el número de elementos, este algoritmo tiene complejidad de tiempo O(k) , donde k es el tamaño de la muestra y O(1) uso de memoria! Técnicamente esto es O(√n + k) , pero prácticamente es O(k) .

Requisitos:

1. No requiere un PRNG probado. Este PRNG es mucho mejor que el generador lineal congruente (que es popular; Java lo usa ) pero no está tan probado como un Mersenne Twister.

2. Primero no genera ningún elemento con una función diferente. Esto evita duplicados a través de las matemáticas, no cheques. La siguiente sección muestro cómo eliminar esta restricción.

3. El método corto debe ser insuficiente ( k debe acercarse a n ). Si k es solo la mitad n , solo sigue mi sugerencia original.

Ventajas:

1. Ahorro de memoria extrema. Esto requiere memoria constante ... ¡ni siquiera O(k) !

2. Tiempo constante para generar el siguiente elemento. En realidad, esto también es bastante rápido en términos constantes: no es tan rápido como el Mersenne Twister incorporado, pero está dentro de un factor de 2.

3. Frescura.

Para eliminar este requisito:

Primero no genera ningún elemento con una función diferente. Esto evita duplicados a través de las matemáticas, no cheques.

He hecho el mejor algoritmo posible en complejidad de tiempo y espacio, que es una extensión simple de mi generador anterior.

Aquí está el resumen ( n es la longitud del grupo de números, k es el número de claves "extrañas"):

Tiempo de inicialización O(√n) ; O(log log n) para todas las entradas razonables

Este es el único factor de mi algoritmo que técnicamente no es perfecto en lo que respecta a la complejidad algorítmica, gracias al costo de O(√n) . En realidad, esto no será problemático porque el cálculo previo lo reduce a O(log log n) que es inmensamente cercano al tiempo constante.

El costo se amortiza gratis si agota el iterable por un porcentaje fijo.

Este no es un problema práctico.

Amortizado tiempo de generación de clave O(1)

Obviamente, esto no se puede mejorar.

Tiempo de generación de clave O(k) peor de los casos

Si tiene claves generadas desde el exterior, con solo el requisito de que no debe ser una clave que este generador ya haya producido, estas se llamarán "claves externas". Se asume que las claves foráneas son totalmente aleatorias. Como tal, cualquier función que pueda seleccionar elementos del grupo puede hacerlo.

Debido a que puede haber cualquier número de claves externas y pueden ser totalmente aleatorias, el peor de los casos para un algoritmo perfecto es O(k) .

Peor caso de complejidad O(k)

Si las claves externas se asumen totalmente independientes, cada una representa un elemento de información distinto. Por lo tanto, todas las claves deben ser almacenadas. El algoritmo pasa a descartar claves cada vez que ve una, por lo que el costo de la memoria se borrará durante la vida útil del generador.

El algoritmo

Bueno, son mis dos algoritmos. En realidad es bastante simple:

def sample_generator(up_to, previously_chosen=set(), *, prune=True):
    prime = modprime_at_least(up_to+1)

    # Fudge to make it less predictable
    fudge_power = 2**randrange(7, 11)
    fudge_constant = randrange(prime//2, prime)
    fudge_factor = randrange(prime//2, prime)

    def permute(x):
        permuted = pow(x, fudge_power, prime) 
        return permuted if 2*x <= prime else prime - permuted

    for x in range(prime):
        res = (permute(x) + fudge_constant) % prime
        res = permute((res * fudge_factor) % prime)

        if res in previously_chosen:
            if prune:
                previously_chosen.remove(res)

        elif res < up_to:
            yield res

El cambio es tan simple como agregar:

if res in previously_chosen:
    previously_chosen.remove(res)

Puede agregar a previously_chosen en cualquier momento agregando al set que pasó. De hecho, también puede eliminar del conjunto para agregar nuevamente al grupo potencial, aunque esto solo funcionará si sample_generator aún no lo ha sample_generator o lo salté con prune=False .

Así que hay. Es fácil ver que cumple todos los requisitos, y es fácil ver que los requisitos son absolutos. Tenga en cuenta que si no tiene un conjunto, todavía cumple con sus peores casos al convertir la entrada en un conjunto, aunque aumenta la sobrecarga.

Probando la calidad del RNG

Sentí curiosidad por lo bueno que es realmente este PRNG, estadísticamente hablando.

¡Algunas búsquedas rápidas me llevan a crear estas tres pruebas, que parecen mostrar buenos resultados!

En primer lugar, algunos números aleatorios:

N = 1000000

my_gen = list(sample_generator(N))

target = list(range(N))
random.shuffle(target)

control = list(range(N))
random.shuffle(control)

Estas son listas "barajadas" de 10⁶ números del 0 al 10⁶-1 , uno que utiliza nuestro divertido PRNG y el otro que utiliza un Mersenne Twister como referencia. El tercero es el control.

Aquí hay una prueba que analiza la distancia promedio entre dos números aleatorios a lo largo de la línea. Las diferencias se comparan con el control:

from collections import Counter

def birthdat_calc(randoms):
    return Counter(abs(r1-r2)//10000 for r1, r2 in zip(randoms, randoms[1:]))

def birthday_compare(randoms_1, randoms_2):
    birthday_1 = sorted(birthdat_calc(randoms_1).items())
    birthday_2 = sorted(birthdat_calc(randoms_2).items())

    return sum(abs(n1 - n2) for (i1, n1), (i2, n2) in zip(birthday_1, birthday_2))

print(birthday_compare(my_gen, target), birthday_compare(control, target))
#>>> 9514 10136

Esto es menor que la varianza de cada uno.

Aquí hay una prueba que toma 5 números por turno y ve en qué orden están los elementos. Deben distribuirse uniformemente entre las 120 órdenes posibles.

def permutations_calc(randoms):
    permutations = Counter()        

    for items in zip(*[iter(randoms)]*5):
        sorteditems = sorted(items)
        permutations[tuple(sorteditems.index(item) for item in items)] += 1

    return permutations

def permutations_compare(randoms_1, randoms_2):
    permutations_1 = permutations_calc(randoms_1)
    permutations_2 = permutations_calc(randoms_2)

    keys = sorted(permutations_1.keys() | permutations_2.keys())

    return sum(abs(permutations_1[key] - permutations_2[key]) for key in keys)

print(permutations_compare(my_gen, target), permutations_compare(control, target))
#>>> 5324 5368

Esto es nuevamente menor que la varianza de cada uno.

Aquí hay una prueba que ve cuánto tiempo "corre" son, alias. Secciones de aumentos o disminuciones consecutivas.

def runs_calc(randoms):
    runs = Counter()

    run = 0
    for item in randoms:
        if run == 0:
            run = 1

        elif run == 1:
            run = 2
            increasing = item > last

        else:
            if (item > last) == increasing:
                run += 1

            else:
                runs[run] += 1
                run = 0

        last = item

    return runs

def runs_compare(randoms_1, randoms_2):
    runs_1 = runs_calc(randoms_1)
    runs_2 = runs_calc(randoms_2)

    keys = sorted(runs_1.keys() | runs_2.keys())

    return sum(abs(runs_1[key] - runs_2[key]) for key in keys)

print(runs_compare(my_gen, target), runs_compare(control, target))
#>>> 1270 975

La variación aquí es muy grande, y en varias ejecuciones parece que hay una dispersión uniforme de ambas. Como tal, esta prueba se pasa.

Se me mencionó un generador lineal congruente, como posiblemente "más fructífero". He hecho un LCG mal implementado por mi cuenta, para ver si esta es una declaración precisa.

Los LCG, AFAICT, son como generadores normales en el sentido de que no están hechos para ser cíclicos . Por lo tanto la mayoría de las referencias que miré, también conocido como Wikipedia, cubrió solo lo que define el período, no cómo hacer un LCG fuerte de un período específico. Esto puede haber afectado los resultados.

Aquí va:

from operator import mul
from functools import reduce

# Credit http://.com/a/16996439/1763356
# Meta: Also Tobias Kienzler seems to have credit for my
#       edit to the post, what''s up with that?
def factors(n):
    d = 2
    while d**2 <= n:
        while not n % d:
            yield d
            n //= d
        d += 1
    if n > 1:
       yield n

def sample_generator3(up_to):
    for modulier in count(up_to):
        modulier_factors = set(factors(modulier))
        multiplier = reduce(mul, modulier_factors)
        if not modulier % 4:
            multiplier *= 2

        if multiplier < modulier - 1:
            multiplier += 1
            break

    x = randrange(0, up_to)

    fudge_constant = random.randrange(0, modulier)
    for modfact in modulier_factors:
        while not fudge_constant % modfact:
            fudge_constant //= modfact

    for _ in range(modulier):
        if x < up_to:
            yield x

        x = (x * multiplier + fudge_constant) % modulier

Ya no buscamos números primos, pero sí necesitamos hacer algunas cosas extrañas con factores.

• modulier ≥ up_to > multiplier, fudge_constant > 0
• a - 1 debe ser divisible por cada factor en el modulier ...
• ... mientras que fudge_constant debe ser coprime con modulier

Tenga en cuenta que estas no son reglas para una LCG sino para una LCG con un período completo, que obviamente es igual al mod ulier.

Lo hice como tal:

• Pruebe cada modulier al menos up_to , deteniéndose cuando se cumplan las condiciones
  • Haz un conjunto de sus factores,
  • Sea multiplier el producto de 𝐅 con duplicados eliminados
  • Si el multiplier no es menor que el modulier , continúe con el siguiente modulier
  • Sea fudge_constant un número menor que el modulier , elegido al azar
  • Eliminar los factores de fudge_constant que están en

Esta no es una forma muy buena de generarlo, pero no veo por qué afectaría la calidad de los números, aparte del hecho de que los fudge_constant bajos de fudge_constant y el multiplier son más comunes que un generador perfecto para estos.

De todos modos, los resultados son espantosos :

print(birthday_compare(lcg, target), birthday_compare(control, target))
#>>> 22532 10650

print(permutations_compare(lcg, target), permutations_compare(control, target))
#>>> 17968 5820

print(runs_compare(lcg, target), runs_compare(control, target))
#>>> 8320 662

En resumen, mi RNG es bueno y un generador lineal congruente no lo es. Teniendo en cuenta que Java se sale con un generador lineal congruente (aunque solo utiliza los bits más bajos), esperaría que mi versión fuera más que suficiente.

Answer 2

Aquí hay una manera que no construye la diferencia establecida explícitamente. Pero sí utiliza una forma de lógica de "aceptar / rechazar" de @ Veedrac. Si no estás dispuesto a mutar la secuencia base a medida que avanzas, me temo que eso es inevitable:

def sample(n, base, forbidden):
    # base is iterable, forbidden is a set.
    # Every element of forbidden must be in base.
    # forbidden is updated.
    from random import random
    nusable = len(base) - len(forbidden)
    assert nusable >= n
    result = []
    if n == 0:
        return result
    for elt in base:
        if elt in forbidden:
            continue
        if nusable * random() < n:
            result.append(elt)
            forbidden.add(elt)
            n -= 1
            if n == 0:
                return result
        nusable -= 1
    assert False, "oops!"

Aquí hay un pequeño conductor:

base = list(range(100))
forbidden = set()
for i in range(10):
    print sample(10, base, forbidden)

Answer 3

Bien, un último intento ;-) Al costo de mutar la secuencia base, esto no ocupa espacio adicional, y requiere un tiempo proporcional a n para cada llamada de sample(n) :

class Sampler(object):
    def __init__(self, base):
        self.base = base
        self.navail = len(base)
    def sample(self, n):
        from random import randrange
        if n < 0:
            raise ValueError("n must be >= 0")
        if n > self.navail:
            raise ValueError("fewer than %s unused remain" % n)
        base = self.base
        for _ in range(n):
            i = randrange(self.navail)
            self.navail -= 1
            base[i], base[self.navail] = base[self.navail], base[i]
        return base[self.navail : self.navail + n]

Pequeño conductor

s = Sampler(list(range(100)))
for i in range(9):
    print s.sample(10)
    print s.sample(1)
print s.sample(1)

En efecto, esto implementa un random.shuffle() reanudable, que se random.shuffle() después de que se hayan seleccionado n elementos. base no se destruye, sino que se permuta.

Answer 4

Esta es mi versión de Knuth Shuffle, que fue publicada por primera vez por Tim Peters , prettificada por Eric y luego bien optimizada para el espacio por nigromante .

Esto se basa en la versión de Eric, ya que de hecho encontré su código muy bonito :).

import random
def shuffle_gen(n):
    # this is used like a range(n) list, but we don’t store
    # those entries where state[i] = i.
    state = dict()
    for remaining in xrange(n, 0, -1):
        i = random.randrange(remaining)
        yield state.get(i,i)
        state[i] = state.get(remaining - 1,remaining - 1)
        # Cleanup – we don’t need this information anymore
        state.pop(remaining - 1, None)

uso:

out = []
gen = shuffle_gen(100)
for n in range(100):
    out.append(gen.next())
print out, len(set(out))

Answer 5

OK aquí vamos. Este debería ser el algoritmo no probabilístico más rápido posible. Tiene un tiempo de ejecución de O(k⋅log²(s) + f⋅log(f)) ⊂ O(k⋅log²(f+k) + f⋅log(f))) y espacio O(k+f) . f es la cantidad de números prohibidos, s es la longitud de la racha más larga de números prohibidos. La expectativa para eso es más complicada, pero obviamente está limitada por f . Si asume que s^log₂(s) es mayor que para f o simplemente no está contento con el hecho de que s es una vez más probabilístico, puede cambiar la parte de registro a una búsqueda de bisección forbidden[pos:] para obtener O(k⋅log(f+k) + f⋅log(f)) .

La implementación real aquí es O(k⋅(k+f)+f⋅log(f)) , ya que la inserción en la lista de forbid es O(n) . Esto es fácil de arreglar reemplazando esa lista con una lista ordenada por blist .

También agregué algunos comentarios, porque este algoritmo es ridículamente complejo. La parte lin hace lo mismo que la parte de log , pero necesita s lugar de log²(s) de log²(s) .

import bisect
import random

def sample(k, end, forbid):
    forbidden = sorted(forbid)
    out = []
    # remove the last block from forbidden if it touches end
    for end in reversed(xrange(end+1)):
        if len(forbidden) > 0 and forbidden[-1] == end:
            del forbidden[-1]
        else:
            break

    for i in xrange(k):
        v = random.randrange(end - len(forbidden) + 1)
        # increase v by the number of values < v
        pos = bisect.bisect(forbidden, v)
        v += pos
        # this number might also be already taken, find the
        # first free spot
        ##### linear
        #while pos < len(forbidden) and forbidden[pos] <=v:
        #    pos += 1
        #    v += 1
        ##### log
        while pos < len(forbidden) and forbidden[pos] <= v:
            step = 2
            # when this is finished, we know that:
            # • forbidden[pos + step/2] <= v + step/2
            # • forbidden[pos + step]   >  v + step
            # so repeat until (checked by outer loop):
            #   forbidden[pos + step/2] == v + step/2
            while (pos + step <= len(forbidden)) and /
                  (forbidden[pos + step - 1] <= v + step - 1):
                step = step << 1
            pos += step >> 1
            v += step >> 1

        if v == end:
            end -= 1
        else:
            bisect.insort(forbidden, v)
        out.append(v)
    return out

Ahora, para comparar eso con el "truco" (y la implementación predeterminada en python) que propuso Veedrac, que tiene espacio O(f+k) y ( n/(n-(f+k)) es el número esperado de "conjeturas ” ) Tiempo:

Acabo de trazar esto para k=10 y un n=10000 razonablemente grande n=10000 (solo se vuelve más extremo para una n más grande). Y tengo que decir que solo lo implementé porque me pareció un desafío divertido, pero incluso me sorprende lo extremo que es esto:

Vamos a acercarnos para ver qué está pasando:

Sí, las conjeturas son aún más rápidas para el número 9998 que genera. Tenga en cuenta que, como puede ver en la primera gráfica, incluso mi línea de línea es probablemente más rápida para una f/n más grande (pero todavía tiene requisitos de espacio bastante horribles para la gran n ).

Para llevar el punto a casa: Lo único en lo que está pasando tiempo aquí es generar el conjunto, ya que ese es el factor f en el método de Veedrac.

Así que espero que mi tiempo aquí no haya sido desperdiciado y logré convencerte de que el método de Veedrac es simplemente el camino a seguir. Puedo entender por qué te molesta esa parte probabilística, pero tal vez piense en el hecho de que los hashmaps (= dictados de Python) y toneladas de otros algoritmos funcionan con métodos similares y parecen estar funcionando bien.

Es posible que tenga miedo de la variación en el número de repeticiones. Como se señaló anteriormente, esto sigue una distribución geométrica con p=nf/n . Por lo tanto, la desviación estándar (= la cantidad que "debe esperar" de que el resultado se desvíe del promedio esperado) es

Que es básicamente la misma que la media ( √f⋅n < √n² = n ).

****editar**:
Acabo de darme cuenta de que s es en realidad también n/(n-(f+k)) . Entonces, un tiempo de ejecución más exacto para mi algoritmo es O(k⋅log²(n/(n-(f+k))) + f⋅log(f)) . Lo cual es bueno ya que dados los gráficos anteriores, prueba mi intuición de que eso es bastante más rápido que O(k⋅log(f+k) + f⋅log(f)) . Pero tenga la seguridad de que eso tampoco cambia nada acerca de los resultados anteriores, ya que f⋅log(f) es la parte absolutamente dominante en el tiempo de ejecución.

Answer 6

Puede implementar un generador de barajado, basado en el "Método moderno de Fisher - Yates shuffle # de Wikipedia"

def shuffle_gen(src):
    """ yields random items from base without repetition. Clobbers `src`. """
    for remaining in xrange(len(src), 0, -1):
        i = random.randrange(remaining)
        yield src[i]
        src[i] = src[remaining - 1]

Que luego puede ser cortado usando itertools.islice :

>>> import itertools
>>> sampler = shuffle_gen(range(100))
>>> sample1 = list(itertools.islice(sampler, 10))
>>> sample1
[37, 1, 51, 82, 83, 12, 31, 56, 15, 92]
>>> sample2 = list(itertools.islice(sampler, 80))
>>> sample2
[79, 66, 65, 23, 63, 14, 30, 38, 41, 3, 47, 42, 22, 11, 91, 16, 58, 20, 96, 32, 76, 55, 59, 53, 94, 88, 21, 9, 90, 75, 74, 29, 48, 28, 0, 89, 46, 70, 60, 73, 71, 72, 93, 24, 34, 26, 99, 97, 39, 17, 86, 52, 44, 40, 49, 77, 8, 61, 18, 87, 13, 78, 62, 25, 36, 7, 84, 2, 6, 81, 10, 80, 45, 57, 5, 64, 33, 95, 43, 68]
>>> sample3 = list(itertools.islice(sampler, 20))
>>> sample3
[85, 19, 54, 27, 35, 4, 98, 50, 67, 69]

Answer 7

Si sabe de antemano que va a querer múltiples muestras sin superposiciones, lo más fácil es hacer random.shuffle() en la list(range(100)) (Python 3: puede omitir la list() en Python 2). luego pelar las rebanadas según sea necesario.

s = list(range(100))
random.shuffle(s)
first_sample = s[-10:]
del s[-10:]
second_sample = s[-10:]
del s[-10:]
# etc

La respuesta de Else @ Chronial es razonablemente eficiente.

Answer 8

Editar: ver versiones más limpias a continuación por @TimPeters y @Chronial. Una edición menor empujó esto a la parte superior.

Esto es lo que creo que es la solución más eficiente para el muestreo incremental. En lugar de una lista de números muestreados previamente, el estado que mantendrá la persona que llama comprende un diccionario que está listo para ser utilizado por el muestreador incremental y un conteo de números que quedan en el rango.

La siguiente es una implementación demostrativa. Comparado con otras soluciones:

• sin bucles (sin pirateo de Python / Veedrac estándar; crédito compartido entre Python impl y Veedrac)
• la complejidad del tiempo es O(log(number_previously_sampled))
• la complejidad del espacio es O(number_previously_sampled)

Código:

import random

def remove (i, n, state):
  if i == n - 1:
    if i in state:
      t = state[i]
      del state[i]
      return t
    else:
      return i
  else:
    if i in state:
      t = state[i]
      if n - 1 in state:
        state[i] = state[n - 1]
        del state[n - 1]
      else:
        state[i] = n - 1
      return t
    else:
      if n - 1 in state:
        state[i] = state[n - 1]
        del state[n - 1]
      else:
        state[i] = n - 1
      return i

s = dict()
for n in range(100, 0, -1):
  print remove(random.randrange(n), n, s)

Answer 9

Nota para los lectores de OP: considere mirar la respuesta aceptada originalmente para comprender la lógica y luego entender esta respuesta.

Aaaaa y por razones de integridad: este es el concepto de la respuesta del nigromante , pero se adaptó para que tome una lista de números prohibidos como entrada. Este es el mismo código que en mi respuesta anterior , pero construimos un estado a partir de forbid , antes de generar números.

• Este es el tiempo O(f+k) y la memoria O(f+k) . Obviamente, esto es lo más rápido posible sin requisitos para el formato de forbid (ordenado / establecido). Creo que esto hace que esto sea un ganador de alguna manera ^^.
• Si forbid es un conjunto, el método de adivinación repetida es más rápido con O(k⋅n/(n-(f+k))) , que está muy cerca de O(k) para f+k no muy cerca de n .
• Si se forbid , mi algoritmo ridículo es más rápido con:
  

import random
def sample_gen(n, forbid):
    state = dict()
    track = dict()
    for (i, o) in enumerate(forbid):
        x = track.get(o, o)
        t = state.get(n-i-1, n-i-1)
        state[x] = t
        track[t] = x
        state.pop(n-i-1, None)
        track.pop(o, None)
    del track
    for remaining in xrange(n-len(forbid), 0, -1):
        i = random.randrange(remaining)
        yield state.get(i, i)
        state[i] = state.get(remaining - 1, remaining - 1)
        state.pop(remaining - 1, None)

uso:

gen = sample_gen(10, [1, 2, 4, 8])
print gen.next()
print gen.next()
print gen.next()
print gen.next()

Answer 10

Esta es una versión reescrita de la genial solución de @ necromancer. Lo envuelve en una clase para que sea mucho más fácil de usar correctamente y utiliza más métodos de dictado para cortar las líneas de código.

from random import randrange

class Sampler:
    def __init__(self, n):
        self.n = n # number remaining from original range(n)
        # i is a key iff i < n and i already returned;
        # in that case, state[i] is a value to return
        # instead of i.
        self.state = dict()

    def get(self):
        n = self.n
        if n <= 0:
            raise ValueError("range exhausted")
        result = i = randrange(n)
        state = self.state
        # Most of the fiddling here is just to get
        # rid of state[n-1] (if it exists).  It''s a
        # space optimization.
        if i == n - 1:
            if i in state:
                result = state.pop(i)
        elif i in state:
            result = state[i]
            if n - 1 in state:
                state[i] = state.pop(n - 1)
            else:
                state[i] = n - 1
        elif n - 1 in state:
            state[i] = state.pop(n - 1)
        else:
            state[i] = n - 1
        self.n = n-1
        return result

Aquí hay un controlador básico:

s = Sampler(100)
allx = [s.get() for _ in range(100)]
assert sorted(allx) == list(range(100))

from collections import Counter
c = Counter()
for i in range(6000):
    s = Sampler(3)
    one = tuple(s.get() for _ in range(3))
    c[one] += 1
for k, v in sorted(c.items()):
    print(k, v)

y salida de muestra:

(0, 1, 2) 1001
(0, 2, 1) 991
(1, 0, 2) 995
(1, 2, 0) 1044
(2, 0, 1) 950
(2, 1, 0) 1019

Por globo ocular, esa distribución está bien (ejecuta una prueba de ji cuadrado si eres escéptico). Algunas de las soluciones aquí no dan a cada permutación con igual probabilidad (a pesar de que devuelven cada k-subconjunto de n con igual probabilidad), por lo que son diferentes random.sample()a este respecto.

Answer 11

Razonablemente rápido de una línea ( O(n + m), n = rango, m = antiguo tamaño de muestra):

next_sample = random.sample(set(range(100)).difference(my_sample), 10)