On Apr 14, 9:45 pm, Ross <ross.j...@gmail.com> wrote: > On Apr 14, 7:18 pm, Aaron Brady <castiro...@gmail.com> wrote: > > > > > On Apr 14, 7:01 pm, Aaron Brady <castiro...@gmail.com> wrote: > > > > On Apr 14, 12:37 pm, Ross <ross.j...@gmail.com> wrote: > > > > > On Apr 14, 10:34 am, Ross <ross.j...@gmail.com> wrote: > > > > > > On Apr 14, 5:57 am, a...@pythoncraft.com (Aahz) wrote: > > > > > > > In article > > > > > > <f64c9de2-3285-4f74-adb8-2111c78b7...@37g2000yqp.googlegroups.com>, > > > > > > > Ross <ross.j...@gmail.com> wrote: > > > > > > >On Apr 13, 9:08=A0am, a...@pythoncraft.com (Aahz) wrote: > > > > > > >> In article > > > > > > >> <c569228f-f391-4317-83a2-08621c601...@r8g2000yql.googlegroups.= > > > > > > >com>, > > > > > > >> Ross =A0<ross.j...@gmail.com> wrote: > > > > > > > >>>I'm sorry...my example was probably a bad one. A better example > > > > > > >>>of > > > > > > >>>output I would like would be something like [[1,2],[3,4],[5,6]] > > > > > > >>>and > > > > > > >>>then for the leftovers list [7,8,9,10 etc]. What I'm trying to > > > > > > >>>do is > > > > > > >>>produce some sort of round robin algorithm for tennis that is > > > > > > >>>constrained by the number of courts available each week. So if > > > > > > >>>there > > > > > > >>>are only 3 courts available for a singles league and 10 people > > > > > > >>>have > > > > > > >>>signed up, 4 players will have a bye each week. I want my > > > > > > >>>algorithm to > > > > > > >>>produce unique matchups each week and also give each player the > > > > > > >>>same > > > > > > >>>angle? > > > > > > > >> How about Googling for "round robin algorithm python"? ;-) > > > > > > > >I have the basic algorithm and it works fine...I'm just having > > > > > > >trouble > > > > > > >adding another parameter to it that allows for court constraints > > > > > > >and > > > > > > >bye weeks. > > > > > > > You'll need to give us more information, then. Why don't you start > > > > > > with > > > > > > the core algorithm you're using? > > > > > > -- > > > > > > Aahz (a...@pythoncraft.com) <*> > > > > > > http://www.pythoncraft.com/ > > > > > > > Why is this newsgroup different from all other newsgroups? > > > > > > Here's the core algorithm I'm using: > > > > > > >>> def round_robin(teams,rounds): > > > > > > if len(teams)%2: > > > > > teams.append(None) > > > > > mid = len(teams) //2 > > > > > for i in range(rounds): > > > > > yield zip(teams[:mid], teams[mid:]) > > > > > teams = teams[0:1] + teams[mid:mid+1] + > > > > > teams[1:mid-1]+teams[mid > > > > > +1:]+teams[mid-1:mid] > > > > > > >>> if __name__== '__main__': > > > > > > rounds = 15 > > > > > teams = range(16) > > > > > for round in round_robin(teams,rounds): > > > > > print round > > > > > fyi rounds=15 and teams =range(16) was just test code I was playing > > > > around with...they could theoretically be anything. > > > > Here is an idea. Create a list of all possible pairs, using > > > itertools.combinations. You'll notice everyone gets equal play time > > > and equal time against each other on a pair-by-pair basis. Then, call > > > random.shuffle until one player isn't playing on two courts in one > > > day. > > > This might take a long time. Not that I can guarantee that a depth- > > first-search would be any faster, or that a breadth-first-search would > > run faster *and* run in available memory. <cough> > > I have a sub-optimal solution that I'm playing with now. Since my > output is a list of tuples and looks something like this (if there > were 16 teams and 15 rounds), I could designate a each nth tuple in > each round as a bye, but since the 1st item in my list remains fixed, > it's suboptimal. For example, you could say every 4th (and/or 3rd , > 5th, etc depending on how many available cts) tuple in each round gets > a bye and pop() it from the list...:
>From what I understood, you want each player to play each other player exactly once, with no empty courts until the last round. Your solution doesn't achieve that if you simply omit a choice of matches, even if you omit them fairly. How to omit them fairly is a separate question. I observe that your tuples follow a pattern. Each court is a match between the first slot on the previous court on the previous week, and the second slot on the previous court on the next week, with the exceptions of the first and last courts. The same player always plays on court one against the second slot on the second court on the previous week (and hence (?), first slot on second court on the next week), and the last court is always between the second slot on the last court on the next week and the first slot on the previous court on the previous week. IN other words, it follows a zig zag. Your idea of omitting a given court, including the last but except the first, omits each player twice, and two opponents of each player. If you try to finish the schedule, it will take at least three more weeks. Arranging the second column: 5, 3 14, 7 10, 12 2, 8 6, 4 13, 15 9, 11 11, 13 15, 6 4, 2 8, 10 12, 14 7, 5 3, 1 1, 9 There is guaranteed to be one left over. From what I read about your algorithm last night, if the number of teams is odd, you might be able to finish in two more weeks, because there is always a 'None', but I haven't tried it. Something tells me that my 'randomly permute and eliminate impossible rounds' won't be any more successful, except if you have fewer courts than num*(num+1)/2, but I can give it a shot. -- http://mail.python.org/mailman/listinfo/python-list
