Ответ 1

В чем вы нуждаетесь, в основном, что делает любая утилита слияния: она пытается объединить две последовательности, сохраняя относительный порядок каждой последовательности. Вы можете использовать Python difflib модуль, чтобы разделить две последовательности и объединить их:

from difflib import SequenceMatcher

def merge_sequences(seq1,seq2):
    sm=SequenceMatcher(a=seq1,b=seq2)
    res = []
    for (op, start1, end1, start2, end2) in sm.get_opcodes():
        if op == 'equal' or op=='delete':
            #This range appears in both sequences, or only in the first one.
            res += seq1[start1:end1]
        elif op == 'insert':
            #This range appears in only the second sequence.
            res += seq2[start2:end2]
        elif op == 'replace':
            #There are different ranges in each sequence - add both.
            res += seq1[start1:end1]
            res += seq2[start2:end2]
    return res

Пример:

>>> keys1 = ['A', 'B', 'C', 'D', 'E',           'H', 'I']
>>> keys2 = ['A', 'B',           'E', 'F', 'G', 'H',      'J', 'K']
>>> merge_sequences(keys1, keys2)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']

Обратите внимание, что ответ, который вы ожидаете, не обязательно является единственным возможным. Например, если мы изменим порядок последовательностей здесь, мы получим еще один ответ, который справедлив:

>>> merge_sequences(keys2, keys1)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'I']

Ответ 2

Я бы использовал Set (cf. python doc), который я бы заполнил элементами из двух списков, один после другие.

И создайте список из набора, когда это будет сделано.

Обратите внимание, что в вашем вопросе есть противоречие/парадокс: вы хотите сохранить порядок для элементов, которые нельзя сравнивать (только равенство, потому что "они сложные строки", как вы сказали).

EDIT: OP правильно заметил, что наборы не сохраняют порядок вставки.

Ответ 3

Я подозреваю, что вы можете попросить решение проблемы кратчайшая общая суперпоследовательность, которая, как я считаю, NP-hard в общем случае произвольного количества входных последовательностей. Я не знаю о каких-либо библиотеках для решения этой проблемы, поэтому вам, возможно, придется реализовать один за другим. Вероятно, самый быстрый способ получить рабочий код - взять interjay-ответ, используя difflib, а затем использовать reduce для запуска его в произвольном количестве списков (обязательно укажите пустой список как третий аргумент reduce).

Ответ 4

Используя только списки, вы можете достичь этого с помощью нескольких простых циклов for и .copy():

def mergeLists(list1, list2):
    # Exit if list2 is empty
    if not len(list2):
        return list1
    # Copy the content of list2 into merged list
    merged = list2.copy()

    # Create a list for storing temporary elements
    elements = []
    # Create a variable for storing previous element found in both lists
    previous = None

    # Loop through the elements of list1
    for e in list1:
        # Append the element to "elements" list if it not in list2
        if e not in merged:
            elements.append(e)

        # If it is in list2 (is a common element)
        else:

            # Loop through the stored elements
            for x in elements:
                # Insert all the stored elements after the previous common element
                merged.insert(previous and merged.index(previous) + 1 or 0, x)
            # Save new common element to previous
            previous = e
            # Empty temporary elements
            del elements[:]

    # If no more common elements were found but there are elements still stored
    if len(elements)
        # Insert them after the previous match
        for e in elements:
            merged.insert(previous and merged.index(previous) + 1 or 0, e)
    # Return the merged list
    return merged

In [1]: keys1 = ["A", "B",      "D",      "F", "G", "H"]
In [2]: keys2 = ["A",      "C", "D", "E", "F",      "H"]
In [3]: mergeLists(keys1, keys2)
Out[3]: ["A", "B", "C", "D", "E", "F", "G", "H"]

Английский язык не является моим первым языком, и это довольно сложно объяснить, но если вам интересно объяснение, вот что он делает:

• Здесь есть локальный список elements, который может хранить временные элементы.
• Здесь есть локальная переменная с именем previous, в которой хранится предыдущий элемент, который был в обоих списках.
• Когда он найдет элемент, который НЕ находится в list2, но находится в list1, он добавит этот элемент в список elements и продолжит цикл.
• Когда он попадает в элемент, который находится в обоих списках, он перебирается через список elements, добавляя все элементы после элемента previous к list2.
• Новое соответствие затем сохраняется в previous и elements равно reset до [], и цикл продолжается.
• Начало списков и конец списков подсчитывается как общий элемент, если первый или последний элемент не является общим элементом в обоих списках.

Таким образом, он всегда будет следовать этому формату:

• Предыдущий общий элемент
• Элементы из списка1, между двумя общими элементами
• Элементы в списке2, между двумя общими элементами
• Новый общий элемент

Итак, например:

l1 = ["A", "B", "C",      "E"]
l2 = ["A",           "D", "E"]

• Повторяющийся общий элемент A будет первым в объединенном списке.
• Элементы из l1 между предыдущим общим элементом A и новым общим элементом E будут вставлены сразу после A.
• Элементы из l2 между предыдущим общим elmeent A и новым общим elmeent E будут вставлены сразу после элементов из l1.
• Новый общий элемент E будет последним элементом.

• Возвращаемся к шагу 1, если найдены более общие элементы.

  [ "A", "B", "C", "D", "E" ]

Ответ 5

Недавно я столкнулся с аналогичной проблемой при реализации функции. Сначала я попытался четко определить формулировку проблемы. Если я правильно понимаю, вот формулировка проблемы

Постановка задачи

Напишите функцию merge_lists, которая объединит список списков с перекрывающимися элементами, сохраняя при этом порядок элементов.

Ограничения

1. Если элемент A предшествует элементу B во всех списках, где они встречаются вместе, то элемент A также должен предшествовать элементу B в окончательном списке.

2. Если элемент A и элемент B меняются в разных списках, то есть в некоторых списках A предшествует B, а в некоторых других B предшествует A, то порядок A и B в окончательном списке должен быть таким же, как их порядок в первом списке, где они происходят вместе. То есть, если A предшествует B в l1, а B предшествует A в l2, то A должно предшествовать B в окончательном списке

3. Если Элемент A и Элемент B не встречаются вместе ни в одном списке, то их порядок должен определяться положением списка, в котором каждый из них встречается первым. То есть, если элемент A находится в l1 и l3, элемент B находится в l2 и l6, то порядок в окончательном списке должен быть A, а затем B

Тестовый пример 1:

Входные данные:

l1 = ["Тип и размер", "Ориентация", "Материал", "Местоположения", "Тип передней печати", "Тип обратной печати"]

l2 = ["Тип и размер", "Материал", "Расположение", "Тип передней печати", "Размер передней печати", "Тип обратной печати", "Размер обратной печати"]

l3 = ["Ориентация", "Материал", "Местоположения", "Цвет", "Тип передней печати"]

merge_lists ([l1, l2, l3])

Выход:

["Тип и размер", "Ориентация", "Материал", "Местоположения", "Цвет", "Тип передней печати", "Размер передней печати", "Тип обратной печати", "Размер обратной печати"]

Контрольный пример 2:

Входные данные:

l1 = ["T", "V", "U", "B", "C", "I", "N"]

l2 = ["Y", "V", "U", "G", "B", "I"]

l3 = ["X", "T", "V", "M", "B", "C", "I"]

l4 = ["U", "P", "G"]

списки слияния ([l1, l2, l3, l4])

Выход:

['Y', 'X', 'T', 'V', 'U', 'M', 'P', 'G', 'B', 'C', 'I', 'N']

Тестовый пример 3:

Входные данные:

l1 = ["T", "V", "U", "B", "C", "I", "N"]

l2 = ["Y", "U", "V", "G", "B", "I"]

l3 = ["X", "T", "V", "M", "I", "C", "B"]

l4 = ["U", "P", "G"]

списки слияния ([l1, l2, l3, l4])

Выход:

['Y', 'X', 'T', 'V', 'U', 'M', 'P', 'G', 'B', 'C', 'I', 'N']

Решение

Я пришел к разумному решению, которое решило его правильно для всех данных, которые у меня были. (Это может быть неправильно для какого-то другого набора данных. Оставьте это для других, чтобы комментировать это). Вот решение

def remove_duplicates(l):
    return list(set(l))

def flatten(list_of_lists):
    return [item for sublist in list_of_lists for item in sublist]

def difference(list1, list2):
    result = []
    for item in list1:
        if item not in list2:
            result.append(item)
    return result

def preceding_items_list(l, item):
    if item not in l:
        return []
    return l[:l.index(item)]

def merge_lists(list_of_lists):
    final_list = []
    item_predecessors = {}

    unique_items = remove_duplicates(flatten(list_of_lists))
    item_priorities = {}

    for item in unique_items:
        preceding_items = remove_duplicates(flatten([preceding_items_list(l, item) for l in list_of_lists]))
        for p_item in preceding_items:
            if p_item in item_predecessors and item in item_predecessors[p_item]:
                preceding_items.remove(p_item)
        item_predecessors[item] = preceding_items
    print "Item predecessors ", item_predecessors

    items_to_be_checked = difference(unique_items, item_priorities.keys())
    loop_ctr = -1
    while len(items_to_be_checked) > 0:
        loop_ctr += 1
        print "Starting loop {0}".format(loop_ctr)
        print "items to be checked ", items_to_be_checked
        for item in items_to_be_checked:
            predecessors = item_predecessors[item]
            if len(predecessors) == 0:
                item_priorities[item] = 0
            else:
                if all(pred in item_priorities for pred in predecessors):
                    item_priorities[item] = max([item_priorities[p] for p in predecessors]) + 1
        print "item_priorities at end of loop ", item_priorities
        items_to_be_checked = difference(unique_items, item_priorities.keys())
        print "items to be checked at end of loop ", items_to_be_checked
        print

    final_list = sorted(unique_items, key=lambda item: item_priorities[item])
    return final_list

Я также открыл исходный код в составе библиотеки с именем toolspy. Так что вы можете просто сделать это

pip install toolspy

from toolspy import merge_lists
lls=[['a', 'x', 'g'], ['x', 'v', 'g'], ['b', 'a', 'c', 'x']]
merge_lists(lls)