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

Given: список списков, таких как[[3,2,1], [3,2,1,4,5], [3,2,1,8,9], [3,2,1,5,7,8,9]]

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

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

I currently code it like this:

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]

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

Спасибо!

New edit: Извините, что упомянул: в моем случае, общие элементы списков в 'l' apos; иметь тот же порядок и всегда начинать с 0-го пункта. Так что у вас не будет таких случаев, как[[1,2,5,6],[2,1,7]]

 lukmac29 июн. 2012 г., 16:22
Пожалуйста, смотрите мой новый редактировать в оригинальном сообщении.
 lukmac29 июн. 2012 г., 17:22
Да, ваша редакция подходит лучше, спасибо
 Luka Rahne29 июн. 2012 г., 16:09
что ожидается выход [[1,2,3], [1,4,2,3]]
 agf29 июн. 2012 г., 16:04
Counter в любом случае не сохраняет порядок. Каковы общие элементы между[3, 2, 1] а также[4, 3, 2, 1]? [] или же[3, 2, 1]? Я спрашиваю - имеет ли значение положение и порядок? Если положение не имеет значения, то этоLongest common substring problem ответ на который вы можете найти в другом месте на этом сайте
 Sven Marnach29 июн. 2012 г., 16:04
Каков ожидаемый результат для[[1, 2, 3], [3, 2, 1]]?

Ответы на вопрос(6)

МодернизированныйVertical scan решение с использованием выражения генератора и встроенной функции Python 3zip:

lst = [[3,2,1], [3,2,1,1,5], [3,2,1,8,9], [3,2,1,5,7,8,9]]

next(zip(*(x for x in zip(*lst) if len(set(x)) == 1)))
# (3, 2, 1)

Смотрите также связанныйLeetcode проблема -Longest Common Prefix.

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

Не уверен, как "питонический" это может быть рассмотрено, хотя

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]
 24 сент. 2018 г., 15:54
Довольно аккуратно и не требует никаких дополнительных библиотек!

Это неэффективно, так как это не рано, как только обнаружено несоответствие, но его аккуратность:

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

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

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

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.

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

Given a list of lists of unique items, a value occurs in every list if and only if it occurs 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]
 29 июн. 2012 г., 16:29
Ну, похоже, ворота снова переместились. +1 за хороший ответ на то, что казалось вопросом. :)
 29 июн. 2012 г., 16:40
@SvenMarnach, я думаю, что "общие элементы списков в" l ". иметь одинаковый порядок и всегда начинать с 0-го пункта & quot; не запрещает ввод, как[[1, 2, 3], [1, 44, 2, 3]], Так что я неthink это самая распространенная проблема с префиксами. Но время покажет.
 29 июн. 2012 г., 17:25
Кажется, мой хрустальный шар работал нормально & # x2013; ОП подтвердили, что ищут самый длинный общий префикс.
Решение Вопроса

Я не уверен, насколько это питоническое

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))]
 01 нояб. 2017 г., 20:22
Извините за беспокойство, но у меня похожая проблема. Мне нужно найти самый длинный общий префикс в (одном) списке, но префикс точно не будет включенevery элемент в списке. Не могли бы вы немного подсказать мне, как заставить это работать, или я должен опубликовать новый вопрос?
 01 нояб. 2017 г., 20:32
Что касается python3, я думаю, что вы можете использовать встроенную функцию zip, но я не знаю точно, совпадает ли ваш код с кодом, опубликованным в этом ответе, потому что я не получаю такую ошибку. По поводу вашего первого вопроса я не очень хорошо понимаю, и вы можете опубликовать новый вопрос на SO.
 01 нояб. 2017 г., 20:25
Кроме того, я хотел попробовать этот код, но я также использую Python 3.6.2. Я видел это сейчасizip не вitertools больше, потому что теперь есть главная функция под названиемzip это делает так. Я пытался заменить его, но теперь я получаюTypeError: unhashable type: 'list' on return len(set(x)) == 1, Знаете ли вы, как адаптировать его для работы в Python 3?
 29 июн. 2012 г., 17:03
Довольно питонический.

Ваш ответ на вопрос