Предпосылка:

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

У меня есть двенадцать списков с тысячами парных записей в каждом списке, и мне нужно найти все возможные цепочки записей в списках.

Порядок списков относительно друг друга фиксирован — list3 следует за list2 следует за list1 и т.д. У меня есть решение, но оно явно старомодное и не очень Pythonic — и для его запуска требуется вечность. Мой последний запуск занял 3 часа и 40 минут, что совершенно неосуществимо.

Итак, я ищу любые решения, которые были бы более эффективными и (надеюсь) ускорили процесс до чего-то управляемого.

Формат ввода:

Входные данные форматируются как 2D-списки, например:

 l1 = [ ['SHORT', 'FILM'], ['LEASE', 'BACK'], ['SHELF', 'LIFE'], ['HOLDS', 'FAST'], ... ]
l2 = [ ['BOAT', 'DECK'], ['FAST', 'FOOD'], ['FILM', 'PROP'], ['CHOW', 'LINE'], ... ]
l3 = [ ['FOOD', 'DRIVE'], ['PROP', 'PLANE'], ['GOAL', 'LINES'], ['WRAP', 'PARTY'], ... ]
.
.
.
l12 = [ [ ...
 

Вывод:

Мне нужно найти все возможные цепочки слов, которые соответствуют второму слову каждой пары в списке с первым словом в следующем списке и т. Д., Последовательно соединяя все пути.

Код, который у меня есть (сокращен только до трех списков для краткости), выглядит следующим образом:

 l1 = [['SHORT', 'FILM'], ['LEASE', 'BACK'], ['SHELF', 'LIFE'], ['HOLDS', 'FAST']]
l2 = [['BOAT', 'DECK'], ['FAST', 'FOOD'], ['FILM', 'PROP'], ['CHOW', 'LINE']]
l3 = [['FOOD', 'DRIVE'], ['PROP', 'PLANE'], ['GOAL', 'LINES'], ['WRAP', 'PARTY']]

ans = []

for i in range(len(l1)):
        for j in range(len(l2)):
                if  l1[i][1] == l2[j][0]:
                        for k in range(len(l3)):
                                if l2[j][1] == l3[k][0]:
                                        item = [l1[i][0], l1[i][1], l2[j][1], l3[k][1]]
                                        ans.append(item)

print(ans)
 

Что дает результат::

 [['SHORT', 'FILM', 'PROP', 'PLANE'], ['HOLDS', 'FAST', 'FOOD', 'DRIVE']]
 

Есть предложения по более эффективному и быстрому (!) способу сделать это?

ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИЯ И ОГРАНИЧЕНИЯ

Я узнал более подробную информацию об этом, которая предоставляет дополнительные ограничения, которые изменят код. Во-первых, на самом деле нет 12 списков, есть три списка, которые повторяются (по порядку) 4 раза: list1, list2, list3, list1, list2, list3 и т.д.

Кроме того, список должен быть «обведен» обратно в конце, чтобы второе слово пары в list12 (такое же, как list3) совпадало с первым словом в паре list1 (l12[j][1] == l1[k][0]) .

Например, для того, чтобы цепочка:

 HORSE BACK FLIP PHONE HOME RUNS SHORT FILM PROP PLANE RIDE HIGH
 

чтобы быть допустимым решением, HIGH HORSE оно должно быть в list12 / list3.

Кроме того, поскольку три списка повторяются четыре раза и обводятся по кругу, четыре цикла

 HORSE BACK FLIP PHONE HOME RUNS SHORT FILM PROP PLANE RIDE HIGH
PHONE HOME RUNS SHORT FILM PROP PLANE RIDE HIGH HORSE BACK FLIP
SHORT FILM PROP PLANE RIDE HIGH HORSE BACK FLIP PHONE HOME RUNS
PLANE RIDE HIGH HORSE BACK FLIP PHONE HOME RUNS SHORT FILM PROP
 

считаются одним и тем же циклом слов, и дубликаты должны быть удалены.

Фрагмент кода, который я использую, является:

 for i in range(len(list1)):
  for j in range(len(list2)):
    if  list1[i][1] == list2[j][0]:
      for k in range(len(list3)):
        if list2[j][1] == list3[k][0]:
          for l in range(len(list1)):
            if list3[k][1] == list1[l][0]:
              for m in range(len(list2)):
                if list1[l][1] == list2[m][0]:
                  for n in range(len(list3)):
                    if list2[m][1] == list3[n][0]:
                      for o in range(len(list1)):
                        if list3[n][1] == list1[o][0]:
                          for p in range(len(list2)):
                            if list1[o][1] == list2[p][0]:
                              for q in range(len(list3)):
                                if list2[p][1] == list3[q][0]:
                                  for r in range(len(list1)):
                                    if list3[q][1] == list1[r][0]:
                                      for s in range(len(list2)):
                                        if list1[r][1] == list2[s][0]:
                                          for t in range(len(list3)):
                                            if list2[s][1] == list3[t][0] and list3[t][1] == list1[i][0]:
                                              item = [list1[i][0], list1[i][1], list2[j][1], list3[k][1], list1[l][1], list2[m][1], list3[n][1], list1[o][1], list2[p][1], list3[q][1], list1[r][1], list2[s][1]]
                                              ans.append(item)
 

Что дает мне все циклы, но не удаляет дубликаты. И … для завершения требуется несколько часов.

Есть предложения?

Вы хотите создавать словари из каждого из ваших списков, чтобы вы могли выполнять быстрый поиск для каждого соединения, не перебирая весь следующий список в поисках совпадения. Это должно сэкономить вам кучу времени. Я мало что сделал с нотацией Big O, но я думаю, что это превращает проблему O (N ^ 2) в проблему O (N).

Вот как это сделать для приведенного вами сокращенного примера. Это должно работать так же хорошо (на самом деле намного лучше) для ваших 12 длинных списков:

 l1 = [['SHORT', 'FILM'], ['LEASE', 'BACK'], ['SHELF', 'LIFE'], ['HOLDS', 'FAST']]
l2 = [['BOAT', 'DECK'], ['FAST', 'FOOD'], ['FILM', 'PROP'], ['CHOW', 'LINE']]
l3 = [['FOOD', 'DRIVE'], ['PROP', 'PLANE'], ['GOAL', 'LINES'], ['WRAP', 'PARTY']]

# Define a list of our lists so we can iterate over them
lists = [l1, l2, l3]

# For each list except the first one, create an equivalent dictionary where the first value
# in each list entry is a key, and the second value is the corresponding value for that key.
dicts = [{e[0]:e[1] for e in l} for l in lists[1:]]

# Attempt to find a full chain for one of the pairs in list #1
def do_one_chain(pair):
    chain = []
    chain.extend(pair)
    for d in dicts:
        if pair[1] not in d:
            return None
        pair = (pair[1], d[pair[1]])
        chain.append(pair[1])
    return chain

# Iterate over our first list...
ans = []
for pair in l1:
    # Apply our search function to a pair from list #1
    r = do_one_chain(pair)
    # If a chain was found, add it to the answer list
    if r:
        ans.append(r)

# Print the found chains
print(ans)
 

Результат:

 [['SHORT', 'FILM', 'PROP', 'PLANE'], ['HOLDS', 'FAST', 'FOOD', 'DRIVE']]
 

Что приятно в этом, так это то, что решение не только намного эффективнее, но и намного чище и компактнее. Ни один из кодов не изменяется при добавлении дополнительных уровней. Вам просто нужно добавить новые уровни в lists список. Я знаю, что это то, что вы искали, опасаясь необходимости растягивать эти вложенные if операторы до 12 уровней, верно?

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