sharing/swapping items between lists

Aaron Brady castironpi at gmail.com
Wed Apr 15 15:56:37 CEST 2009


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...:

<multiposting>
The randomizing solution isn't quite suitable for 16 teams.  With 5
teams/1 court, and 5 teams/2 courts, 6 teams/2 courts, the solution
comes within seconds.  For 7 teams/3 courts, the solution takes a few
minutes.  (1 GHz.) Here's the code.  I doubt it's adequate, but it
still could be faster, and is definitely less stressful, than by
hand.  For any long-running calculations, save your results.

from itertools import combinations, permutations
import string
import random as ran
def circulate( num_players, num_courts ):
    ''' 2 players per court '''
    assert num_players<= 26, '26 players max'
    assert num_players> 2* num_courts, 'no randomization needed'
    player_set= set( string.ascii_lowercase[ :num_players ] )
    combs= list( ''.join( x ) for x in combinations( player_set, 2 ) )

    #print( len( list( permutations( combs ) ) ) )

    iteration= 0
    while 1:
        ran.shuffle( combs )
        #print( combs )
        ok= True
        for i in range( 0, len( combs ), num_courts ):
            cur= ''.join( combs[ i: i+ num_courts ] )
            #print( cur )
            if len( set( cur ) )!= len( cur ): # any dupes in round
                ok= False
                break
        if ok:
            return [ combs[ i: i+ num_courts ] for i in range( 0, len
( combs ), num_courts ) ]
        iteration+= 1
        if iteration & 0xFFFF== 0:
            print( iteration, hex( iteration ) )



More information about the Python-list mailing list