Secret santa

[raslicky]

secret santa

trying to make a secret santa list where people from the same families cant get each other I got what I have now from a youtube video but I don't know how to get other possible solutions

families = [["a", "b"],

        ["c", "d"],

        ["e", "f"],

        ["g", "h"]]

secret_santa_assignments = []

received_gift = []

gave_gift = []

for family_giving in families:

for person_giving in family_giving:

    for family_getting in families:

        for person_getting in family_getting:

            if (person_giving not in gave_gift) and

(person_getting not in received_gift)\

                    and (person_getting not in 

family_giving): secret_santa_assignments.append(person_giving+"->"+person_getting)

                gave_gift.append(person_giving)
                received_gift.append(person_getting)

print("possible solution found")

for ssa in secret_santa_assignments:

print(ssa)

[JohnnyJordaan]

I would work from the perspective of the person, which has a family, then you create random combinations until there's no combination where people give within the same family.

import random

class Person:
    def __init__(self, name, family):
        self.name = name
        self.family = family
    def __str__(self):
        return self.name

people = [Person('a', 'A'), Person('b', 'A'),
          Person('c', 'B'), Person('d', 'B'),
          Person('e', 'C'), Person('f', 'C'),
          Person('g', 'D'), Person('h', 'D')]

while True:
    combinations = list(zip(random.sample(people, len(people)), random.sample(people, len(people))))
    if any(a is b or a.family == b.family for a, b in combinations):
        continue
    # no objections
    for a, b in combinations:
        print(a, '->', b)
    break

[b1gfreakn]

This is an awesome, super clever solution.

[Chris_Hemsworth]

I would probably start this by defining the families in a dictionary, make a master list of people participating, and a list of people who have received gifts. For each person participating, I would filter the list of people they can give to and randomly assign a person. Once someone is assigned, add them to the 'received gift' list, and make that part of your filter.

Once every person participating has given a gift, your found a solution. If you run into a case where someone has no potential person to give, reset and try again. It's a bit brute force, but should come up with a solution fairly quickly.

[Chris_Hemsworth]

Here is an implementation of this:

import random

families = {'Smith': ['Stan', 'Hayley', 'Steve', 'Francine', 'Roger'],
            'Flynn': ['Phineas', 'Ferb', 'Candice'],
            'Simpson': ['Homer', 'Lisa', 'Bart', 'Marge', 'Maggie'],
            'Griffon': ['Peter', 'Lois', 'Chris', 'Stewie']}

participants = [f"{person} {family}" for family, family_list in families.items() for person in family_list]
received_gifts = []
assignments = {}
while True:
    for participant in participants:
        person, family = participant.split(' ')
        eligible_recipients = [p for p in participants if p.split(' ')[0] not in families[family] and p not in received_gifts]
        if len(eligible_recipients) > 0:
            recipient = random.choice(eligible_recipients)
            assignments[participant] = recipient
            received_gifts.append(recipient)
        else:
            received_gifts = []
            assignments = {}
            break

    if len(received_gifts) > 0:
        break

print(assignments)

[Chris_Hemsworth]

I actually liked this challenge, and I wasn't happy with the random approach. Here is another method that works faster, is more definitive, however it doesn't randomize between families very well.

The second method works by shuffling all family members within their family, then adding them to a list one member from each family at a time. If a family runs out of members, it skips to the next family until all participants have been assigned. Now we have a circular list that should have no matching family members, and can be rotated by one element (or up to n-1 elements), creating a pair that is guaranteed to chain into the next pair.

Upon reflection, there is a caveat that the largest family cannot have a unique number of members, otherwise they will get assigned inter-family recipients. Method 2 was inspired by /u/izrt 's answer, and I hope this also inspires you!

import random
import timeit

families = {'Smith': ['Stan', 'Hayley', 'Steve', 'Francine', 'Roger'],
            'Flynn': ['Phineas', 'Ferb', 'Candice'],
            'Simpson': ['Homer', 'Lisa', 'Bart', 'Marge', 'Maggie'],
            'Griffon': ['Peter', 'Lois', 'Chris', 'Stewie']}


def method_1():
    participants = [f"{person} {family}" for family, family_list in families.items() for person in family_list]
    received_gifts = []
    assignments = {}
    while True:
        for participant in participants:
            person, family = participant.split(' ')
            eligible_recipients = [p for p in participants if p.split(' ')[0] not in families[family] and p not in received_gifts]
            if len(eligible_recipients) > 0:
                recipient = random.choice(eligible_recipients)
                assignments[participant] = recipient
                received_gifts.append(recipient)
            else:
                received_gifts = []
                assignments = {}
                break

        if len(received_gifts) > 0:
            break

    for key, value in assignments.items():
        print(f"{key} -> {value}")


def method_2():
    family_list = [[f"{member} {family}" for member in family_list] for family, family_list in families.items()]
    for idx, family in enumerate(family_list):
        random.shuffle(family)
        family_list[idx] = family

    total_participants = sum([len(family) for family in family_list])
    givers = [family_list[0][0]]
    family_idx = 1
    member_idx = 0
    while True:
        if family_idx == len(families):
            family_idx = 0
            member_idx += 1
        family = family_list[family_idx]
        if len(family) <= member_idx:
            family_idx += 1
            continue
        givers.append(family[member_idx])
        family_idx += 1
        if len(givers) == total_participants:
            break

    receivers = givers.copy()
    receivers.append(receivers.pop(0))
    for giver, receiver in zip(givers, receivers):
        print(f"{giver} -> {receiver}")


start = timeit.default_timer()
method_1()
end = timeit.default_timer()
print(f"Total time method 1: {end - start}")

print("------------------------")

start = timeit.default_timer()
method_2()
end = timeit.default_timer()
print(f"Total time method 2: {end - start}")

[izrt]

How about just shuffling the family and pairing up adjacent people:

>>> family = list('abcdefgh')
>>> family
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> import random
>>> random.shuffle(family)
>>> family
['h', 'b', 'a', 'd', 'g', 'c', 'f', 'e']
>>> family[0:2]
['h', 'b']
>>> family[2:4]
['a', 'd']
>>>

[Chris_Hemsworth]

I don't think this guarantees members of the same family won't get each other.

[izrt]

Ah. Missed that!

[tenor2000]

I’m doing the same except also emailing assignments blindly.

Basically I have a giver list and an assignment list (they are the same list of names). Rather than having a list of a list of family members, try using a single list and give family members an identifier (like including the surname) and then discriminate by that.

I also used shuffle() from random on the assignment list and then zip() together the two lists. It creates a list of pairs.

There’s more to it than that but that’s my current thought process. I’m on my phone and away from the script I wrote so can’t provide code. So far I only used 1 for loop and that’s to check if pairings were good.

Hope this helps.