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.
Best Answer
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:
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:
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: