coed social square

[ryryguy]

Hi, a friend has requested help doing a schedule for a "mix-up" volleyball tournament.  I'm a programmer and want to try to throw together a web page to generate the schedule.

It's basically a 4x4 "social square", but with the additional constraint that the teams must be co-ed. I've briefly scanned Richard's pages about this, but haven't had a chance to dig in seriously yet.  But it seems like his algorithm should work except for the co-ed constraint.  Has anyone got an algorithm that deals with that constraint, or got a hint?  (If someone has or can quickly generate the schedule for me, that would work too!   )

8 guys
8 gals
Teams of 4 coed 2 guys and 2 gals
2 courts at a time
Ten rounds (*edit*: in other words, 20 total games (10 rounds x 2 courts), with each player playing 10 times.)

edit: clarification of number of games.

[ryryguy]

Having had a moment to look a bit more at the social square notes, I see another difference.  For the volleyball tournament, the goal is to maximize the unique combinations of both teammates and opponents.  If I'm reading it right, the "pure" social square is just about unique combinations of teammates.  For the volleyball tournament, for a given player we want to see the same players on either side of the net as few times as possible.  It's probably not possible to get that perfectly balanced but as close as we can come.

[Ian Wakeling]

You are right about the social square, these are not going to help you - but if you do need those then they can be generated with some combinatorial math, search for more info on design theory and affine planes.

The bad news is that I don't have any way of generating a schedule for your volleyball mix-up and it will be a real monster to design an algorithm for balancing it.  You would need to break it down as follows, there are:

56 possible same-sex pairs on the same team
64 possible opposite-sex pairs on the same team
56 possible same-sex pairs on opposing teams
64 possible opposite-sex pairs on opposing teams

Starting with a random schedule, count up the frequency of all the pairs above and then look for changes to the schedule which improve the pairwise balance as a whole.  So an iterative improvement approach may work, or alternatively it may be possible to optimize everything using a constraint programming approach. Either way it will likely take a lot of CPU.

Hope that helps.

[ryryguy]

Thanks Ian.  I hadn't thought of an iterative approach like you describe, that is interesting.

Maybe I'll be able to figure something out for next year - my friend should have asked me to help earlier than 3 days ahead of the tournament.    If I do come up with something I'll post it here.

Thanks again.

[Richard A. DeVenezias]

This plan may work for you.  Females are even numbered and Males odd.

round      team1      team2      team3      team4

1      (16,2,3,5)      (10,15,6,9)      (4,11,13,14)      (7,1,8,12)
2      (16,12,13,15)      (5,10,1,4)      (14,6,3,7)      (2,11,8,9)
3      (16,4,5,7)      (12,2,15,1)      (6,13,8,11)      (9,3,10,14)
4      (16,7,11,14)      (8,10,15,5)      (9,1,12,6)      (3,4,13,2)
5      (16,14,5,9)      (15,2,3,6)      (1,8,10,11)      (4,13,7,12)
6      (16,3,7,10)      (4,6,11,1)      (5,12,14,15)      (8,2,9,13)
7      (16,9,2,7)      (10,12,13,1)      (11,3,14,8)      (5,6,15,4)
8      (16,5,9,12)      (6,8,13,3)      (7,14,1,2)      (10,4,11,15)
9      (16,11,4,9)      (12,14,15,3)      (13,5,2,6)      (1,10,7,8)
10      (16,13,6,11)      (14,1,2,5)      (15,7,4,8)      (3,12,9,10)

There are 78 pairs with repeats. 40 occur twice, 28 thrice and 10 four times.  17 pairs are repeats as opponents-only, 17 as teammates-only and 44 split between as mate and opponent.
6 pairs (out of 120 possible) never occur.

It was derived from the 16-player Whist schedule and popped out after running through some combinatoric and balancing transformations.

[Ian Wakeling]

Richard,

Do you intend that team1 always plays team 2, and team 3 against team 4 in each round?

Ian.

[ryryguy]

Richard - thanks a lot!  I think we can use that.  Even if not as balanced as it could possibly be I think it's a lot better than what they've used in years past.  (This is an annual tournament.)