Entrelazando múltiples iterables al azar, preservando su orden en python

Inspirado en esta pregunta anterior sobre el desbordamiento de stack , he estado considerando cómo intercalar aleatoriamente iterables en python mientras se preserva el orden de los elementos dentro de cada iterable. Por ejemplo:

>>> def interleave(*iterables): ... "Return the source iterables randomly interleaved" ...  >>> interleave(xrange(1, 5), xrange(5, 10), xrange(10, 15)) [1, 5, 10, 11, 2, 6, 3, 12, 4, 13, 7, 14, 8, 9] 

La pregunta original hecha para intercalar aleatoriamente dos listas, a y b, y la solución aceptada fue:

 >>> c = [x.pop(0) for x in random.sample([a]*len(a) + [b]*len(b), len(a)+len(b))] 

Sin embargo, esta solución funciona solo para dos listas (aunque se puede extender fácilmente) y se basa en el hecho de que a y b son listas para que se pueda usar pop() y len() , lo que significa que no se puede usar con iterables . También tiene el desafortunado efecto secundario de vaciar las listas de fonts a y b.

Las respuestas alternativas dadas para la pregunta original toman copias de las listas de fonts para evitar modificarlas, pero esto me parece ineficiente, especialmente si las listas de fonts son considerables. Las respuestas alternativas también utilizan len() y, por lo tanto, no se pueden usar en meros iterables.

Escribí mi propia solución que funciona para cualquier número de listas de entrada y no las modifico:

 def interleave(*args): iters = [i for i, b in ((iter(a), a) for a in args) for _ in xrange(len(b))] random.shuffle(iters) return map(next, iters) 

pero esta solución también se basa en que los argumentos de origen son listas para que len() pueda usarse en ellos.

Entonces, ¿existe una manera eficiente de intercalar aleatoriamente los resultados en python, conservando el orden original de los elementos, que no requiere conocer la longitud de los resultados con antelación y no toma copias de los resultados?

Edición: tenga en cuenta que, al igual que con la pregunta original, no necesito que la asignación al azar sea justa.

Aquí hay una forma de hacerlo usando un generador:

 import random def interleave(*args): iters = map(iter, args) while iters: it = random.choice(iters) try: yield next(it) except StopIteration: iters.remove(it) print list(interleave(xrange(1, 5), xrange(5, 10), xrange(10, 15))) 

No si quieres encajar para ser “justo”.

Imagina que tienes una lista que contiene un millón de artículos y otra que contiene solo dos artículos. Una aleatorización “justa” tendría el primer elemento de la lista corta que se produce en aproximadamente el índice 300000 o menos.

 a,a,a,a,a,a,a,...,a,a,a,b,a,a,a,.... ^ 

Pero no hay forma de saberlo por adelantado hasta que sepas la longitud de las listas.

Si solo tomas de cada lista con un 50% (1 / n) de probabilidad, entonces puedes hacerlo sin saber la longitud de las listas, pero obtendrás algo más como esto:

 a,a,b,a,b,a,a,a,a,a,a,a,a,a,a,a,... ^ ^ 

Estoy satisfecho de que la solución provista por aix cumple con los requisitos de la pregunta. Sin embargo, después de leer los comentarios de Mark Byers , quería ver cuán “injusta” era la solución.

Además, en algún momento después de que escribí esta pregunta, el usuario de desbordamiento de stack EOL publicó otra solución a la pregunta original que produce un resultado “justo”. La solución de EOL es:

 >>> a.reverse() >>> b.reverse() >>> [(a if random.randrange(0, len(a)+len(b)) < len(a) else b).pop() ... for _ in xrange(len(a)+len(b))] 

También mejoré aún más mi propia solución para que no se base en los argumentos que apoyan a len() pero sí hace copias de los iterables de origen:

 def interleave(*args): iters = sum(([iter(list_arg)]*len(list_arg) for list_arg in map(list, args)), []) random.shuffle(iters) return map(next, iters) 

o, escrito de manera diferente:

 def interleave(*args): iters = [i for i, j in ((iter(k), k) for k in map(list, args)) for _ in j] random.shuffle(iters) return map(next, iters) 

Luego probé la solución aceptada a la pregunta original, escrita por FJ y reproducida en mi pregunta anterior, a las soluciones de aix, EOL y mías. La prueba implicó intercalar una lista de 30000 elementos con una sola lista de elementos (el centinela). Repetí la prueba 1000 veces y la siguiente tabla muestra, para cada algoritmo, el índice mínimo, máximo y promedio del centinela después del intercalado, junto con el tiempo total tomado. Esperamos que un algoritmo "justo" produzca una media de aprox. 15,000:

 algo min max mean total_seconds ---- --- --- ---- ------------- FJ: 5 29952 14626.3 152.1 aix: 0 8 0.9 27.5 EOL: 45 29972 15091.0 61.2 srgerg: 23 29978 14961.6 18.6 

Como se puede ver en los resultados, cada uno de los algoritmos de FJ, EOL y srgerg producen resultados aparentemente "justos" (al menos en las condiciones de prueba dadas). Sin embargo, el algoritmo de aix siempre ha colocado al centinela dentro de los primeros 10 elementos del resultado. Repetí el experimento varias veces con resultados similares.

Así que Mark Byers tiene la razón. Si se desea un intercalado verdaderamente aleatorio, la longitud de la fuente de iterables deberá conocerse con anticipación, o se deberán hacer copias para que se pueda determinar la longitud.