Obtener muestra aleatoria de la lista mientras se mantiene el orden de los artículos?

Simple-a-código O(N + K*log(K)) manera

Tome una muestra aleatoria sin reemplazar los índices, clasifique los índices y tómelos del original.

indices = random.sample(range(len(myList)), K)
[myList[i] for i in sorted(indices)]

O más concisamente:

[x[1] for x in sorted(random.sample(enumerate(myList),K))]

Optimizado O(N)-tiempo, O (1)-auxiliar-espacio camino

Alternativamente puede usar un truco matemático e iterativamente ir a través de myList de izquierda a derecha, eligiendo números con probabilidad dinámicamente cambiante (N-numbersPicked)/(total-numbersVisited). La ventaja de este enfoque es que es un O(N) algoritmo ya que no implica la clasificación!

from __future__ import division

def orderedSampleWithoutReplacement(seq, k):
    if not 0<=k<=len(seq):
        raise ValueError('Required that 0 <= sample_size <= population_size')

    numbersPicked = 0
    for i,number in enumerate(seq):
        prob = (k-numbersPicked)/(len(seq)-i)
        if random.random() < prob:
            yield number
            numbersPicked += 1

Prueba de concepto y prueba de que las probabilidades son correctas :

Simulado con 1 billón de muestras pseudoaleatorias en el transcurso de 5 horas:

>>> Counter(
        tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
        for _ in range(10**9)
    )
Counter({
    (0, 3): 166680161, 
    (1, 2): 166672608, 
    (0, 2): 166669915, 
    (2, 3): 166667390, 
    (1, 3): 166660630, 
    (0, 1): 166649296
})

Las probabilidades divergen de las probabilidades verdaderas por menos un factor de 1.0001. Ejecutar esta prueba de nuevo resultó en un orden diferente, lo que significa que no está sesgado hacia un pedido. La ejecución de la prueba con menos muestras para [0,1,2,3,4], k=3 y [0,1,2,3,4,5], k=4 tuvo resultados similares resultado.

editar: No estoy seguro de por qué las personas votan comentarios equivocados o temen votar... No, no hay nada malo con este método. =)

(También una nota útil del usuario tegan en los comentarios: Si esto es python2, querrá usar xrange, como de costumbre, si realmente le importa el espacio adicional.)

editar : Prueba: Considerando la distribución uniforme (sin reemplazo) de elegir un subconjunto de k de una población seq de tamaño len(seq), nosotros puede considerar una partición en un punto arbitrario i en 'left' (0,1,..., i-1) y 'derecho' (i, i + 1,..., len (seq)). Dado que elegimos numbersPicked del subconjunto conocido de la izquierda, el resto debe provenir de la misma distribución uniforme en el subconjunto desconocido de la derecha, aunque los parámetros ahora son diferentes. En particular, la probabilidad de que seq[i] contenga un elemento elegido es #remainingToChoose/#remainingToChooseFrom, o (k-numbersPicked)/(len(seq)-i), por lo que simulamos eso y recurrimos al resultado. (Esto debe terminar ya que si # remainingToChoose == # Remainingtochoosef From, entonces todas las probabilidades restantes son 1.) Esto es similar a un árbol de probabilidad que se genera dinámicamente. Básicamente puede simular una distribución de probabilidad uniforme condicionando las elecciones anteriores (a medida que crece el árbol de probabilidad, elige la probabilidad de la rama actual de tal manera que sea aposteriori igual que las hojas anteriores, es decir, condicionada a las elecciones anteriores; esto funcionará porque esta probabilidad es uniformemente exactamente N / k).

edit : Timothy Shields menciona Reservoir Sampling , que es la generalización de este método cuando len(seq) es desconocido (como con una expresión generadora). Específicamente el que se señala como "algoritmo R" es el espacio O(N) y O(1) si se hace en el lugar; implica tomar el primer elemento N y reemplazarlos lentamente (también se da una pista de una prueba inductiva). También se pueden encontrar variantes distribuidas útiles y variantes diversas de muestreo de reservorios en la página de wikipedia.

edit : Aquí hay otra forma de codificarlo a continuación de una manera más semánticamente obvia.

from __future__ import division
import random

def orderedSampleWithoutReplacement(seq, sampleSize):
    totalElems = len(seq)
    if not 0<=sampleSize<=totalElems:
        raise ValueError('Required that 0 <= sample_size <= population_size')

    picksRemaining = sampleSize
    for elemsSeen,element in enumerate(seq):
        elemsRemaining = totalElems - elemsSeen
        prob = picksRemaining/elemsRemaining
        if random.random() < prob:
            yield element
            picksRemaining -= 1

from collections import Counter         
Counter(
    tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
    for _ in range(10**5)

)

Tal vez solo pueda generar la muestra de índices y luego recopilar los elementos de su lista.

randIndex = random.sample(range(len(mylist)), sample_size)
randIndex.sort()
rand = [mylist[i] for i in randIndex]

Aparentemente random.sample se introdujo en python 2.3

Así que para la versión debajo de eso, podemos usar shuffle (ejemplo para 4 elementos):

myRange =  range(0,len(mylist)) 
shuffle(myRange)
coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]

Aleatorio.ejemplo de implementarlo.

>>> random.sample([1, 2, 3, 4, 5],  3)   # Three samples without replacement
[4, 1, 5]