Как в Python получить пересечение двух списков, сохранив порядок пересечения?

У меня есть список списков ("подсписков"), и я хочу посмотреть, встречается ли одна и та же последовательность любой неопределенной длины более чем в одном подсписке. Чтобы уточнить, порядок элементов должен быть сохранен - ​​я не хочу пересечения каждого подсписка как набора. Должно быть не менее 2 элементов, которые совпадают последовательно. Пожалуйста, см. пример ниже.

Вход:

someList = [[0,1,3,4,3,7,2],[2,3,4,3],[0,3,4,3,7,3]]

Желаемый результат: (будет распечатан в файл, но не беспокойтесь об этой детали)

sublist0_sublist1 = [3,4,3] #пересечение 1-го и 2-го подсписков

sublist0_sublist2 = [3,4,3,7] #пересечение 1-го и 3-го подсписков

sublist1_sublist2 = [3,4,3] #пересечение 2-го и 3-го подсписков


person leon    schedule 16.05.2013    source источник
comment
дубликат stackoverflow.com/questions/16120751/   -  person Colleen    schedule 16.05.2013
comment
Должны ли элементы результата последовательно появляться во входных списках?   -  person interjay    schedule 16.05.2013
comment
@interjay Да, если я правильно понял ваш вопрос. В приведенном мной примере и 1-й, и 3-й подсписки содержат «0», но в 1-м подсписке «0» не касается/не соединяется с «3» (он разделен «1»), поэтому « 0' не считается частью пересечения.   -  person leon    schedule 16.05.2013
comment
@Коллин Коллин Я не думаю, что это дубликат. Вопрос, с которым вы меня связали, выглядит очень сложным, и я не понял статью в Википедии о LIS. Мой вопрос намного проще, или, по крайней мере, он более прямой и более простыми словами. Прошу прощения, если я слишком нуб, чтобы понять, что это дублирующий вопрос.   -  person leon    schedule 16.05.2013
comment
Затем найдите алгоритм самой длинной общей подстроки, предполагая, что вам нужна самая длинная такая подстрока, когда их больше одной. Ссылка @Colleen не кажется актуальной.   -  person interjay    schedule 16.05.2013
comment
Ах, не удалось понять, что другой вопрос 1. более ограничителен, чем говорится в заголовке, и 2. не требует непрерывных подпоследовательностей. В этом случае посмотрите на stackoverflow.com/questions/14032903 / для помощи по алгоритмам, хотя она написана на C++, а не на python.   -  person Colleen    schedule 16.05.2013
comment
@interjay Это очень близко к тому, что я хочу, но проблема в том, что это решение работает со строками и ищет кучу совпадающих символов. Другими словами, чтобы он работал с моим вводом, мне пришлось бы сначала преобразовать его в строку: [[0,1,3,4,3,7,2],[2,3,4,3]] необходимо преобразовать в ['0134372','2343']. Это проблема, поскольку [0,1,3,4] и [0,13,4] станут ['0134'] и дадут ложные результаты. Пожалуйста, поправьте меня, если я ошибаюсь.   -  person leon    schedule 16.05.2013
comment
Возможно, вы можете объединить их в строки, разделенные каким-либо символом, например запятой. Сопоставление 1,34 и [1,34] должно возвращать один и тот же результат.   -  person MxLDevs    schedule 16.05.2013
comment
@Keikoku О, это хорошая идея.   -  person leon    schedule 16.05.2013
comment
Я чувствую, что это будет очень громоздко, преобразовать все в строку, а затем преобразовать все обратно. НО, похоже, это справится с задачей. Если кто-нибудь предложит элегантное решение, дайте мне знать! Спасибо.   -  person leon    schedule 16.05.2013
comment
Что делать, если у вас есть несколько пересечений между двумя списками?   -  person Noctis Skytower    schedule 16.05.2013
comment
Только самый длинный будет напечатан. Если они одинаковой длины, оба будут напечатаны. Это был бы другой список списков!   -  person leon    schedule 16.05.2013


Ответы (1)


Поднял это для вас (включая ваш комментарий о том, что все максимальные подсписки одинаковой длины должны быть возвращены в список):

def sublists(list1, list2):
    subs = []
    for i in range(len(list1)-1):
        for j in range(len(list2)-1):
            if list1[i]==list2[j] and list1[i+1]==list2[j+1]:
                m = i+2
                n = j+2
                while m<len(list1) and n<len(list2) and list1[m]==list2[n]:
                    m += 1
                    n += 1
                subs.append(list1[i:m])
    return subs

def max_sublists(list1, list2):
    subls = sublists(list1, list2)
    if len(subls)==0:
        return []
    else:
        max_len = max(len(subl) for subl in subls)
        return [subl for subl in subls if len(subl)==max_len]

Это работает хорошо для этих случаев:

In [10]: max_sublists([0,1,3,4,3,7,2],[0,3,4,3,7,3])
Out[10]: [[3, 4, 3, 7]]
In [11]: max_sublists([0,1,2,3,0,1,3,5,2],[1,2,3,4,5,1,3,5,3,7,3])
Out[11]: [[1, 2, 3], [1, 3, 5]]

Это не красиво, хотя и не очень быстро.

Вам нужно только выяснить, как сравнивать каждый подсписок в исходном списке подсписков, но это должно быть легко.

[Редактировать: я исправил ошибку и предотвратил появление вашей ошибки.]

person Ruben Tavernier    schedule 16.05.2013
comment
Элегантный! Спасибо!! Умно, что вы искали 2 совпадения подряд для цикла if. Это экономит время. Единственная небольшая проблема, с которой я сталкиваюсь, заключается в том, что я получаю сообщение об ошибке в строке max_len. Я думаю, это потому, что иногда есть только одно пересечение (или ни одного), и он ожидает запустить цикл for хотя бы один раз... или что-то в этом роде. Я еще не понял. - person leon; 17.05.2013
comment
Пожалуйста! Проблема в вашей строке max_len вполне может быть просто Python2.X против Python 3.X. Если вы используете Python 2.X, у вас может быть две записи этой строки как: max_len = max([len(subl) for subl in subls]) (так, с квадратными скобками, чтобы сначала заставить понимание списка в max-функции). Я надеюсь, что это работает! - person Ruben Tavernier; 17.05.2013
comment
Кстати, я думаю, что сделал опечатку в своей строке for j in range(len(list2)-2):, которая должна вычесть только 1 (вы можете видеть, где я запутался. ;-) - я перепроверю и отредактирую. - person Ruben Tavernier; 17.05.2013
comment
Оказывается, ошибка строки max_len намного проще. Вы, вероятно, получили ValueError: max() arg is an empty sequence, поэтому я исправил функцию, чтобы возвращать пустой список, когда не найдены подходящие подсписки. Я также исправил опечатку, которая глючила в некоторых тестах (я устал вчера). - person Ruben Tavernier; 17.05.2013
comment
Ошибка найдена! Я набрал print вместо return в конце sublists(). Ха-ха. Я не думаю, что даже необходимо указывать max_sublists() возвращать пустой список, потому что sublists() уже возвращает пустой список по умолчанию. Спасибо за вашу помощь! - person leon; 17.05.2013
comment
Пожалуйста, но это все же необходимо, потому что если sublists возвращает пустой список, вызов max(len(subl) for subl in []) приведет к ValueError: max() arg is an empty sequence. - person Ruben Tavernier; 19.05.2013