Самая длинная цепочка слов из списка слов

Ответ 1

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

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
def get_results(_start, _current, _seen):
  if all(c in _seen for c in words if c[0] == _start[-1]):
    yield _current
  else:
      for i in words:
        if i[0] == _start[-1]:
          yield from get_results(i, _current+[i], _seen+[i])


new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)

Выход:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

Это решение работает аналогично поиску по ширине, так как функция get_resuls будет продолжать выполнять итерацию по всему списку, пока текущее значение не было get_resuls раньше. Значения, которые были замечены функцией, добавляются в список _seen, в конечном счете прекращая поток рекурсивных вызовов.

Это решение также будет игнорировать результаты с дубликатами:

words = ['giraffe', 'elephant', 'ant', 'ning', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse',]
new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)

Выход:

['ant', 'tiger', 'racoon', 'ning', 'giraffe', 'elephant']

Ответ 2

У меня есть новая идея, как показано на рисунке:

Мы можем построить ориентированный граф словом [0] == word [-1], тогда проблема преобразуется, чтобы найти путь максимальной длины.

Ответ 3

Как уже упоминалось, проблема состоит в том, чтобы найти самый длинный путь в направленном ациклическом графе.

Для любого графика, связанного с Python, networkx - ваш друг.

Вам просто нужно инициализировать график, добавить узлы, добавить ребра и запустить dag_longest_path:

import networkx as nx
import matplotlib.pyplot as plt

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat',
         'hedgehog', 'mouse']

G = nx.DiGraph()
G.add_nodes_from(words)

for word1 in words:
    for word2 in words:
        if word1 != word2 and word1[-1] == word2[0]:
            G.add_edge(word1, word2)
nx.draw_networkx(G)
plt.show()
print(nx.algorithms.dag.dag_longest_path(G))

Он выводит:

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

Примечание: этот алгоритм работает только в том случае, если на графике нет циклов (циклов). Это означает, что он потерпит неудачу с ['ab', 'ba'] потому что будет путь бесконечной длины: ['ab', 'ba', 'ab', 'ba', 'ab', 'ba',...]

Ответ 4

В духе решений грубой силы вы можете проверить все перестановки в списке words и выбрать наилучшую непрерывную начальную последовательность:

from itertools import permutations

def continuous_starting_sequence(words):
    chain = [words[0]]
    for i in range(1, len(words)):
        if not words[i].startswith(words[i - 1][-1]):
            break
        chain.append(words[i])
    return chain

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
best = max((continuous_starting_sequence(seq) for seq in permutations(words)), key=len)

print(best)
# ['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

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

Это, конечно, имеет временную сложность O (nn!): D

Ответ 5

Эта функция создает тип итератора, называемый генератором (см.: что делает ключевое слово "yield"?). Он рекурсивно создает дополнительные экземпляры одного и того же генератора для изучения всех возможных хвостовых последовательностей:

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

def chains(words, previous_word=None):
    # Consider an empty sequence to be valid (as a "tail" or on its own):
    yield []
    # Remove the previous word, if any, from consideration, both here and in any subcalls:
    words = [word for word in words if word != previous_word]
    # Take each remaining word...
    for each_word in words:
        # ...provided it obeys the chaining rule
        if not previous_word or each_word.startswith(previous_word[-1]):
            # and recurse to consider all possible tail sequences that can follow this particular word:
            for tail in chains(words, previous_word=each_word):
                # Concatenate the word we're considering with each possible tail:
                yield [each_word] + tail  

all_legal_sequences = list(chains(words))  # convert the output (an iterator) to a list
all_legal_sequences.sort(key=len) # sort the list of chains in increasing order of chain length
for seq in all_legal_sequences: print(seq)
# The last line (and hence longest chain) prints as follows:
# ['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

Или, чтобы быстрее добраться до самой длинной цепи:

print(max(chains(words), key=len)

Наконец, вот альтернативная версия, которая позволяет повторять слова во вводе (т.е. Если вы включаете слово N раз, вы можете использовать его до N раз в цепочке):

def chains(words, previous_word_index=None):
    yield []
    if previous_word_index is not None:
        previous_letter = words[previous_word_index][-1]
        words = words[:previous_word_index] + words[previous_word_index + 1:]
    for i, each_word in enumerate( words ):
        if previous_word_index is None or each_word.startswith(previous_letter):
            for tail in chains(words, previous_word_index=i):
                yield [each_word] + tail  

Ответ 6

Вот рабочий рекурсивный подход грубой силы:

def brute_force(pool, last=None, so_far=None):
    so_far = so_far or []
    if not pool:
        return so_far
    candidates = []
    for w in pool:
        if not last or w.startswith(last):
            c_so_far, c_pool = list(so_far) + [w], set(pool) - set([w])
            candidates.append(brute_force(c_pool, w[-1], c_so_far))
    return max(candidates, key=len, default=so_far)

>>> brute_force(words)
['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

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

Ответ 7

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

    1. Form a tree with the root node as first word. 
    2. Form the branches if there is any word or words that starts 
with the alphabet with which this current word ends.
    3. Exhaust the entire given list based on the ending alphabet
 of current word and form the entire tree.
    4. Now just find the longest path of this tree and store it.
    5. Repeat steps 1 to 4 for each of the words given in the list
 and print the longest path among the longest paths we got above.

Надеюсь, это может дать лучшее решение, если будет представлен большой список слов. Я обновлю это с помощью фактической реализации кода.

Ответ 8

Надеюсь, более интуитивный способ сделать это без рекурсии. Перейдите через список и дайте Python сортировку и список понятий, сделайте для вас работу:

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

def chain_longest(pivot, words):
    new_words = []
    new_words.append(pivot)
    for word in words:
        potential_words = [i for i in words if i.startswith(pivot[-1]) and i not in new_words]
        if potential_words:
            next_word = sorted(potential_words, key = lambda x: len)[0]
            new_words.append(next_word)
            pivot = next_word
        else:
            pass
    return new_words

max([chain_longest(i, words) for i in words], key = len)
>>
['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

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

Постижение списка проходит через каждое слово в виде стержня и возвращает вам самую длинную цепочку.

Ответ 9

Другой ответ с использованием рекурсивного подхода:

def word_list(w_list, remaining_list):
    max_result_len=0
    res = w_list
    for word_index in range(len(remaining_list)):
        # if the last letter of the word list is equal to the first letter of the word
        if w_list[-1][-1] == remaining_list[word_index][0]:
            # make copies of the lists to not alter it in the caller function
            w_list_copy = w_list.copy()
            remaining_list_copy = remaining_list.copy()
            # removes the used word from the remaining list
            remaining_list_copy.pop(word_index)
            # append the matching word to the new word list
            w_list_copy.append(remaining_list[word_index])
            res_aux = word_list(w_list_copy, remaining_list_copy)
            # Keep only the longest list
            res = res_aux if len(res_aux) > max_result_len else res 
    return res

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
word_list(['dog'], words)

выход:

['dog', 'giraffe', 'elephant', 'tiger', 'racoon']