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

15

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

Да, ваша редакция подходит лучше, спасибо lukmac
Пожалуйста, смотрите мой новый редактировать в оригинальном сообщении. lukmac
что ожидается выход [[1,2,3], [1,4,2,3]] Luka Rahne
Counter в любом случае не сохраняет порядок. Каковы общие элементы между[3, 2, 1] а также[4, 3, 2, 1]? [] или же[3, 2, 1]? Я спрашиваю - имеет ли значение положение и порядок? Если положение не имеет значения, то этоLongest common substring problem ответ на который вы можете найти в другом месте на этом сайте agf
Каков ожидаемый результат для[[1, 2, 3], [3, 2, 1]]? Sven Marnach

Ваш Ответ

6   ответов
44

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]
Довольно аккуратно и не требует никаких дополнительных библиотек!
0

Модернизированный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.

0

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

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

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

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

2

Учитывая ваш пример кода, вы, кажется, хотите версию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]
Кажется, мой хрустальный шар работал нормально & # x2013; ОП подтвердили, что ищут самый длинный общий префикс.
@SvenMarnach, я думаю, что "общие элементы списков в" l ". иметь одинаковый порядок и всегда начинать с 0-го пункта & quot; не запрещает ввод, как[[1, 2, 3], [1, 44, 2, 3]], Так что я неthink это самая распространенная проблема с префиксами. Но время покажет.
Ну, похоже, ворота снова переместились. +1 за хороший ответ на то, что казалось вопросом. :)
18

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

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

Похожие вопросы