Объединить два списка строк

Question

Если два списка строк, содержащих дубликаты, сохраняются для одного элемента в каждом списке, как бы вы объединили их в один список, содержащий одну копию каждого значения в порядке списка?

К примеру, учитывая следующие два списка в Python:

a = ['Second', 'Third', 'Fourth'] 
b = ['First', 'Second', 'Third'] 

Или

a = ['First', 'Third', 'Fourth'] 
b = ['First', 'Second', 'Third'] 

Как бы вы объединить два списка, чтобы получить единый список, как это:

result = ['First', 'Second', 'Third', 'Fourth'] 

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

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

a = ['First', 'Third', 'Fourth'] 
b = ['First', 'Second', 'Fourth'] 

Это может иметь 'Third' и 'Second' в любом порядке, так как нет ни одного пункта в обоих списках между ними, чтобы обеспечить руководство.

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

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

Answer 1

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

1. Возьмите следующий индекс в А.
2. Шаг через В поисках совпадения:
   1. Если был матч:
      • Удалить все от начала до B включительно матч в B, и добавить к C
   2. Если не было матча:
      • объявления d Индекс А до С
3. Повторите
4. Если есть что-то осталось в B, добавить его к С.

Это питон код для алгоритма:

a1 = ['Second', 'Third', 'Fourth'] 
b1 = ['First', 'Second', 'Third'] 

a2 = ['First', 'Third', 'Fourth'] 
b2 = ['First', 'Second', 'Third'] 

a3 = ['First', 'Third', 'Fourth'] 
b3 = ['First', 'Second', 'Fourth'] 

def merge(a, b): 
    c = [] 
    b_oldindex = 0 
    for a_index in range(len(a)): 
     match = False 
     for b_index in range(b_oldindex, len(b)): 
      if a[a_index] == b[b_index]: 
       c.extend(b[b_oldindex:b_index+1]) 
       b_oldindex = b_index + 1 
       match = True 
       break 
     if not match: 
      c.append(a[a_index]) 
    if b_oldindex < len(b): 
     c.extend(b[b_oldindex:]) 
    return c 

print(merge(a1,b1)) 
print(merge(a2,b2)) 
print(merge(a3,b3)) 
print(merge(b1,a1)) 
print(merge(b2,a2)) 
print(merge(b3,a3)) 

Который производит следующие данные:

['First', 'Second', 'Third', 'Fourth'] 
['First', 'Second', 'Third', 'Fourth'] 
['First', 'Third', 'Second', 'Fourth'] 
['First', 'Second', 'Third', 'Fourth'] 
['First', 'Second', 'Third', 'Fourth'] 
['First', 'Second', 'Third', 'Fourth'] 

Во всех тестовых случаях единственный, который не может произвести правильный заказ, - merge(a3,b3).

полностью Решение проблемы может включать в себя осуществление правильного алгоритма слияния (как это используется в сортировка слиянием), которая требует умения оценить порядок, что элементы должны быть. Вы можете увидеть python implementation of merge sort в Rosetta коде.

UPDATE:

Учитывая, что это на самом деле, чтобы отсортировать рассрочка в наборе книг, вы можете избежать ситуаций, вы описанные в вашем третьем наборе данных, принимая дополнительную информацию во внимание. А именно, используйте функцию merge в списках в обратном порядке публикации авторских прав или публикации.

Например, в вашем случае:

a3 = ['First', 'Third', 'Fourth'] # Second novel 
b3 = ['First', 'Second', 'Fourth'] # Third novel 

a3 's книга была бы опубликована до b3' книги s. Если вы можете собрать такие метаданные, вы можете избежать этой проблемы.

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

Answer 2

Использование библиотеки bisect Python.

from bisect import insort 

a = ['First', 'Third', 'Fourth'] 
b = ['First', 'Second', 'Fourth'] 
for entry in b: 
    insort(entry, a) 

unique = Set(a) 
print unique 

Примечание: очевидно, строки не будут сравнивать с тем правильно, вы, вероятно, захотите использовать словарь для этого!

Answer 3

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

a = ['Second', 'Third', 'Fourth'] 
b = ['First', 'Second', 'Third'] 
c= list(set(a+b)) 
['Second', 'Fourth', 'Third', 'First'] 
#Note that set will not organize anything, it will just delete the duplicates 

Answer 4

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

newlist = [] 
for i in range(len(a)): 
    if a[i] == b[i]: 
    newlist.append(a) 
    else: 
    newlist.append(a) 
    newlist.append(b) 

Если ваши списки более усложняют превратить один из них в словарь первый и проверить друг против друга при слиянии.

Answer 5

Простой алгоритм:

1. Concat список
2. Удалить Dups
3. Сортировать

Код:

def order_list(lst, order_dict): 
    return sorted(list(lst), key = lambda x: order_dict.get(x, -1)) 

c = list(set(a + b)) 
ord_dict = {"First": 1, "Second": 2, "Third": 3, "Fourth": 4} 
order_list(c, ord_dict) 

Answer 6

У вас есть 2 различных проблем здесь:

• Дубликат устранение
• Заказ

Я бы их по отдельности. Устранение дублирования достаточно просто. Используйте set:

>>> a = ['Second', 'Third', 'Fourth'] 
>>> b = ['First', 'Second', 'Third'] 
>>> x = set(a) 
>>> x 
set(['Second', 'Fourth', 'Third']) 
>>> x.update(b) 
>>> x 
set(['Second', 'Fourth', 'Third', 'First']) 

Тогда вам нужно к определить порядок каким-то образом. Самый простой способ сделать это может быть для отображения каждого возможного элемента значения:

>>> order_dict = {'First': 1, 'Second': 2, 'Third': 3, 'Fourth': 4} 
>>> result = sorted(list(x), key=lambda i: order_dict[i]) 
>>> result 
['First', 'Second', 'Third', 'Fourth'] 

В качестве альтернативы, можно использовать какое-то функцию сравнения с sorted «s cmp аргументом, если вы можете определить для ваших ценностей.

Надеюсь, это поможет.

Answer 7

У меня была такая же проблема, и у меня есть ответ. Я нашел этот пост, потому что искал больше питонических способов сделать это.

Во-первых, замечание о частном случае:

a=['A','C','D','E'] 
b=['A','B','D','F'] 
c=joinListsOrdered(a,b) 

в моем случае у меня нет никаких проблем: ['A','B','C','D','E','F'] так хорошо, как ['A','C','B','D','F','E']. Единственное условие проверки, которое я хочу: порядок элементов в c уважает порядок в a и b отдельно, то есть [el for el in c if el in a] по размеру равен a (и эквивалентно b). Я также думаю, что это единственная разумная позиция по этой проблеме без дополнительной информации о проблеме.

Это означает, что основное внимание уделяется общим элементам (['A', 'D']). Если они находятся в правильном порядке, все остальное можно легко застрять посередине. Таким образом, этот алгоритм:

def joinListsOrdered(a,b): 
    # Find ORDERED common elements 
    order={} 
    for i, e in enumerate(a): 
     order[e]=i 
    commonElements=sorted(set(a) & set(b), key=lambda i: order[i]) 
    # Cycle on each common element. 
    i=0 #index of a 
    j=0 #index of b 
    c=[] 
    for comEl in commonElements: 
     while not a[i]==comEl: 
      c.append(a[i]) 
      i=i+1 
     while not b[j]==comEl: 
      c.append(b[j]) 
      j=j+1 
     c.append(comEl) 
     i=i+1;j=j+1 
    # Add the eventual residuals after the last common element. 
    c=c+a[i:]+b[j:] 
    return c 

Конечно, не соблюдает условия проверки, если порядок в a и b для некоторого общего элемента отличается, но в этом случае проблема не имеет решения.