Что такое Pythonic способ найти самый длинный общий префикс списка списков?

Данный: список списков, например [[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]]

Todo: найдите самый длинный общий префикс всех подсписок.

Существует: в другом потоке Общие элементы между двумя списками, не использующими наборы в Python ", предлагается использовать" Counter ", который доступен выше python 2.7. Однако наш текущий проект был написан на python 2.6, поэтому" Counter" не используется.

В настоящее время я кодирую его так:

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]

Но я считаю, что это не очень питонов, есть ли лучший способ кодирования?

Спасибо!

Новое редактирование. Извините, что в моем случае общие элементы списков в 'l' имеют одинаковый порядок и всегда начинаются с 0-го элемента. Таким образом, у вас не будет таких случаев, как [[1,2,5,6],[2,1,7]]

Ответы

Ответ 1

Я не уверен, как это pythonic

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

Ответ 2

os.path.commonprefix() хорошо работает для списков:)

>>> 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]

Ответ 3

Учитывая ваш пример кода, вам, похоже, нужна версия reduce(set.intersection, map(set, l)), которая сохраняет начальный порядок первого списка.

Это требует алгоритмических улучшений, а не стилистических улучшений; "Питонический" код сам по себе не принесет вам пользы. Подумайте о ситуации, которая должна выполняться для всех значений, которые встречаются в каждом списке:

Учитывая список списков, значение появляется в каждом списке тогда и только тогда, когда оно встречается в списках nlist, где nlist - общее количество списков.

Если мы можем гарантировать, что каждое значение происходит только один раз в каждом списке, то указанное выше можно перефразировать:

Учитывая список списков уникальных элементов, значение происходит в каждом списке тогда и только тогда, когда оно встречается nlist times total.

Мы можем использовать наборы, чтобы гарантировать, что элементы в наших списках уникальны, поэтому мы можем объединить этот последний принцип с простой стратегией счета:

>>> 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
...

Теперь нам нужно всего лишь фильтровать исходный список:

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

Ответ 4

Здесь альтернативный способ использования 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]

Не уверен, как это можно было бы назвать "пифоническим".

Ответ 5

Он неэффективен, так как он не срабатывает, как только обнаружено несоответствие, но его порядок:

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