Introducción
El estudio de las correspondencias, aplicaciones y los tipos de éstas últimas entre dos conjuntos finitos cualesquiera es una materia que casi siempre se trata de soslayo en el primer curso de todas las ingenierías. Admitiendo que conceptualmente es un tema sencillo, eso no quiere decir que no tenga aplicaciones prácticas interesantes. En efecto: existen situaciones en que debemos emparejar elementos de dos conjuntos distintos A y B sujetos a ciertas restricciones de compatibilidad; esto es: existen elementos del conjunto A que no pueden emparejarse con según qué elementos del conjunto B y viceversa. Dado este planteamiento, es interesante a veces determinar todas las formas de emparejamiento posibles que respeten las leyes de compatibilidad citadas. Otras veces sólo nos interesará encontrar una forma de emparejamiento al azar. Todo lo anterior se tratará en este monográfico. Además se describirá una serie de herramientas computacionales que permiten extraer toda la información anterior. Nos centraremos para finalizar en una aplicación práctica muy interesante de todos los conceptos anteriores: el juego del Amigo Invisible.
Pero antes de todo ello conviene repasar algunos conceptos matemáticos muy sencillos, como son: productos cartesianos, correspondencias, aplicaciones o funciones y sus tipos.
Productos cartesianos y correspondencias
Sean dos conjuntos finitos de nombres A y B. El número de elementos de cada conjunto definirá el cardinal de dicho conjunto.
Denominaremos producto cartesiano de los conjuntos A y B (y notaremos como AxB) al conjunto de todos los pares ordenados (a, b) donde a es un elemento de A y b es un elemento de B. En este contexto el conjunto A se denominará conjunto inicial y el conjunto B conjunto final. Además, dado un par (a, b) diremos que b es imagen de a y a es antiimagen de b.
Dado el producto cartesiano anterior, una correspondencia (que notaremos como A->B) es cualquier subconjunto de éste. Es común representar una correspondencia como una tabla donde cada columna representa un elemento del conjunto A y cada fila un elemento del conjunto B. Así, dados dos elementos a de A y b de B, si el par (a, b) pertenece a la correspondencia marcaremos la celda correspondiente con una equis o un valor true y la dejaremos en blanco (o con un valor false) en caso contrario.
Veamos un ejemplo. Sean los conjuntos A={a, b, c, d} y B={x, y, z}. Podemos establecer una correspondencia mediante la tabla siguiente:
| a | b | c | d | |
| x | false | true | false | false |
| y | true | false | true | false |
| z | true | true | false | false |
Tabla 1 – Ejemplo de correspondencia entre los conjuntos A y B.
La correspondencia anterior está formada por los siguientes pares:
A->B={(a, y), (a, z), (b, x), (b, z), (c, y), (d, nulo)}
Obsérvese que el elemento d del conjunto A no está relacionado con ningún elemento del conjunto B. Para representar tal situación lo que hacemos es emparentar el elemento d con el elemento nulo (que llamaremos nulo), formando así el par (d, nulo).
Aplicaciones
Dada una correspondencia A->B diremos que ésta es aplicación (también denominada función) si todo elemento del conjunto A tiene una imagen única en el conjunto B.
Establezcamos por ejemplo la siguiente aplicación entre los conjuntos A y B:
| a | b | c | d | |
| x | false | false | false | true |
| y | true | false | true | false |
| z | false | true | false | false |
Tabla 2 – Ejemplo de aplicación entre los conjuntos A y B.
Vemos que en todas las columnas aparece un true y sólo uno. La aplicación representada (que denominaremos f) es entonces:
f={(a, y), (b, z), (c, y), (d, x)}
En la expresión anterior podemos afirmar que y es imagen de a por la aplicación f, y lo notaremos como: y=f(a). De forma análoga escribiremos: z=f(b), y=f(c) y x=f(d). Una forma más abreviada aún de notar la aplicación anterior es escribiendo únicamente las imágenes, de la forma:
f={y, z, y, x}
En la notación anterior se sobreentiende el orden de las antiimágenes en el conjunto inicial.
Aplicaciones inyectivas
Dada una aplicación f, ésta será inyectiva si dados dos elementos cualesquiera del conjunto inicial, por ejemplo x e y, es f(x)=f(y) si y sólo si x=y. Dicho de otro modo: la antiimagen de cualquier elemento del conjunto final, si existe, debe ser única.
Tomando la notación más abreviada para una aplicación, una forma inmediata de ver si es inyectiva es comprobando que no se repite ninguna imagen. En este sentido, es obvio que la aplicación f={y, z, y, x} del ejemplo anterior no es inyectiva, pues la imagen y está repetida.
El proyecto Correspondencias
En la página de descargas, dentro del apartado Correspondencias y aplicaciones, el lector podrá descargar el proyecto Correspondencias, tanto en su versión en Java como en su versión en C++.
Dada una matriz booleana, como la representada en la tabla 1 anterior, se trata de extraer todas las posibles aplicaciones y aplicaciones inyectivas contenidas en la misma.
Aunque la intención del lector sea usar únicamente la versión en C++, es aconsejable echar antes un vistazo al javadoc de la versión en Java, pues explica claramente la descripción del problema y el uso de las clases implicadas en su resolución.
Es necesario indicar que, dada una matriz booleana, el número de aplicaciones que se pueden extraer de la misma es el producto extendido a todas las columnas del número de valores true en cada columna. Si la matriz es grande, el número de aplicaciones puede llegar a ser inmenso, requiriendo tiempos de computación inadmisibles. Consecuentemente, tenga en cuenta el lector que las clases contenidas en el proyecto Correspondencias están diseñadas para manejar matrices de tamaño pequeño.
Aplicaciones sobreyectivas y aplicaciones biyectivas
Una aplicación es sobreyectiva si todo elemento del conjunto final tiene antiimagen en el conjunto inicial.
Tomando la notación más abreviada para una aplicación, una forma inmediata de ver si es sobreyectiva es comprobando que en ella aparecen, al menos una vez, todos los elementos del conjunto final.
Una aplicación que es a la vez inyectiva y sobreyectiva se dice que es biyectiva.
De nuevo, tomando la notación más abreviada para una aplicación, una forma inmediata de ver si es biyectiva es comprobando que en ella aparecen sin repetirse todos los elementos del conjunto final.
Llegados a este punto es claro que:
- Para que una aplicación entre conjuntos finitos sea biyectiva es condición necesaria que el cardinal de ambos conjuntos sea el mismo.
- Una aplicación biyectiva es siempre una permutación del conjunto final, esto es, la disposición de todos los elementos del conjunto final en un orden u otro.
El proyecto ApplBij
En la página de descargas, dentro del apartado Aplicaciones biyectivas, el lector podrá descargar el proyecto ApplBij, tanto en su versión en Python como en su versión en C++.
Dada una matriz cuadrada y booleana, se trata de extraer al azar una aplicación biyectiva contenida en la misma.
Tanto la descripción del problema como el uso de las clases implicadas en su resolución están suficientemente explicadas en el propio código fuente, ora en la versión en Python, ora en la versión en C++.
El juego del Amigo Invisible
El juego de amigo invisible consiste en una ceremonia de entrega y recepción de regalos dentro de un grupo establecido de personas, de manera que toda persona debe hacer un regalo y recibir otro. La forma como se asignan los regalos, esto es, a quién debe regalar cada persona, se elige previamente mediante un sorteo secreto, de manera que la única información que recibe cada jugador tras el sorteo es a quién debe hacer el regalo, pero carece de información sobre quién regala a quién y quién le hará el regalo a él. La dificultad del juego reside en diseñar el sorteo secreto de manera que se satisfagan las siguientes condiciones:
- Todos los jugadores deben hacer un regalo.
- Todos los jugadores deben recibir un regalo.
- El sorteo debe respetar un conjunto de restricciones previamente acordadas si las hubiera; por ejemplo: se pueden impedir los regalos entre hermanos o dentro de parejas, etc.
Las restricciones se explicitan en una matriz booleana como la que hemos venido usando hasta ahora. Cada columna representa un donante de regalos (del conjunto inicial de donantes de regalos) y cada fila representa un receptor de regalos (del conjunto final del receptores de regalos). Como ambos conjuntos (el de donantes y el de receptores) son en realidad el mismo, la matriz de restricciones será cuadrada.
En su forma más simple (cuando apenas hay restricciones) se permite en el sorteo que una persona pueda hacer un regalo a cualquier otra persona del grupo con la misma probabilidad. En ese caso todos los elementos de la matriz de restricciones tendrán el valor true, salvo los elementos de la diagonal principal, que serán false, pues no está permitido en ningún caso regalarse a sí mismo.
Para extraer una solución válida del sorteo se emplean las clases del proyecto ApplBij. En esencia el método de computación funciona de la siguiente manera:
- Se calcula la densidad de la matriz cuadrada y booleana de restricciones. En este contexto la densidad de la matriz es el cociente entre el número de aplicaciones alojadas en la matriz y el número de permutaciones del conjunto final (receptores de regalos).
- Si la densidad es muy superior a uno significará que la matriz es muy densa, esto es, hay muchos valores true (en comparación con los valores false). En este caso se buscan al azar permutaciones del conjunto final y se finaliza la búsqueda para la primera permutación que sea compatible con la matriz de restricciones.
- Si la densidad es muy inferior a uno significará que la matriz es muy rala, esto es, hay pocos valores true (en comparación con los valores false). En ese caso se extraen al azar aplicaciones de la matriz de restricciones y se finaliza la búsqueda para la primera aplicación que sea biyectiva.
- Si la densidad es cercana a uno podemos tomar cualquiera de los dos caminos anteriores, pero en este caso si la matriz es grande es posible que necesitemos un número muy grande de intentos antes de dar con una solución válida del sorteo (si es que ésta existe). No obstante, y de manera general, en casi todos los sorteos del Amigo Invisible que se celebran la densidad de la matriz de restricciones es muy superior a la unidad.
La metodología anterior se ha empleado en el juego del Amigo Invisible Online, aplicación creada por Bosco Curtu y que goza de merecido prestigio y de gran éxito y en Internet (sobre todo en cuando se acercan las fechas navideñas). A finales de 2008 y a comienzos de 2009 ambos estuvimos trabajando para integrar esta algoritmia en su aplicación web. Más recientemente se ha empleado también en la Applet del Amigo Invisible Familiar, que puede disfrutarse en este mismo sitio web.
