0

estoy desarrollando con python la lógica necesaria para sortear el amigo invisible y me gustaria hacer algo asi:

Imaginemos 3 participantes:

  • pepe
  • martin
  • antonio

Primer Caso

Ahora con estos 3 participantes digamos que no queremos que a pepe le toque martin es decir agregamos una exclusion pepe para que no le toque martin.

  • pepe exclusiones [2]
  • martin
  • antonio

PD: Esto no significa que martin no le regale a pepe. Pepe NO le regalara a martin pero martin SI puede regalar a pepe. IMPORTANTE que en este caso concreto a pepe le toque regalar a antonio, porque si a martin le toca regalar a antonio pepe se va a quedar sin regalarle a nadie

Segundo caso

Tambien el programa tendra que tener en cuenta que las exclusiones no sea abusivas, por ejemplo esto no funcionaria porque 2 personas no pueden regalarle a una sola ya que va a haber 1 a quien no le va a regalar nadie

  • pepe exclusiones [2]
  • martin exclusiones [1]
  • antonio exclusiones [1]

Pruebas

De momento llevo algo como esto pero falla en el primer caso diciendo que las exclusiones son abusivas sin llegar a serlo

class Persona:
    def __init__(self, nombre, exclusiones=None):
        self.nombre = nombre
        self.exclusiones = exclusiones if exclusiones is not None else []

def sorteo_amigo_invisible(personas):
    if len(personas) < 3:
        print("Error: Debe haber al menos 3 personas para realizar el sorteo.")
        return
    
    personas_disponibles = personas.copy()
    
    asignaciones = {}
    
    for persona in personas:
        personas_disponibles_para_asignar = [p for p in personas_disponibles if p.nombre != persona.nombre and p.nombre not in persona.exclusiones]
        
        if not personas_disponibles_para_asignar:
            print("Error: No se puede realizar el sorteo debido a exclusiones demasiado restrictivas.")
            return
        
        amigo_invisible = random.choice(personas_disponibles_para_asignar)
        
        asignaciones[persona.nombre] = amigo_invisible.nombre
        
        personas_disponibles.remove(amigo_invisible)
    
    for persona, amigo in asignaciones.items():
        print(f"{persona} le ha tocado regalar a {amigo}.")

personas = [
    Persona("Juan", [2]),
    Persona("María", []),
    Persona("Pedro"),
    Persona("Ana", [3]),
    Persona("Luis")
]

sorteo_amigo_invisible(personas)
7
  • 1
    En todos los casos debes tratar de evitar las relaciones circulares o mutuas: (A -> B) y (B -> A). La cantidad de emparejamientos será igual a la cantidad de personas, entonces, si la cantidad de personas es impar no puede haber cantidad de relaciones mútuas - 1, ya que siempre quedará uno solo. Si la cantidad es par no habrá ese problema pero será poco atractivo el juego.
    – aeportugal
    Commented el 8 may. a las 7:22
  • Entiendo, y de hecho lo estuve probando antes de llegar a esta logica, y claro el problema es que en ocasiones el resultado es algo como: A -> C C -> B B -> A
    – Anthonyx82
    Commented el 8 may. a las 7:30
  • 1
    @Anthonyx82 Acaso no es A -> C C -> B B -> A el único resultado válido para tres personas?? De cualquier otra manera estarías teniendo a una persona autoregalándose. Por cierto, si el valor por defecto de exclusiones es [] puedes ahorrarte el ternario comprobando si es None, directamente lo asignas.
    – Benito-B
    Commented el 8 may. a las 8:39
  • 1
    Este problema se puede resolver con backtracking, la forma más sencilla es utilizando un while y una pila
    – Yussef
    Commented el 8 may. a las 10:06
  • @Yussef si estoy buscando información sobre ello veremos si consigo hacerlo, muchas gracias
    – Anthonyx82
    Commented el 8 may. a las 10:28

1 respuesta 1

0

Finalmente llegue a este codigo, lo se es extremadamente complejo y hay partes que yo ni siguiera recuerdo, pero por si a alguien pueda ayudarle

def generar_combinaciones(participantes, exclusiones, asignaciones=[], index=0):
    if index == len(participantes):
        yield asignaciones[:]
        return
    
    participante_actual = participantes[index]
    for posible_asignacion in participantes:
        if (posible_asignacion != participante_actual and
                (not exclusiones.get(participante_actual) or posible_asignacion not in exclusiones[participante_actual])):
            asignaciones.append((participante_actual, posible_asignacion))
            yield from generar_combinaciones(participantes, exclusiones, asignaciones, index + 1)
            asignaciones.pop()


def validar_combinaciones(combinaciones):
    for asignacion in combinaciones:
        regalados = {x[1] for x in asignacion}
        if len(regalados) != len(asignacion):
            return False
    return True


def sorteo_amigo_invisible(participantes, exclusiones):
    combinaciones = generar_combinaciones(participantes, exclusiones)
    for combinacion in combinaciones:
        if validar_combinaciones(combinacion):
            yield combinacion


# Ejemplo de uso
participantes = ["pepe", "martin", "antonio", "fran" ]
exclusiones = {
    "pepe": ["martin", "antonio"],
    "martin": [],
    "antonio": [],
    "fran": []
}

for resultado in sorteo_amigo_invisible(participantes, exclusiones):
    print(resultado)

Basicamente el codigo genera todas las posibles combinaciones y de hay puedes escojer una de ellas de forma aleatoria

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.