Python слова игры. Последняя буква первого слова == первая буква второго слова. Найти максимально возможную последовательность слов

Ваша идея вызвать функцию внутри себя является хорошей. Мы можем решить это с помощью рекурсии:

 def get_neighbors(word, choices): return set(x for x in choices if x[0] == word[-1]) def longest_path_from(word, choices): choices = choices - set([word]) neighbors = get_neighbors(word, choices) if neighbors: paths = (longest_path_from(w, choices) for w in neighbors) max_path = max(paths, key=len) else: max_path = [] return [word] + max_path def longest_path(choices): return max((longest_path_from(w, choices) for w in choices), key=len) 

Теперь мы просто определим наш список слов:

 words = ("audino bagon baltoy banette bidoof braviary bronzor carracosta " "charmeleon cresselia croagunk darmanitan deino emboar emolga " "exeggcute gabite girafarig gulpin haxorus") words = frozenset(words.split()) 

Вызов longest_path с набором слов:

 >>> longest_path(words) ['girafarig', 'gabite', 'exeggcute', 'emolga', 'audino'] 

Несколько вещей, чтобы знать: как вы указываете, это имеет экспоненциальную сложность, так что будьте осторожны! Кроме того, знайте, что у python есть предел рекурсии!

Используя некоторую черную магию и теорию графов, я нашел частичное решение, которое может быть хорошим (не полностью протестированным).

Идея состоит в том, чтобы сопоставить вашу проблему с проблемой графа, а не с простой итерационной проблемой (хотя она тоже может работать!). Поэтому я определил узлы графа как первые буквы и последние буквы ваших слов. Я могу создавать только ребра между узлами типа first и last . Я не могу перенести узел first числом X на узел last номера X (за ним не может следовать слово self). И от этого ваша проблема такая же, как и проблема с самым длинным путем, которая, как правило, является NP-трудной для общего случая 🙂

Получая некоторую информацию здесь: stackoverflow-17985202 Мне удалось написать это:

 g = "audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig gulpin haxorus" words = g.split() begin = [w[0] for w in words] # Nodes first end = [w[-1] for w in words] # Nodes last links = [] for i, l in enumerate(end): # Construct edges ok = True offset = 0 while ok: try: bl = begin.index(l, offset) if i != bl: # Cannot map to self links.append((i, bl)) offset = bl + 1 # next possible edge except ValueError: # no more possible edge for this last node, Next! ok = False # Great function shamelessly taken from stackoverflow (link provided above) import networkx as nx def longest_path(G): dist = {} # stores [node, distance] pair for node in nx.topological_sort(G): # pairs of dist,node for all incoming edges pairs = [(dist[v][0]+1,v) for v in G.pred[node]] if pairs: dist[node] = max(pairs) else: dist[node] = (0, node) node,(length,_) = max(dist.items(), key=lambda x:x[1]) path = [] while length > 0: path.append(node) length,node = dist[node] return list(reversed(path)) # Construct graph G = nx.DiGraph() G.add_edges_from(links) # TADAAAA! print(longest_path(G)) 

Хотя это выглядит хорошо, есть большой недостаток. Вы, например, работаете, потому что в результирующем графике входных слов нет цикла, однако это решение не выполняется на циклических графах. Способ вокруг этого – обнаружить циклы и сломать их. Обнаружение может быть выполнено следующим образом:

 if nx.recursive_simple_cycles(G): print("CYCLES!!! /o\") 

Разрыв цикла можно сделать, просто сбросив случайное ребро в цикле, а затем вы случайно найдете оптимальное решение для своей проблемы (представьте себе цикл с хвостом, вы должны сократить цикл на узле, имеющем 3 ребра), таким образом, я предложите грубо заставлять эту часть, пробуя все возможные перерывы цикла, вычисляя самый длинный путь и занимая самый длинный из самых длинных путей. Если у вас есть несколько циклов, это становится немного более взрывоопасным по количеству возможностей … но эй, это NP-жесткий, по крайней мере, так, как я его вижу, и я не планировал это решать сейчас 🙂

Надеюсь, поможет

Вот решение, которое не требует рекурсии. Он использует функцию перестановки itertools, чтобы посмотреть на все возможные упорядочения слов и найти ту, которая имеет самую длинную длину. Чтобы сэкономить время, как только заказ попадает на слово, которое не работает, оно перестает проверять это упорядочение и перемещается дальше.

 >>> g = 'girafarig eudino exeggcute omolga gabite' ... p = itertools.permutations(g.split()) ... longestword = "" ... for words in p: ... thistry = words[0] ... # Concatenates words until the next word doesn't link with this one. ... for i in range(len(words) - 1): ... if words[i][-1] != words[i+1][0]: ... break ... thistry += words[i+1] ... i += 1 ... if len(thistry) > len(longestword): ... longestword = thistry ... print(longestword) ... print("Final answer is {}".format(longestword)) girafarig girafariggabiteeudino girafariggabiteeudinoomolga girafariggabiteexeggcuteeudinoomolga Final answer is girafariggabiteexeggcuteeudinoomolga 

Сначала давайте посмотрим, как выглядит проблема:

 from collections import defaultdict import pydot words = ( "audino bagon baltoy banette bidoof braviary bronzor carracosta " "charmeleon cresselia croagunk darmanitan deino emboar emolga " "exeggcute gabite girafarig gulpin haxorus" ).split() def main(): # get first -> last letter transitions nodes = set() arcs = defaultdict(lambda: defaultdict(list)) for word in words: first = word[0] last = word[-1] nodes.add(first) nodes.add(last) arcs[first][last].append(word) # create a graph graph = pydot.Dot("Word_combinations", graph_type="digraph") # use letters as nodes for node in sorted(nodes): n = pydot.Node(node, shape="circle") graph.add_node(n) # use first-last as directed edges for first, sub in arcs.items(): for last, wordlist in sub.items(): count = len(wordlist) label = str(count) if count > 1 else "" e = pydot.Edge(first, last, label=label) graph.add_edge(e) # save result graph.write_jpg("g:/temp/wordgraph.png", prog="dot") if __name__=="__main__": main() 

приводит к

что делает решение достаточно очевидным (путь показан красным), но только потому, что граф ацикличен (за исключением двух тривиальных автопилот).