9.11

(a) All 10 team assignments for 6 players A,B,C,D,E,F
1. {A,B,C} | {D,E,F}
2. {A,B,D} | {C,E,F}
3. {A,B,E} | {C,D,F}
4. {A,B,F} | {C,D,E}
5. {A,C,D} | {B,E,F}
6. {A,C,E} | {B,D,F}
7. {A,C,F} | {B,D,E}
8. {A,D,E} | {B,C,F}
9. {A,D,F} | {B,C,E}
10. {A,E,F} | {B,C,D}

(b) Back-tracking algorithm (no repeats)
Idea: always put the first player into the first team; then choose the remaining k-1 teammates in all possible ways.

def generate_teams(players): # players length = 2k, assumed sorted
n = len(players); k = n // 2 # k people per team
first = players[0] # fix first player to avoid duplicates

team = [first] # partial team 1
res = [] # list of (team1, team2)

def backtrack(start):
if len(team) == k: # team1 complete
team1 = set(team)
team2 = set(players) - team1
res.append((sorted(team1), sorted(team2)))
return
for i in range(start, n): # try every possible teammate
team.append(players[i])
backtrack(i + 1)
team.pop()

backtrack(1) # start choosing after 'first'
return res # contains C(n-1,k-1)=10 assignments


Running generate_teams(['A','B','C','D','E','F']) outputs exactly the 10 assignments listed in part (a).
Time complexity: Θ([math]\binom{n-1}{k-1}[/math]) (one visit per valid assignment).
Space complexity: O(k) for the recursion stack plus O([math]\binom{n-1}{k-1}[/math]) if all assignments are stored.

Back to Chapter 9