Tengo una lista ordenada, vamos a decir: (no es realmente sólo números, es una lista de objetos que se ordenan con un momento complicado consumir algoritmo)

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

Hay una función de python que me dará N de los elementos, pero mantener el orden?

Ejemplo:

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

etc…

  • ¿Por qué no quieres random.sample y, a continuación, ordenar?
  • Está ordenado con un no trivial algoritmo… realmente no es justo números
  • Un muy pequeño cambio a Daniel comentario: muestra una gama de [0,count), de ordenación de la muestra (los números en el rango natural de pedido), a continuación, extraer los valores de mylist a partir de los índices. El uso de zip podría lograr el mismo efecto con un poco diferentes de la mecánica.
  • ok, puedo obtener una respuesta + ejemplo, así que tengo algo para aceptar ? 🙂

5 Comentarios

  1. 118

    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, el mejor uso xrange en lugar de range)

    Explicación

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

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

    Estos índices, a continuación, obtener ordenados para preservar el ordenamiento de los elementos en la lista original.

    Finalmente, la lista de la comprensión de la tira de los elementos de la lista original, dado que las muestras de los índices.

  2. 89

    Simple código de O(N + K*log(K)) forma

    Tomar una muestra aleatoria sin reemplazo de los índices, de ordenación de los índices, y llevarlos a partir de la 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) en tiempo O(1)-auxiliar de espacio de manera

    También puedes utilizar un truco matemático y de forma iterativa, ir a través de myList de izquierda a derecha, de escoger los números con dinámicamente cambiante probabilidad (N-numbersPicked)/(total-numbersVisited). La ventaja de este enfoque es que es un O(N) algoritmo puesto 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 correctos:

    Simulado con 1 billón de pseudoaleatoria muestras en el curso 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
    })

    Probabilidades difieren de las verdaderas probabilidades de al menos un factor de 1.0001. La ejecución de esta prueba de nuevo resultó en un orden diferente, lo que significa que no está sesgada hacia uno de pedidos. 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 tuvieron resultados similares.

    edit: No sé por qué la gente vota mal comentario o miedo a upvote… NO, no hay nada de malo con este método. =)

    (También una nota útil de usuario tegan en los comentarios: Si este es python2, usted querrá usar xrange, como de costumbre, si realmente se preocupan por espacio extra.)

    editar: Prueba: teniendo en cuenta la distribución uniforme (sin reemplazo) de escoger un subconjunto de k de una población seq de tamaño len(seq), podemos considerar una partición en un punto arbitrario i en ‘izquierda’ (0,1,…,i-1) y ‘derecha’ (i,i+1,…,len(seq)). Dado que hemos recogido numbersPicked de la izquierda conocido subconjunto, el resto debe provenir de la misma distribución uniforme en el derecho desconocido subconjunto, a pesar de que los parámetros son ahora diferentes. En particular, la probabilidad de que seq[i] contiene un elemento seleccionado es #remainingToChoose/#remainingToChooseFrom, o (k-numbersPicked)/(len(seq)-i), por lo que podemos simular que y recurse en el resultado. (Esto debe terminar ya que si #remainingToChoose == #remainingToChooseFrom, luego todo el resto de las probabilidades son 1.) Esto es similar a un árbol de probabilidad que pasa a ser generados dinámicamente. Básicamente, usted puede simular una uniforme distribución de probabilidad mediante el acondicionamiento previo de opciones (a medida que crece la probabilidad de árbol, tienes que elegir la probabilidad de que la rama actual de tal manera que es aposteriori el mismo que antes de las hojas, es decir, condicionado a que antes de la elección; esto va a funcionar porque esta probabilidad es uniforme exactamente N/k).

    editar: Timoteo Escudos menciona El Embalse De Muestreo, que es la generalización de este método cuando len(seq) es desconocido (tal como un generador de expresión). Específicamente el que señaló como «algoritmo R» es O(N) y O(1) espacio si se hace en el mismo lugar; se trata de tomar el primer N elemento y reemplazando poco a poco a ellos (una alusión a una inductivo prueba también se da). Allí también son útiles distribuidos variantes, y de las diversas variantes del embalse de muestreo que se encuentran en la página de la wikipedia.

    editar: he Aquí otra manera el código de abajo en un semánticamente más obvio manera.

    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)

    )

    • ninguna desventaja, sólo un speedup de O(N) lugar O(N log(N))
    • Su última afirmación es incorrecta debido a que la probabilidad va a 1, naturalmente, si las muestras no son recogidos. Por favor, sea tan amable de copia de seguridad de su primera reclamación con las matemáticas, yo estaría muy interesado si usted puede probar que estoy equivocado, a pesar de mi extensa simulaciones.
    • Muy bonito, me preguntaba cómo hacer este enfoque lineal, demasiado. ¿Esta fórmula tiene una página de wikipedia? 🙂
    • gracias! Me preguntaba yo, pero no lo pude encontrar, no estoy seguro donde agregar que incluso, tal vez en en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29 … Que podría ser en la probabilidad de libros de texto, aunque; es la generalización de la [1/N,1/N-1,1/N-2,...,1] método de muestreo uniforme de las distribuciones discretas para varios valores (sin reemplazo).
    • Me sorprende esta respuesta no tiene más upvotes, que en realidad se explica cómo funciona la solución (y ofrece otra solución!), como contraposición a la primera respuesta, que es sólo una línea fragmento– darme ni idea de por qué o cómo funcionaba.
    • Solución agradable ninjagecko. Hay un buen inductivo prueba para su solución, si alguien está interesado en escribirla.
    • Solución agradable ! No te olvides de añadir from __future__ import division para ejecutar Python 2.
    • Usted debe nombrar el algoritmo en su respuesta: Embalse de Muestreo
    • En esta situación, es probable que desee utilizar xrange() no range(), especialmente si su lista es larga – range() pone todos los elementos en la memoria, mientras que xrange() evalúa perezosamente (para que no pierdas el tiempo y la memoria la creación de una lista que no necesitas). Consulte here para más detalles
    • tegan: Ah sí, lo siento, estoy acostumbrado a la codificación en python3. No es la etiqueta de la OP publicado acerca de (simplemente python2), pero para lo que vale, range() es un perezoso objeto en python3. Editado.
    • Para aquellos que ejecuta Python 2.x: prob = (k-numbersPicked)/float(len(seq)-i)
    • He probado este algoritmo y defenitly no puede funcionar bien para cualquier secuencia. Aquí es un simple contador-ejemplo: ideone.com/FNYfj8
    • trató de este algoritmo y defenitly no puede funcionar bien para cualquier secuencia. Este es un contra-ejemplo.») Un algoritmo funciona si tiene un válido prueba matemática como este; la prueba anterior caso, también es muy buena evidencia de que funciona. No sé C#, pero me doy cuenta de que su i variable no está incluso se incrementa. Pueden existir otros errores en su transcripción.
    • Volví a leer tu respuesta y aquí se fija la aplicación. Estoy de acuerdo en que parece que se garantiza a devolver exactamente N registros. Lo siento por la lectura inattentively la primera vez.

  3. 7

    Tal vez sólo se puede generar la muestra de los índices y, a continuación, recoger los elementos de la lista.

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

    Aparentemente random.sample se introdujo en python 2.3

    así que para la versión en virtud de que, podemos utilizar la reproducción aleatoria (ejemplo de 4 elementos):

    myRange =  range(0,len(mylist)) 
    shuffle(myRange)
    coupons = [ bestCoupons[i] for i in sorted(myRange[:4]) ]
    • Estás usando Python 2.2?! Usted debe actualizar… que el camino fuera de fecha.
    • bueno, ¿qué tenemos en los servidores.. hacer un sistema-ancho de la actualización es demasiada Burocracia
  5. -1

    al azar.ejemplo de implementarlo.

    >>> random.sample([1, 2, 3, 4, 5],  3)   # Three samples without replacement
    [4, 1, 5]
    • Que no está ordenado.

Dejar respuesta

Please enter your comment!
Please enter your name here