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

Question

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

Я могу делать соответствующие буквы и слова вверх и хранить их в списках, но у меня возникают проблемы с тем, как обрабатывать потенциально экспоненциальное число возможностей слов в списках. Если слово 1 соответствует слову 2, а затем я спускаюсь по этому маршруту, как я могу вернуться назад, чтобы увидеть, соответствуют ли слова 3 или 4 словом один, а затем начинают свои собственные маршруты, все из первого слова?

Я думал о некотором способе вызвать функцию внутри себя, может быть?

Я знаю, что это не так, как будто я делаю то, что мне нужно, но это начало. Заранее благодарю за любую помощь!

g = "audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon cresselia croagunk darmanitan deino emboar emolga exeggcute gabite girafarig gulpin haxorus" 

def pokemon(): 
    count = 1 
    names = g.split() 
    first = names[count] 
    master = [] 
    for i in names: 
     print (i, first, i[0], first[-1]) 
     if i[0] == first[-1] and i not in master: 
      master.append(i) 
      count += 1 
      first = i 
      print ("success", master) 
    if len(master) == 0: 
     return "Pokemon", first, "does not work" 
    count += 1 
    first = names[count] 

pokemon() 

Answer 1

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

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 есть предел рекурсии!

Answer 2

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

Идея состоит в том, чтобы сопоставить проблему с проблемой графа, а не с простой итерационной проблемой (хотя она тоже может работать!). Поэтому я определил узлы графа как первые буквы и последние буквы ваших слов. Я могу создавать только ребра между узлами типа first и last. Я не могу сопоставить узел first номер X с узлом last номер X (за ним не может следовать слово self). И от того, ваша проблема так же, как the Longest path problem, который имеет тенденцию быть 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-трудное, по крайней мере, как я вижу это, и я не планировал решить, что теперь :)

Надеется, что это помогает

Answer 3

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

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

Answer 4

Во-первых, давайте посмотрим, что эта проблема выглядит следующим образом:

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

результатов в

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