sharing/swapping items between lists

[Aaron Brady]

On Apr 14, 9:45 pm, Ross <ross.j... at gmail.com> wrote:
> On Apr 14, 7:18 pm, Aaron Brady <castiro... at gmail.com> wrote:
>
>
>
> > On Apr 14, 7:01 pm, Aaron Brady <castiro... at gmail.com> wrote:
>
> > > On Apr 14, 12:37 pm, Ross <ross.j... at gmail.com> wrote:
>
> > > > On Apr 14, 10:34 am, Ross <ross.j... at gmail.com> wrote:
>
> > > > > On Apr 14, 5:57 am, a... at pythoncraft.com (Aahz) wrote:
>
> > > > > > In article <f64c9de2-3285-4f74-adb8-2111c78b7... at 37g2000yqp.googlegroups.com>,
>
> > > > > > Ross  <ross.j... at gmail.com> wrote:
> > > > > > >On Apr 13, 9:08=A0am, a... at pythoncraft.com (Aahz) wrote:
> > > > > > >> In article <c569228f-f391-4317-83a2-08621c601... at r8g2000yql.googlegroups.=
> > > > > > >com>,
> > > > > > >> Ross =A0<ross.j... at 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... at 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.