Distancia a Erdős
Una de las razones por la que el matemático húngaro Paul Erdős es conocido es por la multitud de colaboraciones que realizó durante toda su carrera, un total de 511. Tal es así que se establece la distancia a Erdős como la distancia que has estado de coautoría con Erdős. Por ejemplo, si eres Paul Erdős tu distancia a Erdős es 0, si has escrito un artículo con Erdős tu distancia es 1, si has escrito un artículo con alguien que ha escrito un artículo con Erdős tu distancia es 2, etc. El objetivo de este problema es definir una función que a partir de una lista de pares de coautores y un número natural n calcular la lista de los matemáticos a una distancia n de Erdős.
Para el problema se considerará la siguiente lista de coautores
1 2 3 4 5 6 7 8 9 10 11 12 |
coautores :: [(String,String)] coautores = [("Paul Erdos","Ernst Straus"),("Paul Erdos","Pascual Jordan"), ("Paul Erdos","D. Kleitman"),("Albert Einstein","Ernst Straus"), ("John von Newmann","David Hilbert"),("S. Glashow","D. Kleitman"), ("John von Newmann","Pascual Jordan"), ("David Pines","D. Bohm"), ("Albert Einstein","Otto Stern"),("S. Glashow", "M. Gell-Mann"), ("Richar Feynman","M. Gell-Mann"),("M. Gell-Mann","David Pines"), ("David Pines","A. Bohr"),("Wolfgang Pauli","Albert Einstein"), ("D. Bohm","L. De Broglie"), ("Paul Erdos","J. Conway"), ("J. Conway", "P. Doyle"),("Paul Erdos","A. J. Granville"), ("A. J. Granville","B. Mazur"),("B. Mazur","Andrew Wiles")] |
La lista anterior es real y se ha obtenido del artículo Famous trails to Paul Erdős.
Definir la función
1 |
numeroDeErdos :: [(String, String)] -> Int -> [String] |
tal que (numeroDeErdos xs n) es la lista de lista de los matemáticos de la
lista de coautores xs que se encuentran a una distancia n de Erdős. Por ejemplo,
1 2 3 4 5 6 |
λ> numeroDeErdos coautores 0 ["Paul Erdos"] λ> numeroDeErdos coautores 1 ["Ernst Straus","Pascual Jordan","D. Kleitman","J. Conway","A. J. Granville"] λ> numeroDeErdos coautores 2 ["Albert Einstein","John von Newmann","S. Glashow","P. Doyle","B. Mazur"] |
Nota: Este ejercicio ha sido propuesto por Enrique Naranjo.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
data Arbol a = N a [Arbol a] deriving Show coautores :: [(String,String)] coautores = [("Paul Erdos","Ernst Straus"),("Paul Erdos","Pascual Jordan"), ("Paul Erdos","D. Kleitman"),("Albert Einstein","Ernst Straus"), ("John von Newmann","David Hilbert"),("S. Glashow","D. Kleitman"), ("John von Newmann","Pascual Jordan"), ("David Pines","D. Bohm"), ("Albert Einstein","Otto Stern"),("S. Glashow", "M. Gell-Mann"), ("Richar Feynman","M. Gell-Mann"),("M. Gell-Mann","David Pines"), ("David Pines","A. Bohr"),("Wolfgang Pauli","Albert Einstein"), ("D. Bohm","L. De Broglie"), ("Paul Erdos","J. Conway"), ("J. Conway", "P. Doyle"),("Paul Erdos","A. J. Granville"), ("A. J. Granville","B. Mazur"),("B. Mazur","Andrew Wiles")] -- 1ª solución -- =========== numeroDeErdos :: [(String, String)] -> Int -> [String] numeroDeErdos xs n = nivel n (arbolDeErdos xs "Paul Erdos") -- (arbolDeErdos xs a) es el árbol de coautores de a según la lista de -- coautores xs. Por ejemplo, -- λ> arbolDeErdos coautores "Paul Erdos" -- N "Paul Erdos" -- [N "Ernst Straus" -- [N "Albert Einstein" -- [N "Wolfgang Pauli" [], -- N "Otto Stern" []]], -- N "Pascual Jordan" -- [N "John von Newmann" -- [N "David Hilbert" []]], -- N "D. Kleitman" -- [N "S. Glashow" -- [N "M. Gell-Mann" -- [N "Richar Feynman" [], -- N "David Pines" -- [N "A. Bohr" [], -- N "D. Bohm" -- [N "L. De Broglie" []]]]]], -- N "J. Conway" -- [N "P. Doyle" []], -- N "A. J. Granville" -- [N "B. Mazur" -- [N "Andrew Wiles" []]]] arbolDeErdos :: [(String, String)] -> String -> Arbol String arbolDeErdos xs a = N a [arbolDeErdos noColaboradores n | n <- colaboradores] where colaboradores = [filtra a (x,y) | (x,y) <- xs, x == a || y == a] filtra a (x,y) | a == x = y | otherwise = x noColaboradores = [(x,y) | (x,y) <- xs, x /= a, y /= a] -- (nivel n a) es la lista de los elementos del árbol a en el nivel -- n. Por ejemplo, -- nivel 0 (N 3 [N 5 [N 6 []], N 7 [N 9 []]]) == [3] -- nivel 1 (N 3 [N 5 [N 6 []], N 7 [N 9 []]]) == [5,7] -- nivel 2 (N 3 [N 5 [N 6 []], N 7 [N 9 []]]) == [6,9] nivel :: Int -> Arbol a -> [a] nivel 0 (N a xs) = [a] nivel n (N a xs) = concatMap (nivel (n-1)) xs -- 2ª solución -- =========== numeroDeErdos2 :: [(String, String)] -> Int -> [String] numeroDeErdos2 = auxC ["Paul Erdos"] where auxC v xs 0 = v auxC v xs x = auxC (n v) (m v xs) (x-1) where n v = [a | (a,b) <- xs, elem b v] ++ [b | (a,b) <- xs, elem a v] m ys xs = [(a,b) | (a,b) <- xs , notElem a ys && notElem b ys] -- 3ª solución -- =========== numeroDeErdos3 :: [(String, String)] -> Int -> [String] numeroDeErdos3 ps n = (sucCoautores "Paul Erdos" ps) !! n -- (sucCoautores a ps) es la sucesión de coautores de a en ps ordenados -- por diatancia. Por ejemplo, -- λ> take 3 (sucCoautores "Paul Erdos" coautores) -- [["Paul Erdos"], -- ["Ernst Straus","Pascual Jordan","D. Kleitman","J. Conway", -- "A. J. Granville"], -- ["Albert Einstein","John von Newmann","S. Glashow","P. Doyle", -- "B. Mazur"]] -- λ> sucCoautores "Albert Einstein" coautores -- [["Albert Einstein"], -- ["Ernst Straus","Otto Stern","Wolfgang Pauli"], -- ["Paul Erdos"], -- ["Pascual Jordan","D. Kleitman","J. Conway", "A. J. Granville"], -- ["John von Newmann","S. Glashow","P. Doyle","B. Mazur"], -- ["David Hilbert","M. Gell-Mann","Andrew Wiles"], -- ["David Pines","Richar Feynman"], -- ["D. Bohm","A. Bohr"], -- ["L. De Broglie"]] sucCoautores :: String -> [(String, String)] -> [[String]] sucCoautores a ps = takeWhile (not . null) (map fst (iterate sig ([a], as \\ [a]))) where as = elementos ps sig (xs,ys) = (zs,ys \\ zs) where zs = [y | y <- ys , or [elem (x,y) ps || elem (y,x) ps | x <- xs]] -- (elementos ps) es la lista de los elementos de los pares ps. Por -- ejemplo, -- elementos [(1,3),(3,2),(1,5)] == [1,3,2,5] elementos :: Eq a => [(a, a)] -> [a] elementos = nub . (concatMap (\(x,y) -> [x,y])) |