How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)?

Question

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)?

I'm starting with a class of a given size and a group of a giving size, and trying to create a set of groupings such that the groups are unique in each grouping.

For example, if I had a class of 6 and a group size of 2, I'd want the pairings to be:

1: [A,B] [C,D] [E,F]
2: [A,C] [B,E] [D,F]
3: [A,D] [B,F] [C,E]
4: [A,E] [B,D] [C,F]
5: [A,F] [B,C],[D,E]

I can do this by hand for a group this small, but as the size increases even a little bit, it gets daunting. Its easy to find algorithms (they're even built into python itertools) for generating all permutations and combinations, but my goal is to eliminate huge numbers of those combinations, as I'm trying to generate a set of pairings in which there are no repeats (i.e. once "A,B" appears once, it should never appear again).

Here's a start at an attempt at a larger class (10 students):

[A,B] [C,D] [E,F] [G,H] [I,J]
[A,C] [B,D] [E,G] [F,I] [H,J]
[A,D] [B,C] [E,H] [F,J] [G,I]
[A,E] [B,F] [C,G] [D,J] [H,I]
...

It starts to get tricky to generate the combinations following the rule. I've made some starts at code to generate these combinations, but it gets thorny and inefficient with lots of backing out when you realize you've backed yourself into a corner. Anyone have a suggestion for a simpler approach?

The best solution I have so far is to generate all permutations and then weed out the duplicates, but that seems quite inefficient, especially given that the number of permutations scales as a factorial but the number of sets I'm generating should grow linearly.

Answer 1

The annealing approach was a bit over my head, but I was able to come up with a solution that seems to work well for the numbers I'm working with and that may be within reach of others who find this post.

The key was to use a random shuffle of the list rather than trying to walk through the permutations systematically, which becomes impossible for numbers as big as a typical class.

Here's the basic idea:

• Treat your students as a deck of cards that gets dealt into pairs
• Keep track of pairs that have been used so we don't repeat them.
• Randomly shuffle the deck and cut the deck into pairs
• Check if any of the pairs in that shuffle have already been used
• If they have, reject the shuffle
• If they haven't, keep the pairings and add them to the list of pairs not to repeat.

I ran this with a deck of 26 being shuffled and was able to generate 19 pairs in a few minutes. Here's the output, with the number of iterations the loop has been through printed for good measure:

Iterations: 1

Set 0 : [(15, 24), (25, 7), (22, 12), (0, 3), (14, 13), (20, 23), (8, 18), (19, 6), (9, 5), (17, 2), (21, 16), (10, 11), (1, 4)]

Iterations: 2

Set 1 : [(0, 2), (25, 3), (20, 15), (7, 11), (5, 10), (17, 16), (4, 23), (24, 8), (6, 9), (1, 13), (22, 14), (12, 21), (19, 18)]

Iterations: 4

Set 2 : [(8, 0), (14, 19), (17, 1), (7, 3), (15, 11), (10, 21), (9, 18), (4, 12), (23, 5), (24, 2), (22, 6), (13, 20), (16, 25)]

Iterations: 8

Set 3 : [(3, 24), (15, 6), (16, 1), (22, 20), (25, 21), (10, 18), (19, 5), (17, 14), (7, 23), (13, 4), (0, 11), (9, 2), (12, 8)]

Iterations: 9

Set 4 : [(18, 21), (11, 22), (20, 16), (23, 2), (7, 10), (24, 0), (4, 9), (17, 25), (19, 8), (12, 3), (15, 5), (6, 13), (1, 14)]

Iterations: 23

Set 5 : [(1, 7), (20, 3), (8, 22), (23, 0), (15, 21), (14, 6), (18, 5), (9, 25), (19, 13), (12, 17), (16, 4), (24, 11), (10, 2)]

Iterations: 32

Set 6 : [(20, 2), (1, 12), (19, 25), (18, 3), (24, 7), (5, 6), (11, 4), (8, 16), (9, 22), (13, 21), (0, 17), (10, 14), (23, 15)]

Iterations: 66

Set 7 : [(1, 6), (25, 2), (15, 3), (24, 9), (10, 4), (18, 13), (14, 23), (8, 5), (11, 21), (16, 19), (17, 20), (22, 7), (0, 12)]

Iterations: 88

Set 8 : [(25, 5), (21, 14), (10, 24), (17, 9), (1, 23), (8, 13), (0, 4), (18, 22), (12, 15), (6, 3), (20, 19), (16, 11), (2, 7)]

Iterations: 469

Set 9 : [(19, 22), (5, 16), (17, 13), (6, 2), (15, 9), (20, 0), (11, 14), (3, 23), (21, 24), (18, 25), (12, 7), (1, 10), (4, 8)]

Iterations: 877

Set 10 : [(8, 9), (16, 3), (2, 11), (17, 23), (7, 4), (14, 15), (12, 10), (20, 24), (21, 19), (6, 18), (22, 25), (1, 0), (13, 5)]

Iterations: 1363

Set 11 : [(20, 5), (6, 12), (16, 18), (9, 14), (0, 19), (1, 2), (17, 10), (13, 22), (25, 15), (3, 11), (4, 24), (7, 8), (21, 23)]

Iterations: 7435

Set 12 : [(18, 12), (11, 13), (9, 16), (5, 4), (8, 6), (25, 20), (14, 7), (19, 24), (10, 0), (17, 21), (15, 1), (3, 2), (22, 23)]

Iterations: 12008

Set 13 : [(4, 25), (5, 14), (12, 2), (19, 3), (18, 17), (23, 10), (1, 24), (15, 16), (20, 8), (21, 7), (13, 9), (6, 11), (22, 0)]

Iterations: 23082

Set 14 : [(14, 25), (6, 7), (5, 1), (18, 0), (22, 24), (19, 2), (23, 16), (11, 20), (21, 4), (12, 9), (13, 15), (17, 8), (10, 3)]

Iterations: 24293

Set 15 : [(22, 1), (6, 4), (16, 14), (15, 10), (7, 17), (24, 23), (2, 18), (25, 8), (11, 19), (21, 20), (0, 13), (3, 9), (5, 12)]

Iterations: 218369

Set 16 : [(12, 11), (9, 7), (4, 18), (10, 16), (5, 2), (24, 13), (19, 17), (23, 8), (14, 20), (6, 21), (15, 22), (0, 25), (1, 3)]

Iterations: 1080700

Set 17 : [(11, 9), (16, 6), (13, 7), (15, 17), (0, 21), (10, 8), (22, 2), (1, 25), (12, 23), (14, 3), (18, 20), (4, 19), (24, 5)]

Iterations: 6746593

Set 18 : [(23, 18), (15, 7), (17, 3), (25, 24), (22, 5), (12, 19), (1, 21), (4, 14), (11, 8), (9, 10), (13, 2), (20, 6), (0, 16)]

The number of iterations goes up dramatically over time, but it's within workable limits.

Since this solution relies on a random shuffle, there's also some variability in the results. For example, when looking for a class set of 12, I find that some runs appear to get into an impossible corner, where others quite quickly get all 11 possible sets, as the one below did:

Iterations: 1

Set 0 : [(6, 1), (7, 9), (11, 4), (10, 3), (8, 2), (5, 0)]

Iterations: 2

Set 1 : [(1, 3), (10, 11), (9, 8), (5, 7), (0, 6), (2, 4)]

Iterations: 4

Set 2 : [(2, 10), (7, 8), (4, 6), (5, 11), (3, 9), (1, 0)]

Iterations: 15

Set 3 : [(9, 10), (4, 1), (8, 5), (7, 11), (6, 2), (3, 0)]

Iterations: 17

Set 4 : [(11, 9), (8, 1), (6, 5), (7, 3), (4, 10), (0, 2)]

Iterations: 21

Set 5 : [(4, 3), (7, 1), (2, 11), (9, 5), (6, 8), (0, 10)]

Iterations: 38

Set 6 : [(10, 7), (4, 0), (9, 6), (11, 8), (2, 1), (5, 3)]

Iterations: 241

Set 7 : [(4, 7), (11, 3), (9, 2), (0, 8), (6, 10), (5, 1)]

Iterations: 806

Set 8 : [(9, 1), (3, 2), (4, 5), (8, 10), (11, 6), (0, 7)]

Iterations: 1660

Set 9 : [(8, 3), (2, 5), (11, 0), (9, 4), (7, 6), (1, 10)]

Iterations: 9236

Set 10 : [(0, 9), (2, 7), (5, 10), (3, 6), (8, 4), (11, 1)]

Answer 2

This is equivalent to a round robin tournament. https://en.wikipedia.org/wiki/Round-robin_tournament

The relevant text "The standard algorithm for round-robins is to assign each competitor a number, and pair them off in the first round then fix one of the competitors in the first or last column of the table and rotate the others clockwise one position until you end up almost back at the initial position. If there are an odd number of competitors, a dummy competitor can be added, whose scheduled opponent in a given round does not play and has a bye."