¿Cómo intercalar elegantemente dos listas de longitud desigual en python?

Quiero fusionar dos listas en python, con las listas de diferentes longitudes, de modo que los elementos de la lista más corta estén lo más espaciados dentro de la lista final como sea posible. es decir, quiero tomar [1, 2, 3, 4] y ['a','b'] y fusionarlos para obtener una lista similar a [1, 'a', 2, 3, 'b', 4] . Debe ser capaz de funcionar con listas que no sean múltiplos exactos también, por lo que podría tomar [1, 2, 3, 4, 5] y ['a', 'b', 'c'] y producir [1, 'a', 2, 'b', 3, 'c', 4, 5] o similar. Necesita preservar el orden de ambas listas.

Puedo ver cómo hacer esto mediante un método de fuerza bruta de largo aliento, pero como Python parece tener una amplia gama de excelentes herramientas para hacer todo tipo de cosas inteligentes que no conozco (todavía) me pregunté si habría algo más. elegante puedo usar?

NB: Estoy usando Python 3.3.

si a es la lista más larga y b es la más corta

 from itertools import groupby len_ab = len(a) + len(b) groups = groupby(((a[len(a)*i//len_ab], b[len(b)*i//len_ab]) for i in range(len_ab)), key=lambda x:x[0]) [j[i] for k,g in groups for i,j in enumerate(g)] 

p.ej

 >>> a = range(8) >>> b = list("abc") >>> len_ab = len(a) + len(b) >>> groups = groupby(((a[len(a)*i//len_ab], b[len(b)*i//len_ab]) for i in range(len_ab)), key=lambda x:x[0]) >>> [j[i] for k,g in groups for i,j in enumerate(g)] [0, 'a', 1, 2, 'b', 3, 4, 5, 'c', 6, 7] 

Puedes usar este truco para asegurarte de que a sea ​​más largo que b

 b, a = sorted((a, b), key=len) 

Este es básicamente el mismo que el algoritmo de línea de Bresenham . Puede calcular las posiciones de “píxeles” y utilizarlas como índices en las listas.

En lo que difiere su tarea es que solo desea que cada elemento se muestre una vez. Necesitará modificar el algoritmo o postprocesar los índices, agregando los elementos de las listas solo la primera vez que aparezcan. Sin embargo, hay una ligera ambigüedad: cuando los índices de píxel / lista cambian al mismo tiempo, tendrá que elegir cuál incluir primero. Esto corresponde a las dos opciones diferentes para intercalar las listas que se mencionan en la pregunta y un comentario.

Tomando mucho dinero de la solución de Jon Clements, podría escribir una función que tome un número arbitrario de secuencias y devuelva una secuencia combinada de elementos espaciados uniformemente:

 import itertools as IT def evenly_spaced(*iterables): """ >>> evenly_spaced(range(10), list('abc')) [0, 1, 'a', 2, 3, 4, 'b', 5, 6, 7, 'c', 8, 9] """ return [item[1] for item in sorted(IT.chain.from_iterable( zip(IT.count(start=1.0 / (len(seq) + 1), step=1.0 / (len(seq) + 1)), seq) for seq in iterables))] iterables = [ ['X']*2, range(1, 11), ['a']*3 ] print(evenly_spaced(*iterables)) 

rendimientos

 [1, 2, 'a', 3, 'X', 4, 5, 'a', 6, 7, 'X', 8, 'a', 9, 10] 

Con el supuesto de que a es la secuencia a insertar en:

 from itertools import izip, count from operator import itemgetter import heapq a = [1, 2, 3, 4] b = ['a', 'b'] fst = enumerate(a) snd = izip(count(0, len(a) // len(b)), b) print map(itemgetter(1), heapq.merge(fst, snd)) # [1, 'a', 2, 3, 'b', 4] 

Si modificamos la respuesta de @ Jon como esta.

 from itertools import count import heapq [x[1] for x in heapq.merge(izip(count(0, len(b)), a), izip(count(0, len(a)), b))] 

No importa cuál de a / b es el más largo.

Si queremos hacer esto sin itertools:

 def interleave(l1, l2, default=None): max_l = max(len(l1), len(l2)) data = map(lambda x: x + [default] * (max_l - len(x)), [l1,l2]) return [data[i%2][i/2] for i in xrange(2*max_l)] 

Ahh, se perdió la parte igualmente espaciada. Esto se marcó por alguna razón como duplicado con una pregunta que no requería un espacio igual en presencia de diferentes longitudes de listas.

Una variante de @Jon Clements responde utilizando more_itertools.collate con una explicación.

Dado

 import itertools as it import more_itertools as mit a, b = range(1, 5), ["a", "b"] 

Código

 first = enumerate(a) second = zip(it.count(0, len(a) // len(b)), b) [x for i, x in mit.collate(first, second, key=lambda x: x[0])] # [1, 'a', 2, 3, 'b', 4] 

Detalles

Esta respuesta se actualiza para usar con Python 3.

first y la second son iterables de tuplas, cada una de las cuales comprende un par de posición-elemento.

 list(first) # [(0, 1), (1, 2), (2, 3), (3, 4)] list(second) # [(0, 'a'), (2, 'b')] 

more_itertools.collate() envuelve heapq.merge() , que combina en orden los first y second iterables ordenados. En la lista de comprensión final, la key es la función de clasificación, mientras que se devuelve el último elemento de cada tupla.

Instale este paquete de terceros a través de > pip install more_itertools o use heapq.merge() directamente.