从单词列表中最长的单词链

Question

所以,这是我正在尝试的功能的一部分.

我不希望代码太复杂.

我有一个单词列表,例如

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

单词链序列的概念是下一个单词以最后一个单词结尾的字母开头.

(编辑:每个单词不能多次使用.除此之外没有其他限制.)

我希望输出给出最长的单词链序列,在这种情况下是:

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

我不确定该怎么做,我尝试过不同的尝试.其中一个......

如果我们从列表中的特定单词开始,此代码正确地找到单词链,例如单词[0](所以'giraffe'):

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

您可以使用递归来探索当包含正确的初始字符的每个可能的字母被添加到运行列表时出现的每个"分支":

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

Answer 2

我有一个新想法,如图所示:

我们可以通过word [0] == word [-1]构造有向图,然后转换问题以找到最大长度路径.

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