I have the following Python brainteaser: We arrange a 30-day programme with 48 participants. Every day in the programme, participants are paired in twos. Participants cannot have the same partners twice and all participants have to be partnered up every day. P.S. I hope my math is right in the title.
I've managed an implementation but it feels very clunky. Is there an efficient way to do this? Perhaps using the cartesian product somehow? All feedback and tips are much appreciated.
# list of people: 48
# list of days: 30
# each day, the people need to be split into pairs of two.
# the same pair cannot occur twice
import random
from collections import Counter
class person ():
def __init__ (self, id):
self.id = id
class schedule ():
def __init__ (self, days):
self.people_list = []
self.days = days
self.placed_people = []
self.sets = []
def create_people_list(self, rangex):
for id in range(rangex):
new_person = person(id)
self.people_list.append(new_person)
print(f"{len(self.people_list)} people and {self.days} days will be considered.")
def assign_pairs(self):
for day in range(self.days): # for each of the 30 days..
print("-" * 80)
print(f"DAY {day + 1}")
self.placed_people = [] # we set a new list to contain ids of placed people
while Counter([pers.id for pers in self.people_list]) != Counter(self.placed_people):
pool = list( set([pers.id for pers in self.people_list]) - set(self.placed_people))
# print(pool)
person_id = random.choice(pool) # pick random person
person2_id = random.choice(pool) # pick random person
if person_id == person2_id: continue
if not set([person_id, person2_id]) in self.sets or len(pool) == 2:
if len(pool) == 2: person_id, person2_id = pool[0], pool[1]
self.sets.append(set([person_id, person2_id]) )
self.placed_people.append(person_id)
self.placed_people.append(person2_id)
print(f"{person_id} {person2_id}, ", end="")
schdl = schedule(30) # initiate schedule with 30 days
schdl.create_people_list(48)
schdl.assign_pairs()
Outputs:
48 people and 30 days will be considered.
--------------------------------------------------------------------------------
DAY 1
37 40, 34 4, 1 46, 13 39, 12 35, 18 33, 25 24, 23 31, 17 42, 32 19, 36 0, 11 9, 7 45, 10 21, 44 43, 29 41, 38 16, 15 22, 2 20, 26 47, 30 28, 3 8, 6 27, 5 14,
--------------------------------------------------------------------------------
DAY 2
42 28, 25 15, 6 17, 2 14, 7 40, 11 4, 22 37, 33 20, 0 16, 3 39, 19 47, 46 24, 12 27, 26 1, 34 10, 45 8, 23 13, 32 41, 9 29, 44 31, 30 5, 38 18, 43 21, 35 36,
--------------------------------------------------------------------------------
DAY 3
8 28, 33 12, 40 26, 5 35, 13 31, 29 43, 44 21, 11 30, 1 7, 34 2, 47 45, 46 17, 4 23, 32 15, 14 22, 36 42, 16 41, 37 19, 38 3, 20 6, 10 0, 24 9, 27 25, 18 39,
--------------------------------------------------------------------------------
[...]
--------------------------------------------------------------------------------
DAY 29
4 18, 38 28, 24 22, 23 33, 9 41, 40 20, 26 39, 2 42, 15 10, 12 21, 11 45, 46 7, 35 27, 29 36, 3 31, 19 6, 47 32, 25 43, 13 44, 1 37, 14 0, 16 17, 30 34, 8 5,
--------------------------------------------------------------------------------
DAY 30
17 31, 25 7, 6 10, 35 9, 41 4, 16 40, 47 43, 39 36, 19 44, 23 11, 13 29, 21 46, 32 34, 12 5, 26 14, 15 0, 28 24, 2 37, 8 22, 27 38, 45 18, 3 20, 1 33, 42 30,
Thanks for your time! Also, a follow up question: How can I calculate whether it is possible to solve the task, i.e. to arrange all the participants in unique pairs every day?
Round-robin tournaments are extremely easy to organize. In fact, the algorithm is so simple that you can organize a round-robin tournament between humans without any paper or computer, just by giving the humans simple instructions.
You have an even number N = 48 humans to pair up. Imagine you have a long table with N // 2 seats on one side, facing N // 2 seats on the other side. Ask all the humans to seat at that table.
This is your first pairing.
Call one of the seats "seat number 1".
To move to the next pairing: the human at seat number 1 doesn't move. Every other human moves clockwise one seat around the table.
Current pairing
1 2 3 4
8 7 6 5
Next pairing
1 8 2 3
7 6 5 4
# a table is a simple list of humans
def next_table(table):
return [table[0]] + [table[-1]] + table[1:-1]
# [0 1 2 3 4 5 6 7] -> [0 7 1 2 3 4 5 6]
# a pairing is a list of pairs of humans
def pairing_from_table(table):
return list(zip(table[:len(table)//2], table[-1:len(table)//2-1:-1]))
# [0 1 2 3 4 5 6 7] -> [(0,7), (1,6), (2,5), (3,4)]
# a human is an int
def get_programme(programme_length, number_participants):
table = list(range(number_participants))
pairing_list = []
for day in range(programme_length):
pairing_list.append(pairing_from_table(table))
table = next_table(table)
return pairing_list
print(get_programme(3, 8))
# [[(0, 7), (1, 6), (2, 5), (3, 4)],
# [(0, 6), (7, 5), (1, 4), (2, 3)],
# [(0, 5), (6, 4), (7, 3), (1, 2)]]
print(get_programme(30, 48))
If you want the humans to be custom objects instead of ints, you can replace the second argument number_participants by the list table directly; then the user can supply a list of whatever they want:
def get_programme(programme_length, table):
pairing_list = []
for day in range(programme_length):
pairing_list.append(pairing_from_table(table))
table = next_table(table)
return pairing_list
print(get_programme(3, ['Alice', 'Boubakar', 'Chen', 'Damian']))
# [[('Alice', 'Damian'), ('Boubakar', 'Chen')],
# [('Alice', 'Chen'), ('Damian', 'Boubakar')],
# [('Alice', 'Boubakar'), ('Chen', 'Damian')]]
If there are N humans, each human can be paired with N-1 different humans. If N is even, then the round-robin circle-method will make sure that the first N-1 rounds are correct. After that, the algorithm is periodic: the Nth round will be identical to the first round.
Thus there is a solution if and only if programme_length < number_participants and the number of participants is even; and the round-robin algorithm will find a solution in that case.
If the number of participants is odd, then every day of the programme, there must be at least one human who is not paired. The round-robin tournament can still be applied in this case: add one extra "dummy" human (usually called bye-player). The dummy human behaves exactly like a normal human for the purposes of the algorithm. Every round, one different real human will be paired with the dummy human, meaning they are not paired with a real human this round. With this method, all you need is programme_length <= number_participants.