Cliques de orden k
Nota: En este ejercicio usaremos las mismas notaciones que en el anterior importando el módulo Cliques.
Definir la función
|
1 |
kCliques :: Eq a => Grafo a -> Int -> [[a]] |
tal que (kCliques g k) es la lista de los cliques del grafo g de tamaño k. Por ejemplo,
|
1 2 3 4 5 6 |
λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 3 [[2,3,5],[2,4,5]] λ> kCliques [(1,2),(2,3),(2,4),(2,5),(3,5),(4,5)] 2 [[1,2],[2,3],[2,4],[2,5],[3,5],[4,5]] λ> kCliques [(n,n+1) | n <- [1..100]] 3 [] |
Nota: Escribir la solución en el módulo KCliques para poderlo usar en los siguientes ejercicios.
Soluciones
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 |
module KCliques where import Grafo import Cliques -- 1ª definición kCliques1 :: Eq a => Grafo a -> Int -> [[a]] kCliques1 g k = [xs | xs <- cliques g , length xs == k] -- 2ª definición kCliques :: Eq a => Grafo a -> Int -> [[a]] kCliques g k = [xs | xs <- kSubconjuntos (nodos g) k , esClique g xs] -- (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k -- elementos. Por ejemplo, -- ghci> kSubconjuntos "bcde" 2 -- ["bc","bd","be","cd","ce","de"] -- ghci> kSubconjuntos "bcde" 3 -- ["bcd","bce","bde","cde"] -- ghci> kSubconjuntos "abcde" 3 -- ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"] kSubconjuntos :: [a] -> Int -> [[a]] kSubconjuntos _ 0 = [[]] kSubconjuntos [] _ = [] kSubconjuntos (x:xs) k = [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k -- Comparación de eficiencia -- ========================= -- λ> kCliques1 [(n,n+1) | n <- [1..20]] 3 -- [] -- (4.28 secs, 3,204,548,608 bytes) -- λ> kCliques [(n,n+1) | n <- [1..20]] 3 -- [] -- (0.01 secs, 3,075,768 bytes) |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
«Es mejor resolver un problema de cinco maneras diferentes, que resolver cinco problemas de una sola manera.»
2 Comentarios