Clases de equivalencia
Definir la función
|
1 |
clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]] |
tal que (clasesEquivalencia xs r) es la lista de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,
|
1 2 3 4 5 6 |
λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3) [[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]] λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0) [[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]] λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y) [[-4,4],[-3,3],[-2,2],[-1,1],[0]] |
Soluciones
|
1 2 3 4 5 6 7 |
import Data.List (partition) clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]] clasesEquivalencia [] r = [] clasesEquivalencia ys@(x:xs) r = us : clasesEquivalencia vs r where (us,vs) = partition (r x) ys |
Solución en Maxima
|
1 2 |
clasesEquivalencia (xs,r) := equiv_classes (setify (xs),r)$ |
La evaluación de los ejemplos es
|
1 2 3 4 5 6 7 |
(%i6) xs : makelist (k,k,1,10)$ (%i7) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,3) = 0))); (%o7) {{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}} (%i8) clasesEquivalencia (xs, lambda ([x,y], is (remainder (x-y,5) = 0))); (%o8) {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}} (%i9) clasesEquivalencia (makelist(k,k,-4,4), lambda ([x,y], is (abs (x) = abs (y)))); (%o9) {{- 4, 4}, {- 3, 3}, {- 2, 2}, {- 1, 1}, {0}} |