13. Clases de equivalencia y particiones

13.1 Introducción

En el tema anterior vimos que una relación de equivalencia agrupa elementos según un criterio. Ahora estudiaremos qué forma tienen esos grupos y cómo se relacionan con el concepto de partición.

Estos conceptos son útiles en programación para clasificar datos, agrupar registros, segmentar usuarios, organizar archivos y separar elementos según una propiedad común.

13.2 Qué es una clase de equivalencia

Dada una relación de equivalencia sobre un conjunto A, la clase de equivalencia de un elemento a es el conjunto de todos los elementos que son equivalentes a a.

Se lee: la clase de a contiene todos los elementos x del conjunto que están relacionados con a.

13.3 Ejemplo con restos módulo 3

Tomemos el conjunto A = {0, 1, 2, 3, 4, 5, 6, 7, 8} y la relación “tener el mismo resto al dividir por 3”.

Los elementos de cada clase tienen el mismo resto. Por ejemplo, 1, 4 y 7 dejan resto 1 al dividir por 3.

13.4 Representantes de clase

Cualquier elemento de una clase puede usarse como representante de esa clase. En el ejemplo anterior, [1], [4] y [7] representan la misma clase.

Esto ocurre porque todos esos elementos son equivalentes entre sí.

13.5 Qué es una partición

Una partición de un conjunto es una colección de subconjuntos no vacíos que cumplen dos condiciones:

• No se superponen: ningún elemento aparece en dos subconjuntos distintos.
• Cubren todo el conjunto: cada elemento aparece en algún subconjunto.

13.6 Relación entre equivalencia y partición

Toda relación de equivalencia genera una partición del conjunto. Cada bloque de la partición es una clase de equivalencia.

También ocurre lo inverso: si tenemos una partición de un conjunto, podemos definir una relación de equivalencia diciendo que dos elementos están relacionados si pertenecen al mismo bloque.

13.7 Ejemplo con archivos

Si definimos que dos archivos son equivalentes cuando tienen la misma extensión, las clases de equivalencia agrupan archivos por tipo.

Cada archivo pertenece a una sola clase y todas las clases juntas cubren el conjunto completo de archivos.

13.8 Agrupar por criterio en JavaScript

En programación, formar clases de equivalencia suele equivaler a agrupar elementos por una clave.

const archivos = ["index.html", "tema1.html", "main.css", "app.js", "main.js"];

function extension(nombre) {
  return nombre.split(".").pop();
}

const clases = {};

for (const archivo of archivos) {
  const clave = extension(archivo);
  if (!clases[clave]) clases[clave] = [];
  clases[clave].push(archivo);
}

console.log(clases);

La extensión actúa como criterio de equivalencia. Los archivos con la misma clave quedan en la misma clase.

13.9 Partición por restos en JavaScript

También podemos formar clases según el resto de dividir por un número. Este ejemplo crea la partición módulo 3.

const numeros = [0, 1, 2, 3, 4, 5, 6, 7, 8];
const particion = {};

for (const numero of numeros) {
  const resto = numero % 3;
  if (!particion[resto]) particion[resto] = [];
  particion[resto].push(numero);
}

console.log(particion);

El resultado tiene tres clases: los números con resto 0, los números con resto 1 y los números con resto 2.

13.10 Verificar si una agrupación es partición

Para que una agrupación sea una partición, todos los elementos deben aparecer exactamente una vez y ningún grupo debe estar vacío.

function esParticion(conjunto, grupos) {
  if (grupos.some(grupo => grupo.length === 0)) {
    return false;
  }

  const vistos = new Set();

  for (const grupo of grupos) {
    for (const elemento of grupo) {
      if (!conjunto.includes(elemento) || vistos.has(elemento)) {
        return false;
      }
      vistos.add(elemento);
    }
  }

  return conjunto.every(elemento => vistos.has(elemento));
}

const conjunto = [0, 1, 2, 3, 4, 5];
const grupos = [[0, 3], [1, 4], [2, 5]];

console.log(esParticion(conjunto, grupos));

13.11 Aplicaciones en programación

13.12 Errores comunes

• Creer que una clase de equivalencia contiene solo un elemento.
• Permitir que un mismo elemento aparezca en dos clases distintas.
• Olvidar que una partición debe cubrir todo el conjunto.
• Incluir grupos vacíos dentro de una partición.
• Confundir el representante de una clase con la clase completa.

13.13 Qué debes recordar de este tema

• La clase de equivalencia de un elemento contiene todos los elementos equivalentes a él.
• Distintos representantes pueden nombrar la misma clase.
• Una relación de equivalencia divide el conjunto en clases.
• El conjunto de clases forma una partición.
• Una partición no tiene superposición y cubre todo el conjunto.
• En programación, las clases de equivalencia se parecen a agrupaciones por clave.

13.14 Conclusión

Las clases de equivalencia permiten pasar de una relación a una organización por grupos. Las particiones muestran que esos grupos no se mezclan y cubren todos los elementos del conjunto.

En el próximo tema estudiaremos relaciones de orden parcial, donde la relación no agrupa por equivalencia, sino que establece una forma de comparación entre elementos.