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

Question

Итак, это часть функции, которую я пытаюсь создать.

Я не хочу, чтобы код был слишком сложным.

У меня есть список слов,например,

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

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

(Редактировать: каждое слово не может быть использовано более чемодин раз. Кроме этого нет никаких других ограничений.)

Я хочу, чтобы вывод дал самую длинную цепочку слов, которая в данном случае:

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

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

Этот код правильно находит цепочку слов, если мы начинаем с определенного слова из списка, например слов [0] (т. Е. «Жираф»):

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

word_chain = []

word_chain.append(words[0])

for word in words:
    for char in word[0]:

       if char == word_chain[-1][-1]:
            word_chain.append(word)

print(word_chain)

Вывод:

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

НО, я хочу найти максимально длинную цепочку слов (объяснено выше).

Мой метод: Итак, я попытался использоватьприведенный выше рабочий код, который я написал и перебрал, используя каждое слово из списка в качестве отправной точки и находя цепочку слов для каждого слова [0], слова [1], слова [2] и т. д. Затем я попытался найтисамая длинная цепочка слов с помощью оператора if и сравнивает длину с предыдущей самой длинной цепочкой, но я не могу сделать это правильно, и я действительно не знаю, куда это идет.

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

word_chain = []
max_length = 0
for starting_word_index in range(len(words) - 1):

    word_chain.append(words[starting_word_index])

    for word in words:
        for char in word[0]:

            if char == word_chain[-1][-1]:
                word_chain.append(word)

    # Not sure

    if len(word_chain) > max_length:
        final_word_chain = word_chain
        longest = len(word_chain)
        word_chain.clear()

print(final_word_chain)

Этомоя n-ая попытка, я думаю, что эта распечатывает пустой список, до этого у меня были разные попытки, которые не смогли очистить список word_chain должным образом и в конечном итоге повторяли слова снова.Надеюсь, я не сделал это слишком утомительным или запутанным ... Спасибо!

Answer 1

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

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

Answer 2

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

Для всего графа, связанного с 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', ...]

Answer 3

В духе решений для грубой силы вы можете проверить все перестановки из списка 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

Answer 4

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

    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.

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

Answer 5

Другой ответ, использующий рекурсивный подход:

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']

Answer 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']

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

Answer 7

Эта функция создает тип итератора, называемого генератором (см .: Что делает ключевое слово 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  

Answer 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 если они начинаются с шарнирным словом и не появляются в новом спискеслов.Если найдено, то просто отсортируйте их по длине и возьмите первый элемент.

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

Answer 9

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

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 будет продолжать перебирать весь список, пока текущее значение не было вызвано ранее.Значения, которые были просмотрены функцией, добавляются в список _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']