Find all the pairs in a list with conditions Python

Question

I have a real life problem that I want to solve using Python. I have a team of x=10 people (myself included) and during n-1=9 weeks we want to schedule a 1-on-1 call each week such that everyone gets a call with everyone and no pair of people talk twice during the 9 weeks.

This is my solution but it is flawed because, although everyone speaks with everyone, each person has two calls per week and I want just 1 call per week.

Any idea of how could I solve this?

#for shifting a list to the left with n positions
def rotate(l, n):
    return l[n:] + l[:n]

def generate_1on1_meetings(members):
    random.shuffle(members)
    n = len(members)
    for i in range(0, int(n / 2)):
        print("WEEK " + str(i + 1) + "\n")
        aux = rotate(members, i + 1)
        for j in range(0, n):
            print(members[j] + " - " + aux[j])
        print("\n")

EDIT: So to make things more clear, there should be an even number (2k) of persons. In each week there will be k meetings, each person appearing just in one meeting, and in each week everyone will have participated in exactly one meeting. There need to be 2k-1 weeks to have all the meetings.

Example: so let's consider the case of 4 team members: [A, B, C, D]. A solution given my constraints would be:

Week 1:AB,CD

Week 2: AC, BD

Week 3: AD, BC

So each person had just one meeting per week, all of them appeared in just 1 meeting in each week and after the 4-1 weeks passed everyone had a meeting with everyone

Answer 1

Lets arrange the pairs first. Then schedule the meetings.

Decomposed

1. combinations: using itertools.combinations

   Example: a team of 3 persons has 3 combinations/pairs, a team of 4 has 6

to schedule meetings for 6 pairs:

2. schedule variant A: one meeting per week

   Example: for 6 pairs we need 6 weeks, for 3 we need 3 weeks

3. schedule variant B: one meeting per week per person

   Example: for 6 pairs we need 3 weeks, for 3 we need 3

Code

1. combinations:

import itertools

def arrange_pairs(members):
    # 1:1 combinations, return a list of tuples (1:1 pair)
    return list(itertools.combinations(members,2))  # combine pairs (r=2) of members

members = [1,2,3,4]  # given 4 team-members, simplified as numerical ID
print(f"members: {len(members)}")
pairs = arrange_pairs(members)
print(f"pairs: {len(pairs)}")

Prints:

members: 4
pairs: 6

See also: How to get all possible combinations of a list’s elements?

2. schedule variant A

def schedule_meetings(pairs):
    # 1 meeting per week, return a list of meeting-descriptions as string
    scheduled = []
    cw = 1  # calendar week or just a counter
    for pair in pairs:
        scheduled.append(f"week {cw:2}: {pair}")
        cw = cw + 1
    return scheduled


meetings = schedule_meetings(pairs)
print(f"meetings: {len(meetings)}")
print(*meetings, sep='\n')

Prints:

meetings: 6
week  1: (1, 2)
week  2: (1, 3)
week  3: (1, 4)
week  4: (2, 3)
week  5: (2, 4)
week  6: (3, 4)

3. schedule variant B

def schedule_meetings(pairs, cw = 1):
    # 1 meeting per person per week, return a list of meeting-descriptions as string
    pair = pairs[0]
    scheduled = {cw: [pair]}
    pairs_unmet = set(pairs) - {pair}

    person_met_already = lambda p: p[0] == pair[0] or p[0] == pair[1] or p[1] == pair[0] or p[1] == pair[1]
    pairs_already = set(filter(person_met_already, pairs_unmet))

    for unmet_pair in pairs_unmet - pairs_already:
        scheduled[cw].append(unmet_pair)
    if pairs_already:
        scheduled.update(schedule_meetings(list(pairs_already), cw+1))

    return scheduled


members = [1,2,3,4]  # given 4 team-members, simplified as numerical ID
print(f"members: {len(members)}")
pairs = arrange_pairs(members)
print(f"pairs: {len(pairs)}\t{pairs}")
meetings = schedule_meetings(pairs)
print(f"weeks: {len(meetings)}, meetings: {sum(len(l) for l in meetings.values())}")
for cw, pairs in meetings.items():
    print(f"Week {cw:2}: {pairs}")

members = [1,2,3]  # odd count of memebrs
print(f"members: {len(members)}")
pairs = arrange_pairs(members)
print(f"pairs: {len(pairs)}\t{pairs}")
meetings = schedule_meetings(pairs)
print(f"weeks: {len(meetings)}, meetings: {sum(len(l) for l in meetings.values())}")
for cw, pairs in meetings.items():
    print(f"Week {cw:2}: {pairs}")

Prints:

members: 4
pairs: 6    [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
weeks: 3, meetings: 6
Week  1: [(1, 2), (3, 4)]
Week  2: [(1, 3), (2, 4)]
Week  3: [(2, 3), (1, 4)]
members: 3
pairs: 3    [(1, 2), (1, 3), (2, 3)]
weeks: 3, meetings: 3
Week  1: [(1, 2)]
Week  2: [(1, 3)]
Week  3: [(2, 3)]

See also

• Similar question: Round-robin pairing while referencing previous pairings in Python
• Wikipedia: Round-robin tournament

Answer 2

You could use the round-robin (polygon) algorithm:

Here's an example of the algorithm in Python (works for even and odd number of teams/people):

def roundRobin(people):
    P = people+len(people)%2*[None]
    for _ in range(len(people)-1):
        yield [(P[i],P[-1-i]) for i in range(len(P)//2)]
        P.append(P.pop(1))

output:

# Even number of people (10)

for calls in roundRobin(["A","B","C","D","E","F","G","H","I","J"]):
    print(calls) 

[('A', 'J'), ('B', 'I'), ('C', 'H'), ('D', 'G'), ('E', 'F')]
[('A', 'B'), ('C', 'J'), ('D', 'I'), ('E', 'H'), ('F', 'G')]
[('A', 'C'), ('D', 'B'), ('E', 'J'), ('F', 'I'), ('G', 'H')]
[('A', 'D'), ('E', 'C'), ('F', 'B'), ('G', 'J'), ('H', 'I')]
[('A', 'E'), ('F', 'D'), ('G', 'C'), ('H', 'B'), ('I', 'J')]
[('A', 'F'), ('G', 'E'), ('H', 'D'), ('I', 'C'), ('J', 'B')]
[('A', 'G'), ('H', 'F'), ('I', 'E'), ('J', 'D'), ('B', 'C')]
[('A', 'H'), ('I', 'G'), ('J', 'F'), ('B', 'E'), ('C', 'D')]
[('A', 'I'), ('J', 'H'), ('B', 'G'), ('C', 'F'), ('D', 'E')]


# Odd number of people (7) 

for calls in roundRobin(["A","B","C","D","E","F","G"]):
    print(calls)

[('A', None), ('B', 'G'), ('C', 'F'), ('D', 'E')] no call for A
[('A', 'B'), ('C', None), ('D', 'G'), ('E', 'F')] no call for C
[('A', 'C'), ('D', 'B'), ('E', None), ('F', 'G')] no call for E
[('A', 'D'), ('E', 'C'), ('F', 'B'), ('G', None)] no call for G
[('A', 'E'), ('F', 'D'), ('G', 'C'), (None, 'B')] no call for B
[('A', 'F'), ('G', 'E'), (None, 'D'), ('B', 'C')] no call for D