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

Question

所以，这是我正在尝试创建的函数的一部分。

我不想让代码太复杂。

我有一个单词列表，例如

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

单词链序列的想法是下一个单词以上一个单词结尾字母作为开头。

（编辑：每个单词只能使用一次。除此之外没有其他限制。）

我希望输出最长的单词链序列，这种情况下为：

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

我不太确定该如何做，我有几次尝试。其中一种...

如果我们从列表中的特定单词（例如 words[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']

但是，我想找到可能最长的单词链（如上所述）。

我的方法：因此，我尝试使用上面的可行代码，并循环遍历，使用列表中的每个单词作为起点，找到每个word[0]、word[1]、word[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列表，最终导致单词重复。

非常感谢任何帮助。希望我没有让事情变得太繁琐或令人困惑...谢谢！

- Matt

---

@dataLeo 你好，每个单词只能使用一次（因此大象只能使用一次），除此之外没有其他限制。目标是找到最长的单词链序列。 - Matt

你需要额外的预防措施以防止有人输入以相同字母开头和结尾的名字吗？（...好像我也想不出来...） - Jongware

这将是对 https://codegolf.stackexchange.com/ 的一项伟大贡献。 - Frozenthia

这个问题等价于在一个有向循环图中找到最长路径，其中边最多只被遍历一次。 - Mateen Ulhaq

这个问题的通用名称：https://stackoverflow.com/questions/29522351/longest-path-in-an-undirected-unweighted-graph - nhahtdh

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_results会在当前值之前没有被调用时继续迭代整个列表。已被函数看到的值将添加到_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']

- Ajax1234

Answer 2

我有一个新想法，如下图所示：

我们可以通过 word[0] == word[-1] 构建一个有向图，然后问题就转化为寻找最长路径。

- TimeSeam

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'，...]。

- Eric Duminil

---

“Acyclic”是一个很大的假设。如果有一个循环，问题就是NP难的。 - slider

@slider：确实。我会调查一下，看看是否有可能用networkx解决这个通用问题。 - Eric Duminil

Answer 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(n n!) :D

- slider

Answer 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  

- jez

Answer 6

希望能够提供更直观的方法而不是使用递归。遍历列表，让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 是否以您的枢轴词开头并且不出现在您的新单词列表中。如果找到，则按长度排序并取第一个元素。

列表推导式遍历每个单词作为枢轴，并返回最长的链。

- BernardL

---

预期输出和最长单词链是：['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']，你给出的是['giraffe', 'elephant', 'tiger', 'racoon']，还有什么我漏掉了吗？ - Matt

你可以用 key=len 替换 key = lambda x: len(x)。 - Keyur Potdar

@mandingo 对不起，我对输出结果感到困惑。让我更改一下。 - BernardL

Answer 7

这里是一个可行的递归暴力算法：

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

每次递归调用时，这个函数会从剩余的单词池中尝试使用每个合适的单词进行链式延续。然后它选择最长的这样的延续。

- user2390182

Answer 8

我对这个问题有一种基于树形结构的方法，可能会更快。我仍在努力实现代码，但以下是我的做法：

    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.

如果给出的单词列表很长，我希望这可以提供更好的解决方案。我将使用实际代码实现更新。

- CodeHunter

Answer 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)

output:

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

- Pedro Borges