grafos - python graph library
Cadena de palabras más larga de una lista de palabras (9)
Entonces, esta es una parte de una función que estoy tratando de hacer.
No quiero que el código sea demasiado complicado.
Tengo una lista de palabras, por ejemplo
words = [''giraffe'', ''elephant'', ''ant'', ''tiger'', ''racoon'', ''cat'', ''hedgehog'', ''mouse'']
La idea de la secuencia de la cadena de palabras es que la siguiente palabra comience con la letra con la que terminó la última palabra.
(Editar: cada palabra no se puede usar más de una vez. Aparte de eso no hay otras restricciones).
Quiero que la salida dé la secuencia de cadena de palabras más larga, que en este caso es:
[''hedgehog'', ''giraffe'', ''elephant'', ''tiger'', ''racoon'']
No estoy realmente seguro de cómo hacerlo, tuve diferentes intentos de intentar esto. Uno de ellos...
Este código encuentra la cadena de palabras correctamente si comenzamos con una palabra específica de la lista, por ejemplo, palabras [0] (entonces, ''jirafa''):
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)
Salida:
[''giraffe'', ''elephant'', ''tiger'', ''racoon'']
PERO, quiero encontrar la cadena de palabras más larga posible (explicada anteriormente).
Mi método: Entonces, traté de usar el código de trabajo anterior que escribí y repetí, usando cada palabra de la lista como punto de partida y encontrando la cadena de palabras para cada palabra [0], palabra [1], palabra [2] ] etc. Luego traté de encontrar la cadena de palabras más larga utilizando una instrucción if y comparar la longitud con la cadena más larga anterior, pero no puedo hacerlo correctamente y no sé realmente a dónde va esto.
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)
Este es mi noveno intento, creo que este imprime una lista vacía, tuve diferentes intentos antes de esto que no pudieron borrar la lista de cadena de palabras correctamente y terminaron repitiendo las palabras otra vez.
Cualquier ayuda muy apreciada. Ojalá no haya hecho esto demasiado tedioso o confuso ... ¡Gracias!
Aquí hay un enfoque recursivo de la fuerza bruta que funciona:
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'']
En cada llamada recursiva, esto intenta continuar la cadena con cada palabra elegible del grupo restante. A continuación, elige la continuación más larga.
Como lo mencionaron otros, el problema es encontrar la ruta más larga en un gráfico acíclico dirigido .
Para cualquier gráfico relacionado con Python, networkx es tu amigo.
Solo necesita inicializar el gráfico, agregar los nodos, agregar los bordes y lanzar 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))
Produce:
[''hedgehog'', ''giraffe'', ''elephant'', ''tiger'', ''racoon'']
Nota: este algoritmo solo funciona si no hay ciclos (bucles) en el gráfico. Significa que fallará con [''ab'', ''ba''] porque habría un camino de longitud infinita: [''ab'', ''ba'', ''ab'', ''ba'', ''ab'', ''ba'', ...]
Con suerte, una forma más intuitiva de hacerlo sin recursión. Iterar a través de la lista y dejar que la ordenación y comprensión de Python haga el trabajo por usted:
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'']
Establezca un pivote y verifique el potential_words de palabras potential_words si comienzan con su palabra dinámica y no aparecen en su nueva lista de palabras. Si los encuentra, simplemente ordénelos por longitud y tome el primer elemento.
La lista de comprensión pasa por cada palabra como un pivote y te devuelve la cadena más larga.
En el espíritu de las soluciones de fuerza bruta, puede verificar todas las permutaciones de la lista de words y elegir la mejor secuencia de inicio continuo:
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'']
Como estamos considerando todas las permutaciones, sabemos que debe haber una permutación que comience con la cadena de palabras más grande.
Esto, por supuesto, tiene una complejidad de tiempo O (nn) : D
Esta función crea un tipo de iterador llamado generador (consulte: ¿Qué hace la palabra clave "rendimiento"? ). Crea recursivamente más instancias del mismo generador para explorar todas las secuencias de cola posibles:
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'']
O, para ir directamente a la cadena más larga de manera más eficiente:
print(max(chains(words), key=len)
Finalmente, aquí hay una versión alternativa que permite palabras repetidas en la entrada (es decir, si incluye una palabra N veces, puede usarla N veces en la cadena):
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
Otra respuesta utilizando un enfoque recursivo:
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)
salida:
[''dog'', ''giraffe'', ''elephant'', ''tiger'', ''racoon'']
Puede usar la recursión para explorar cada "rama" que emerge cuando todas las letras posibles que contienen el carácter inicial adecuado se agregan a una lista en ejecución:
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)
Salida:
[''hedgehog'', ''giraffe'', ''elephant'', ''tiger'', ''racoon'']
Esta solución funciona de manera similar a la búsqueda en primer lugar, ya que la función get_resuls continuará get_resuls en toda la lista siempre que no se haya llamado antes al valor actual. Los valores que ha visto la función se agregan a la lista _seen , lo que finalmente _seen el flujo de llamadas recursivas.
Esta solución también ignorará los resultados con duplicados:
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)
Salida:
[''ant'', ''tiger'', ''racoon'', ''ning'', ''giraffe'', ''elephant'']
Tengo un enfoque basado en árboles para esta pregunta que podría ser más rápido. Todavía estoy trabajando en la implementación del código, pero esto es lo que haría:
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.
Espero que esto pueda dar una mejor solución en caso de que haya una gran lista de palabras. Voy a actualizar esto con la implementación del código real.
