|
|
|
I'll try doing it. Er... I guess I'll pm you.
Nvm..... -_- I was thinking math, but more mathematical computing.
I mean Mathematical Programming.
|
put all the names out in twice
with the name on top of itself
like
BOB JIM KIM
BOB JIM KIM
then move the bottom row once for each week.
last two people sit out.
the rest i just dont understand :D
|
United States24761 Posts
Er, to clarify a bit. Doubles in tennis is when two people are on a team and against two people on a different team. There are two courts. That means Person 1 and 2 are playing against person 3 and 4. Likewise, person 5 and 6 are playing against person 7 and 8. Person 9 and 10 are sitting out. Each week we mix it up so that each person gets to be partners with everyone and against everyone, etc.
|
so my answer was completely useless 
lol. you didnt have to clarify i just should have read more carefully.
8 players on 2 courts should have given it away.
|
10 person magic square, column 9 and 10 are byes, column 1 partners with 2, plays 3 and 4.
For 35 weeks, there's a more generalized version, but I forget what it's called.
|
On August 04 2010 10:44 micronesia wrote:
My friend has asked me to help him with a semi-mathematical problem. He is planning a 35 week tennis season for 10 players. Each week, 8 players will play on two courts (doubles) and 2 players will sit out. He needs to create a schedule that says who plays which weeks, who sits out each week, and who partners with and plays against who. The goal is to mix it up as much as possible so that each player plays approximately the same number of weeks, gets to play with each person as a partner, and has the most diversity with regards to their opponents.
Well, it's not hard to see that each player should play for 28 weeks (8/10 of 35).
As far as pairings are concerned, there will be 140 pairings made (4 * 35), using the 45 possible pairs (10 choose 2) available. 140/45 (or 28/9) is almost exactly 3, so everyone can pair with everyone else 3 times, while 5 pairs will play with each other a fourth time.
For diversity of opponents, each player can potentially face 36 pairs that do not include himself (9 choose 2). He can only play 28 of them, however.
To actually create the schedule, I haven't thought about this too much, but would a naive iterative approach be too much work? For instance, you could start by randomly assigning the 5 pairs who partner an extra time (say, 1-2, 3-4, 5-6, 7-8, 9-10). Then you could start distributing each of the 45 pairs over 3 or 4 days. You could do the first few without overlapping. After that you have to start keeping in mind the rules about diversity: all you have to worry about is pairing a group twice with the same player on the opposite side. Maybe it would help to keep a master list for each player (of the 10) of which groups (of the 36) he has faced so far: that would only be 280 entries; seems manageable.
|
you can use linear programming and solve it in lindo if that helps, but there would be a lot of variables and equations
|
Interesting problem, I'll play around with it and see if I can come up with anything.
edit: Well, I was able to enumerate every possible combination of "different" player configurations, by listing all permutations of the numbers from 1-10 and then eliminating duplicates. Each permutation of {1,2,...10} was represented as {(((p1,p2),(p3,p4)), ((p5,p6),(p7,p8))), (p9,p10)} , where {} brackets mean order matters, and parens () mean order doesn't matter. For each permutation, I sorted everything in parentheses. Then I removed duplicate permutations.
Here's a file with all different player configurations. The only problem is that there are 14175 of these combinations, so you'll need to choose a subset of these that maximizes "diversity". To do this, you'll first need to define "diversity" more concretely, e.g.; is it more important that a player's partner is not repeated, even if it means he plays the same opponents multiple times?
|
I'm pretty sure this is a difficult problem to solve with an actual optimal solution; it's much like a minweight matching problem, but it's not bipartite so the problem is probably NP hard.
Don't listen to the linear programming guy, you'd have to use integer programming to model it properly, in which case you're probably better off just using some naive iterated method.
|
United States24761 Posts
On August 04 2010 12:02 overpool wrote:Interesting problem, I'll play around with it and see if I can come up with anything. edit: Well, I was able to enumerate every possible combination of "different" player configurations, by listing all permutations of the numbers from 1-10 and then eliminating duplicates. Each permutation of {1,2,...10} was represented as {(((p1,p2),(p3,p4)), ((p5,p6),(p7,p8))), (p9,p10)} , where {} brackets mean order matters, and parens () mean order doesn't matter. For each permutation, I sorted everything in parentheses. Then I removed duplicate permutations. Here's a file with all different player configurations. The only problem is that there are 14175 of these combinations, so you'll need to choose a subset of these that maximizes "diversity". To do this, you'll first need to define "diversity" more concretely, e.g.; is it more important that a player's partner is not repeated, even if it means he plays the same opponents multiple times?
Wow that's really cool. Yeah I understand I'm being a bit unclear about 'diversity' but that's just because we aren't that picky. Basically, as long as everyone plays the same number of weeks (preferably spread out but not a necessity) and gets to play with each partner approximately the same number of times, and gets to play nearly as many possible opponent-combinations as possible, it's good enough! Any more particular guidelines is unnecessary from my perspective but perfectly welcome if anyone wants to impose it.
Maybe I can just pick 35 random lines from there until it meets the requirements:
1) Each person plays the same number of weeks
2) Each person plays at least twice with each partner
3) Each person does not play the same opponent pair twice in the same season
Would that be fairly easy to do?
|
|
|
On August 08 2010 07:25 micronesia wrote:Show nested quote +On August 04 2010 12:02 overpool wrote:Interesting problem, I'll play around with it and see if I can come up with anything. edit: Well, I was able to enumerate every possible combination of "different" player configurations, by listing all permutations of the numbers from 1-10 and then eliminating duplicates. Each permutation of {1,2,...10} was represented as {(((p1,p2),(p3,p4)), ((p5,p6),(p7,p8))), (p9,p10)} , where {} brackets mean order matters, and parens () mean order doesn't matter. For each permutation, I sorted everything in parentheses. Then I removed duplicate permutations. Here's a file with all different player configurations. The only problem is that there are 14175 of these combinations, so you'll need to choose a subset of these that maximizes "diversity". To do this, you'll first need to define "diversity" more concretely, e.g.; is it more important that a player's partner is not repeated, even if it means he plays the same opponents multiple times? Wow that's really cool. Yeah I understand I'm being a bit unclear about 'diversity' but that's just because we aren't that picky. Basically, as long as everyone plays the same number of weeks (preferably spread out but not a necessity) and gets to play with each partner approximately the same number of times, and gets to play nearly as many possible opponent-combinations as possible, it's good enough! Any more particular guidelines is unnecessary from my perspective but perfectly welcome if anyone wants to impose it. Maybe I can just pick 35 random lines from there until it meets the requirements: 1) Each person plays the same number of weeks 2) Each person plays at least twice with each partner 3) Each person does not play the same opponent pair twice in the same season Would that be fairly easy to do?
Hm, choosing randomly might not be efficient enough to be viable as only a small percent of random combinations would fulfill even the most simple of requirements. Unfortunately, generating combinations that fit such requirements is above my ability level (just a high school student ), but I'm sure there's someone on TL who could do it. For instance, Day[9] is strong in combinatorics iirc.
|
Okay here's what I got:
These are all of the possible partnerships:
http://img811.imageshack.us/img811/5302/sany0110.jpg
This is how to get each team onto each court an equal number of times throughout the 10 weeks:
http://img186.imageshack.us/img186/634/sany0109d.jpg
Denote a group of 4 players, say α through δ, and have cycle through the team labelled as λ over the first group of 5 weeks. Then when the 5 weeks are up as shown in the second picture, redo the process of assigning players to groups as you please.
Then you have your 35 weeks in sets of 5 repeated over and over with at least 2 repeating partnerships per player, as you want.
|
United States24761 Posts
On August 08 2010 09:51 Galois wrote:Okay here's what I got: These are all of the possible partnerships: http://img811.imageshack.us/img811/5302/sany0110.jpgThis is how to get each team onto each court an equal number of times throughout the 10 weeks: http://img186.imageshack.us/img186/634/sany0109d.jpgDenote a group of 4 players, say α through δ, and have cycle through the team labelled as λ over the first group of 5 weeks. Then when the 5 weeks are up as shown in the second picture, redo the process of assigning players to groups as you please. Then you have your 35 weeks in sets of 5 repeated over and over with at least 2 repeating partnerships per player, as you want.
Wow your notation is confusing the hell out of me... first of all I stink with greek letters and second of all the week # symbols you are using I haven't seen before in my recollection.
|
...but I thought that being an obnoxious elitist was what this community was all about. :x
it doesn't matter what the letters or symbols are, though~
you create 5 groups of 2. each of these 5 groups are represented by the letters λ through ο. the players in these guys are chosen as you wish so long as they are selected from the list in the first picture.
the second picture shows the play schedule that you repeat. even though there are a bunch of ways to scatter about the random teams and games, the matches can be rearranged to follow the pattern in the second post to get everybody to play together twice.
then at the end of the 35 weeks everyone will have had their time playing with eachother at least twice.
this is my reasoning in the other post.
edit - i will work harder to try to illustrate more in another post. hopefully i won't die in a duel immediately after staying up all night working on this pressing issue
|
|
|
|
|
|
EPT
