Ordenación de ternas de enteros
Las ternas de números enteros positivos se pueden ordenar por su suma y las de la misma suma por orden lexicográfico. Por ejemplo,
- ternas de suma 3:
|
1 |
(1,1,1) |
- ternas de suma 4:
|
1 |
(1,1,2),(1,2,1),(2,1,1) |
- ternas de suma 5:
|
1 |
(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1) |
- ternas de suma 6
|
1 |
(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1) |
y así sucesivamente.
Definir la función
|
1 |
ternas :: [(integer,integer,integer)] |
tal que ternas es la lista de las ternas de enteros positivos con el orden descrito anteriormente. por ejemplo,
|
1 2 3 4 5 |
λ> take 20 ternas [(1,1,1), (1,1,2),(1,2,1),(2,1,1), (1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1), (1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)] |
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 |
import Data.List (nub, permutations, sort) ternas :: [(Integer,Integer,Integer)] ternas = concatMap ternasSuma [3..] -- (ternasSuma n) es la lista de las ternas de enteros positivos cuya -- suma es n ordenadas lexicográficamte. Por ejemplo, -- λ> ternasSuma 3 -- [(1,1,1)] -- λ> ternasSuma 4 -- [(1,1,2),(1,2,1),(2,1,1)] -- λ> ternasSuma 5 -- [(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)] -- λ> ternasSuma 6 -- [(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)] ternasSuma :: Integer -> [(Integer,Integer,Integer)] ternasSuma n = sort (concatMap permutaciones [(a,b,c) | a <- [1..n] , b <- [a..n] , let c = n-a-b , b <= c]) -- (permutaciones t) es la lista de las permutaciones de la terna t. Por ejemplo, -- λ> permutaciones (1,2,3) -- [(1,2,3),(2,1,3),(3,2,1),(2,3,1),(3,1,2),(1,3,2)] -- λ> permutaciones (1,1,2) -- [(1,1,2),(2,1,1),(1,2,1)] -- λ> permutaciones (1,1,1) -- [(1,1,1)] permutaciones :: (Integer,Integer,Integer) -> [(Integer,Integer,Integer)] permutaciones (a,b,c) = nub [(x,y,z) | [x,y,z] <- permutations [a,b,c]] |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>