Skip to content

Instantly share code, notes, and snippets.

@jmhobbs

jmhobbs/brute_force_gift_exchange.py

Last active January 1, 2016 11:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jmhobbs/8141458 to your computer and use it in GitHub Desktop.
Save jmhobbs/8141458 to your computer and use it in GitHub Desktop.
Download ZIP
Problem: There are six cousins, three sets of siblings. They are drawing for a gift exchange, and none of them can get their sibling. How many combinations are possible. Math is hard, so I wrote a brute force, which I think is correct. This could be more generic. The nested loops are gross.
Raw
brute_force_gift_exchange.py
siblings = {1: 2, 2: 1, 3: 4, 4: 3, 5: 6, 6: 5}
cousins = set(siblings.keys())
# Start by getting all the possible pairings for each person.
possible_pairings = {1: set(), 2: set(), 3: set(), 4: set(), 5: set(), 6: set()}
for i in cousins:
for j in cousins - set((i, siblings[i])):
possible_pairings[i].add(j)
combinations = []
# Now, loop through each possible pairing, for each possible person,
# excluding people that have already been drawn.
for one in possible_pairings[1]:
combination = [(1, one)]
for two in possible_pairings[2]:
if two == one:
continue
combination.append((2, two))
for three in possible_pairings[3]:
if three in (two, one):
continue
combination.append((3, three))
for four in possible_pairings[4]:
if four in (three, two, one):
continue
combination.append((4, four))
for five in possible_pairings[5]:
if five in (four, three, two, one):
continue
combination.append((5, five))
for six in possible_pairings[6]:
if six in (five, four, three, two, one):
continue
combination.append((6, six))
# if we have gotten here, than everyone has a legal gift recipient
# and each person is only a recipient once. That makes this a legal
# combination.
combinations.append(tuple(combination))
# We pop the combination after their loop so that they aren't on the
# stack when we compare it on the next iteration.
combination.pop()
combination.pop()
combination.pop()
combination.pop()
combination.pop()
combination.pop()
# Let's make extra sure they are all unique.
combinations = set(combinations)
print 'Found %d Combinations' % len(combinations)
for combination in combinations:
print ' '.join(['%d => %d' % pair for pair in combination])
# Let's make sure they are all legit!
for combination in combinations:
used = set()
for pair in combination:
if pair[1] in used: # Can't already have been taken.
print 'BAD', combination
break
if pair[1] == pair[0]: # Can't be yourself.
print 'BAD', combination
break
if pair[1] == siblings[pair[0]]: # Can't be your sibling.
print 'BAD', combination
break
used.add(pair[1])
Raw
output.log
jmhobbs@Cordelia:~/Desktop ✪ python brute_force_gift_exchange.py
Found 80 Combinations
1 => 4 2 => 6 3 => 2 4 => 5 5 => 1 6 => 3
1 => 6 2 => 5 3 => 1 4 => 2 5 => 4 6 => 3
1 => 6 2 => 4 3 => 5 4 => 2 5 => 1 6 => 3
1 => 4 2 => 6 3 => 5 4 => 1 5 => 3 6 => 2
1 => 3 2 => 6 3 => 5 4 => 1 5 => 2 6 => 4
1 => 4 2 => 3 3 => 5 4 => 6 5 => 2 6 => 1
1 => 5 2 => 3 3 => 6 4 => 1 5 => 2 6 => 4
1 => 4 2 => 5 3 => 6 4 => 1 5 => 3 6 => 2
1 => 5 2 => 6 3 => 2 4 => 1 5 => 4 6 => 3
1 => 3 2 => 5 3 => 2 4 => 6 5 => 1 6 => 4
1 => 3 2 => 5 3 => 1 4 => 6 5 => 4 6 => 2
1 => 5 2 => 3 3 => 2 4 => 6 5 => 1 6 => 4
1 => 3 2 => 5 3 => 1 4 => 6 5 => 2 6 => 4
1 => 6 2 => 3 3 => 5 4 => 1 5 => 2 6 => 4
1 => 3 2 => 4 3 => 5 4 => 6 5 => 1 6 => 2
1 => 5 2 => 4 3 => 1 4 => 6 5 => 2 6 => 3
1 => 5 2 => 4 3 => 6 4 => 1 5 => 3 6 => 2
1 => 4 2 => 6 3 => 5 4 => 2 5 => 3 6 => 1
1 => 3 2 => 5 3 => 6 4 => 2 5 => 1 6 => 4
1 => 4 2 => 3 3 => 6 4 => 5 5 => 1 6 => 2
1 => 3 2 => 6 3 => 2 4 => 5 5 => 1 6 => 4
1 => 4 2 => 6 3 => 2 4 => 5 5 => 3 6 => 1
1 => 6 2 => 4 3 => 5 4 => 1 5 => 3 6 => 2
1 => 4 2 => 6 3 => 1 4 => 5 5 => 2 6 => 3
1 => 4 2 => 5 3 => 6 4 => 2 5 => 1 6 => 3
1 => 6 2 => 5 3 => 2 4 => 1 5 => 3 6 => 4
1 => 6 2 => 4 3 => 1 4 => 5 5 => 3 6 => 2
1 => 6 2 => 5 3 => 1 4 => 2 5 => 3 6 => 4
1 => 6 2 => 3 3 => 1 4 => 5 5 => 4 6 => 2
1 => 6 2 => 4 3 => 5 4 => 1 5 => 2 6 => 3
1 => 5 2 => 3 3 => 6 4 => 1 5 => 4 6 => 2
1 => 6 2 => 3 3 => 2 4 => 5 5 => 4 6 => 1
1 => 4 2 => 6 3 => 1 4 => 5 5 => 3 6 => 2
1 => 4 2 => 5 3 => 6 4 => 1 5 => 2 6 => 3
1 => 6 2 => 3 3 => 5 4 => 2 5 => 1 6 => 4
1 => 6 2 => 3 3 => 1 4 => 5 5 => 2 6 => 4
1 => 3 2 => 5 3 => 6 4 => 2 5 => 4 6 => 1
1 => 3 2 => 6 3 => 1 4 => 5 5 => 2 6 => 4
1 => 3 2 => 5 3 => 6 4 => 1 5 => 4 6 => 2
1 => 5 2 => 4 3 => 2 4 => 6 5 => 3 6 => 1
1 => 5 2 => 4 3 => 6 4 => 1 5 => 2 6 => 3
1 => 3 2 => 5 3 => 6 4 => 1 5 => 2 6 => 4
1 => 6 2 => 3 3 => 2 4 => 5 5 => 1 6 => 4
1 => 3 2 => 4 3 => 6 4 => 5 5 => 1 6 => 2
1 => 5 2 => 3 3 => 2 4 => 6 5 => 4 6 => 1
1 => 4 2 => 5 3 => 1 4 => 6 5 => 2 6 => 3
1 => 6 2 => 3 3 => 5 4 => 2 5 => 4 6 => 1
1 => 3 2 => 5 3 => 2 4 => 6 5 => 4 6 => 1
1 => 6 2 => 3 3 => 5 4 => 1 5 => 4 6 => 2
1 => 3 2 => 6 3 => 5 4 => 2 5 => 4 6 => 1
1 => 3 2 => 6 3 => 5 4 => 2 5 => 1 6 => 4
1 => 5 2 => 3 3 => 1 4 => 6 5 => 4 6 => 2
1 => 4 2 => 6 3 => 5 4 => 2 5 => 1 6 => 3
1 => 5 2 => 6 3 => 2 4 => 1 5 => 3 6 => 4
1 => 5 2 => 4 3 => 6 4 => 2 5 => 3 6 => 1
1 => 4 2 => 5 3 => 1 4 => 6 5 => 3 6 => 2
1 => 3 2 => 4 3 => 5 4 => 6 5 => 2 6 => 1
1 => 5 2 => 6 3 => 1 4 => 2 5 => 3 6 => 4
1 => 3 2 => 4 3 => 6 4 => 5 5 => 2 6 => 1
1 => 4 2 => 5 3 => 2 4 => 6 5 => 1 6 => 3
1 => 6 2 => 4 3 => 5 4 => 2 5 => 3 6 => 1
1 => 3 2 => 6 3 => 5 4 => 1 5 => 4 6 => 2
1 => 5 2 => 4 3 => 1 4 => 6 5 => 3 6 => 2
1 => 5 2 => 3 3 => 6 4 => 2 5 => 4 6 => 1
1 => 4 2 => 3 3 => 6 4 => 5 5 => 2 6 => 1
1 => 5 2 => 3 3 => 1 4 => 6 5 => 2 6 => 4
1 => 6 2 => 4 3 => 1 4 => 5 5 => 2 6 => 3
1 => 6 2 => 5 3 => 2 4 => 1 5 => 4 6 => 3
1 => 4 2 => 5 3 => 6 4 => 2 5 => 3 6 => 1
1 => 5 2 => 3 3 => 6 4 => 2 5 => 1 6 => 4
1 => 5 2 => 4 3 => 6 4 => 2 5 => 1 6 => 3
1 => 6 2 => 4 3 => 2 4 => 5 5 => 3 6 => 1
1 => 3 2 => 6 3 => 1 4 => 5 5 => 4 6 => 2
1 => 4 2 => 6 3 => 5 4 => 1 5 => 2 6 => 3
1 => 4 2 => 5 3 => 2 4 => 6 5 => 3 6 => 1
1 => 6 2 => 4 3 => 2 4 => 5 5 => 1 6 => 3
1 => 5 2 => 4 3 => 2 4 => 6 5 => 1 6 => 3
1 => 4 2 => 3 3 => 5 4 => 6 5 => 1 6 => 2
1 => 5 2 => 6 3 => 1 4 => 2 5 => 4 6 => 3
1 => 3 2 => 6 3 => 2 4 => 5 5 => 4 6 => 1
jmhobbs@Cordelia:~/Desktop ✪
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment