¿Obtener una muestra aleatoria de la lista manteniendo el orden de los artículos?

Tengo una lista ordenada, digamos: (no es realmente solo números, es una lista de objetos que se ordenan con un algoritmo complicado que consume mucho tiempo)

mylist = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9  , 10 ]

¿Hay alguna función de Python que me dé N de los elementos, pero mantendrá el orden?

Ejemplo:

randomList = getRandom(mylist,4)
# randomList = [ 3 , 6 ,7 , 9 ]
randomList = getRandom(mylist,4)
# randomList = [ 1 , 2 , 4 , 8 ]

etc ...

El siguiente código generará una muestra aleatoria de tamaño 4:

import random

sample_size = 4
sorted_sample = [
    mylist[i] for i in sorted(random.sample(range(len(mylist)), sample_size))
]

(nota: con Python 2, mejor uso en xrangelugar de range)

Explicación

random.sample(range(len(mylist)), sample_size)

genera una muestra aleatoria de los índices de la lista original.

Estos índices luego se ordenan para preservar el orden de los elementos en la lista original.

Finalmente, la comprensión de la lista extrae los elementos reales de la lista original, dados los índices muestreados.

Modo simple de codificar O (N + K * log (K))

Tome una muestra aleatoria sin reemplazar los índices, ordene los índices y sáquelos 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) -time, O (1) -auxiliary-space way

Alternativamente, puede usar un truco matemático y pasar iterativamente myListde izquierda a derecha, seleccionando números con probabilidad que cambia dinámicamente (N-numbersPicked)/(total-numbersVisited). La ventaja de este enfoque es que es un O(N)algoritmo, ya que no implica ordenar.

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 difieren de las probabilidades verdaderas en menos de un factor de 1.0001. La ejecución de esta prueba nuevamente resultó en un orden diferente, lo que significa que no está sesgado hacia un pedido. Ejecutar la prueba con menos muestras [0,1,2,3,4], k=3y [0,1,2,3,4,5], k=4tuvo resultados similares.

editar: No estoy seguro de por qué la gente vota comentarios incorrectos o tiene miedo de votar ... NO, no hay nada de malo en 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 extra).

editar : Prueba: Considerando la distribución uniforme (sin reemplazo) de elegir un subconjunto de kuna población seqde tamaño len(seq), podemos considerar una partición en un punto arbitrario ien 'izquierda' (0,1, ..., i-1) y 'derecha' (i, i + 1, ..., len (seq)). Dado que elegimos numbersPickeddel 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), así que simulamos eso y recurrimos al resultado. (Esto debe terminar ya que si #remainingToChoose == #remainingToChooseFrom, 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 aumenta el árbol de probabilidad, elige la probabilidad de la rama actual de modo 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).

editar : Timothy Shields menciona Reservoir Sampling , que es la generalización de este método cuando len(seq)se desconoce (como con una expresión generadora). Específicamente, el que se indica como "algoritmo R" es el espacio O (N) y O (1) si se realiza en el lugar; implica tomar el primer elemento N y reemplazarlo lentamente (también se da una pista sobre una prueba inductiva). También hay variantes distribuidas útiles y variantes diversas de muestreo de yacimientos que se encuentran en la página de wikipedia.

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

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 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.samplese 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]) ]

random.sample implementarlo.

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