¿Cuál es la manera Pythonic de encontrar el prefijo común más largo de una lista de listas?

Question

Dado: una lista de listas, como [[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]]

Todo: Encontrar el prefijo común más larga de todas las sublistas.

Existe: en otro hilo "Common elements between two lists not using sets in Python", se sugiere utilizar "Contador", que está disponible arriba de python 2.7. Sin embargo, nuestro proyecto actual se escribió en python 2.6, por lo que "Counter" no se usa.

que actualmente código de esta manera:

l = [[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]] 
newl = l[0] 
if len(l)>1: 
    for li in l[1:]: 
    newl = [x for x in newl if x in li] 

Pero no resulta muy Pythonic, hay una mejor forma de codificar?

Gracias!

Nueva edición: Perdón por mencionar: en mi caso, los elementos compartidos de las listas en 'l' tienen el mismo orden y siempre comienzan desde el 0 ° elemento. Por lo tanto, no tendrá casos como [[1,2,5,6],[2,1,7]]

Answer 1

No estoy seguro de cómo Pythonic es

from itertools import takewhile,izip 

x = [[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]] 

def allsame(x): 
    return len(set(x)) == 1 

r = [i[0] for i in takewhile(allsame ,izip(*x))] 

Answer 2

Dado su código de ejemplo, parece que desea una versión de reduce(set.intersection, map(set, l)) que preserve el orden inicial de la primera lista.

Esto requiere algoritmo mejoras, no mejoras estilísticas; El código "pythonic" solo no te hará ningún bien aquí. Piense acerca de la situación que debe retención para todos los valores que se dan en todas las listas:

Given a list of lists, a value occurs in every list if and only if it occurs in nlist lists, where nlist is the total number of lists.

si podemos garantizar que cada valor se produce sólo una vez en cada lista, a continuación, lo anterior puede reformularse:

Given a list of lists of unique items, a value occurs in every list if and only if it occurs nlist times total.

podemos utilizar conjuntos para garantizar que los artículos en nuestras listas son únicos, por lo que podemos combinar este último principio con una simple estrategia de conteo:

>>> l = [[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]] 
>>> count = {} 
>>> for i in itertools.chain.from_iterable(map(set, l)): 
...  count[i] = count.get(i, 0) + 1 
...  

Ahora todo lo que tenemos que hacer es filtrar la lista original:

>>> [i for i in l[0] if count[i] == len(l)] 
[3, 2, 1] 

Answer 3

Aquí es una forma alternativa utilizando itertools:

>>> import itertools 
>>> L = [[3,2,1,4], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]] 
>>> common_prefix = [] 
>>> for i in itertools.izip(*L): 
... if i.count(i[0]) == len(i): 
...  common_prefix.append(i[0]) 
... else: 
...  break 
... 
>>> common_prefix 
[3, 2, 1] 

No sabe cómo "Pythonic" podría considerarse sin embargo.

Answer 4

os.path.commonprefix() funciona bien para las listas :)

>>> x = [[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]] 
>>> import os 
>>> os.path.commonprefix(x) 
[3, 2, 1] 

Answer 5

es ineficiente, ya que no temprana de salida tan pronto como un desajuste es encontrado, pero está ordenado:

([i for i,(j,k) in enumerate(zip(a,b)) if j!=k] or [0])[0]