TAD de los grafos: Recorridos en un grafo completo
Definir la función
|
1 |
recorridos :: [a] -> [[a]] |
tal que recorridos xs es la lista de todos los posibles por el grafo cuyo conjunto de vértices es xs y cada vértice se encuentra conectado con todos los otros y los recorridos pasan por todos los vértices una vez y terminan en el vértice inicial. Por ejemplo,
|
1 2 |
λ> recorridos [2,5,3] [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
module Grafo_Recorridos_en_un_grafo_completo where import Data.List (permutations) import Test.Hspec (Spec, hspec, it, shouldBe) recorridos :: [a] -> [[a]] recorridos xs = [(y:ys) ++ [y] | y:ys <- permutations xs] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ recorridos [2 :: Int,5,3] `shouldBe` [[2,5,3,2],[5,2,3,5],[3,5,2,3],[5,3,2,5],[3,2,5,3],[2,3,5,2]] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0007 seconds -- 1 example, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
from itertools import permutations from typing import TypeVar A = TypeVar('A') def recorridos(xs: list[A]) -> list[list[A]]: return [(list(y) + [y[0]]) for y in permutations(xs)] # Verificación # ============ def test_recorridos() -> None: assert recorridos([2, 5, 3]) \ == [[2, 5, 3, 2], [2, 3, 5, 2], [5, 2, 3, 5], [5, 3, 2, 5], [3, 2, 5, 3], [3, 5, 2, 3]] print("Verificado") # La verificación es # >>> test_recorridos() # Verificado |