Como las listas regaladores
y regalados
contienen los mismos elementos he definido una única lista que he llamado participantes
.
Usaremos un diccionario para guardar qué restricciones tenemos.
Tendremos como llaves los nombres de los participantes en el juego y como valores sets de aquellas personas a las que no puede regalar.
Uso sets porque quiero que comprobar la pertenencia a este contenedor sea rápido.
Definamos este diccionario.
Asumo que los individuos contiguos en la lista son parejas que no se pueden regalar entre sí.
Para otro tipo de restricciones podemos definir los sets con otro criterio.
1
def calcular_restricciones(regaladores) -> dict[str, set[str]]:
restricciones = dict()
for marido, mujer in zip(regaladores[0::2], regaladores[1::2]):
restricciones[marido] = {marido, mujer}
restricciones[mujer] = {marido, mujer}
return restricciones
restricciones = calcular_restricciones(participantes)
Al definir de este modo el diccionario siempre puedo añadir más restricciones.
Por ejemplo si pedro
y luis
no se pudieran regalar mutuamente bastaría con hacer restricciones['pedro'].add('luis')
y restricciones['luis'].add('pedro')
.
El resultado del algoritmo lo voy a guardar en un diccionario.
Las llaves serán el nombre del regalador y los valores serán el nombre del regalado.
Definamos la función sorteo
.
La haremos recursivamente.
El caso base es aquel en el que la lista de regaladores está vacía.
Eso significa que todo el mundo entrega regalo.
En caso contrario, tomamos un regalador e iteramos entre aquellas personas que no tienen ningún regalador y que además no están en sus restricciones.
def sorteo(regaladores: list[str], regalados: list[str], resultado: dict[str, str]):
# Caso base, todos los participantes tienen a quién regalar
if not regaladores:
return True
# Vamos a intentar asignar un regalado al primer regalador de la lista
regalador = regaladores[0]
# Lista con las personas que aún no tienen a quién regalar
regaladores_restantes = regaladores[1:]
# Añado aleatoriedad al iterar los posibles regalados
shuffle(regalados)
# Itero todas las personas que aún no tienen quien les regale
for regalado in regalados:
# Si 'regalado' no puede ser regalada por regalador, paso a la siguiente
if regalado in restricciones[regalador]:
continue
# Lista con las personas que aún no tienen quien les regale
regalados_restantes = [i for i in regalados if i != regalado]
# Añado a la solución la asignación actual
resultado[regalador] = regalado
# Recursivamente llamo a la función para saber
# si la asignación me da una situación resoluble
if sorteo(regaladores_restantes, regalados_restantes, resultado):
# La asignación es correcta, salgo de la función
return True
else:
# La asignación no es correcta,
# la elimino e intento asignarle otro regalado
del resultado[regalador]
# Ninguna de las personas que necesitan regalador
# pueden ser regaladas por 'regalador':
# la situación es irresoluble.
return False
Este código tiene margen de optimización.
Pero creo que la versión actual es un buen equilibrio entre eficacia y claridad.
A la hora de llamar a la función es importante notar que shuffle
es un algoritmo in situ (in-place).
Eso significa que el primer argumento y el segundo deben ser objetos distintos.
Si sólo tenemos una lista participantes
, en el segundo caso habrá que pasarla como una copia:
resultado: dict[str, str] = dict()
sorteo(participantes, participantes.copy(), resultado)
print(resultado)
1 A partir de Python 3.12 ese mismo bucle se puede escribir usando itertools.batched
.