My family does “one big gift” every Christmas; that is instead of everyone simply buying everyone else a smaller gift; every person is assigned to one other person to give them a single large gift. Selection of who gives what to who is a place of some (minor) conflict. Therefore we simply use a random algorithm. Unfortunately, apparently a uniform random sample of pairs is not enough, therefore we take 100 samples to vote for each combination to see who gets what as follows:

from random import shuffle
from collections import Counter
from itertools import combinations
from collections import defaultdict


def random_combinations(items, iterations=100):
    """
    Randomly combines items until a group reaches the minimum number
    of votes. This function will yield both the item voted for and
    the # of votes.
    """

    votes   = defaultdict(Counter)
    giftees = set([])

    for idx in xrange(iterations):
        shuffle(items)
        for (giver, giftee) in combinations(items, 2):
            votes[giver][giftee] += 1

    combos  = []
    for giver, votes in votes.iteritems():
        for giftee, vote in votes.most_common():
            if giftee not in giftees:
                combos.append((giver, giftee, vote))
                giftees.add(giftee)
                break

    if len(combos) != len(items):
        return random_combinations(items, iterations)

    return combos


def read_names(path):
    """
    Reads the names from the associated text file (newline
    delimited). There must be an even number of names otherwise
    this won't work very well.
    """
    with open(path, 'r') as f:
        return [
            name.strip() for name in f if name.strip()
        ]


if __name__ == '__main__':
    # Print the names and the votes!
    for data in random_combinations(read_names('names.txt')):
        print "{} --> {} ({} votes)".format(*data)

Follow Ups

  • The (secret) Gist contains all the code including the data file.
  • Need to implement a method that does not allow for repeat giftee pairs.