es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Algoritmo para determinar qué listas cumplen con el requisito.

22 Jul, 2023 Programación

Me quedé atascado tratando de encontrar un algoritmo y ahora no sé qué hacer.

Necesito llegar de a a d pero solo desplazándome a través de estas listas:

[e, d]
[a, b, c]
[d, a]
[a, b]
[a, e, b]

Este es solo un ejemplo simple y la solución es:

[a → d] // 3ra línea
[a → e → d] // 5ta línea + 1ra línea
[a → b → e → d] // 2da + 5ta + 1ra línea

Pero tengo que resolverlo en Python.
Se me ocurrieron dos formas de resolver esto, la primera fue usando bucles for, pero los bucles comenzaron a repetirse y se volvieron muy lentos, así que decidí ir con la idea número 2.
Estaba pensando en crear una lista de todas las posibles combinaciones que comiencen con a y terminen con d. Luego, comprobar si esto es posible en nuestras listas especificadas.

from itertools import permutations

lst = ['a', 'b', 'c', 'd', 'e']

x = 'a'
y = 'd'

for i in range(1, len(lst)):
    perm = permutations(lst, i+1)

for j in list(perm):
    if (j[0] == x) and (j[-1] == y):
        print(j)

Pero luego, de alguna manera, me quedé atascado y ahora no sé qué hacer. ¿Podría alguien darme una pista? ¿O estoy enfocando esto de manera incorrecta?

edit:

Estoy tratando de encontrar todos los caminos y mostrarlos.

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Parece que estás en el camino correcto al generar todos los posibles caminos y comprobar si son válidos. Una forma de verificar si un camino es válido es iterar a través de las listas dadas y ver si el camino es un subconjunto de alguna de ellas. Aquí tienes un ejemplo de código:

    import itertools

listas = [
    ['e', 'd'],
    ['a', 'b', 'c'],
    ['d', 'a'],
    ['a', 'b'],
    ['a', 'e', 'b']
]

caminos = []
x = 'a'
y = 'd'

for i in range(1, len(listas) + 1):
    for camino in itertools.permutations(listas, i):
        # aplanar el camino
        camino_aplanado = [elemento for sublista in camino for elemento in sublista]
        if camino_aplanado[0] == x and camino_aplanado[-1] == y:
            valido = True
            for sublista in camino:
                if not set(sublista).issubset(set(camino_aplanado)):
                    valido = False
                    break
            if valido:
                caminos.append(camino_aplanado)

for camino in caminos:
    print(camino)

    Esto crea una lista de todos los posibles caminos tomando la permutación de las listas, los aplana en una única lista y verifica si el camino es válido iterando a través de las sub-listas y verificando si son un subconjunto del camino. Los caminos válidos se agregan a la lista caminos, que se imprime al final. ¡Espero que esto te ayude!

Comments are closed.