Euchre Tournament random seating algorithm

[tom_mi]

Hi All,
I'm hoping I can find some help to solve a puzzle that came up last night with friends. I thought I could find a solution but have been out of college too long. We had 3 couples over (8 adults), and wanted to play a single round for each possible pairing of the 8 people. After playing with each person as a partner, we' have an individual emerge with the highest overall score.

I thought about 10 rounds would cover each combination, and we simply played until we knew we'd each played with every other person. This got me thinking of my old linear algebra class in college and the 'n choose y' formulas involving factorials.

I've googled and found the combinatorial matrix formula, but can't use it to properly get the number I'm looking for.

Goal: How to apply the C(n,r) formula to properly seat 8 adults into a single pairing with every other member.

My (wrong?) strategy is a 2-pass process:

pass 1: find the number of combinations of all 8 C(8,2) = 28. I know this is correct.
pass 2 (my fail): We must know how many ways to combine each of those 28 pairs into groupings of 4. Isn't this C(28,4)? Obviously not, because that's 20,475. We'd played every combination in about 9 rounds.


Many thanks for anyone willing to help me clarify this!


For reference, the combinational matrix formula:
C(8,2) = 8! / 2! (8 - 2)! = 28
C(28,4) = 28! / 4! (28 - 4)! = 20475

 

[tom_mi]

As I think more about it, the second pass might not need the c(n,k) formula.

the 28 pairs just need to be divided by 4 seats without replication e.g the table can't hold persons 1,4 and 3,1 because person #1 can't sit in 2 seats simultaneously. I'm a programmer and can write a script to handle this second pass; maybe the problem doesn't lend itself to a purely mathematical representation.

 

[jfalter]

I actually ran into the same issues years ago in college when we would host 16 person euchre tournaments. We wanted everyone to play against everyone else exactly once. It turned out to be a pretty non-trivial issue to solve, and I spent quite a bit of time figuring it out. When I finally solved it, I made a piece of software to do it automatically and then to make it all into a pretty scoreboard with PDF scoresheets. It is available for free on sourceforge (http://euchretourney.sourceforge.net/).

Sourceforge also gives access to all the code, so you can see in there what the algorithmic solution was if you're interested as well.

 

[rcgldr]

We wanted everyone to play against everyone else exactly once.

That isn't possible. For 8 players there are 7 rounds, so that means 2 opponents per round (the other team). That averages to playing every opponent twice. I don't know if this is possible, the 2nd list below has some player versus player occurring 1 or 3 times. I tried your program with 8 players and unless I missed something, player 1 never plays against player 8.

Back to the OP, it's doesn't seem too difficult to fill in the list manually for 7 rounds (28 combinations done 4 at a time). The first 3 rows are just permutations of 2 groups of 4 people. The left column just follows all the pairings with person 0. 4th and 5th rows permute two sets of 4 people that haven't played with each other yet. 6th and 7th rows do the same thing:

01 23 | 45 67
02 13 | 46 57
03 12 | 47 56
04 25 | 16 37
05 24 | 17 36
06 27 | 14 35
07 26 | 15 34

This list doesn't result in balanced play in terms of opponents. 0 versus 2 occurs 6 times, while 0 versus 7 only occurs 1 time. The next list is a bit better, with most opponent combinations occurring 2 times, and a few occurring 1 or 3 times:

01 23 | 45 67
02 46 | 13 57
03 56 | 12 47
04 37 | 16 25
05 17 | 24 36
06 14 | 27 35
07 26 | 15 34

To get every team versus every team would be 28C2 = 378 combinations, with a best possible case of 189 rounds.