On Apr 15, 11:29 am, samwyse <samw...@gmail.com> wrote:
> On Apr 15, 8:56 am, Aaron Brady <castiro...@gmail.com> wrote:
>
>
>
> > 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.
>
> 7 teams/3 courts is the same as 8 teams/4 courts, where the extra
> player is named "bye". In other words, it's an uncontrained problem.
For 9 teams, there are (9*8/2), or 36 pairs, so 36!, or
371993326789901217467999448150835200000000, or 3.7e+41 permutations of
arranging them. (Thanks to Python's long ints.) Many of them work on
2 courts.
There are 5x10^68 hydrogen atoms in a galaxy.
There was a discussion on python-ideas about whether ran.shuffle( ) is
even guaranteed to find a solution eventually. I forget if 36! was
within its bounds. It may run for years and fail.
On the 8 teams/3 courts trial, a depth-first search can improve your
results in a few seconds, but only by getting one team in one round
earlier. That figure is interesting, because there are 28! or 3e+29
possible permutations. It seems many of them work.
The rest of the combinations are impractical to try with a DFS, or
your algorithm does just as good. Here is the DFS. Mine is currently
tinkering around on the 25th place of 36 total slots.
The Pinewood Derby case doesn't show much more promise, though you can
eliminate more possibilities from your round, which may speed it up.
from itertools import combinations, permutations
import string
from copy import deepcopy
def circulate( num_players, num_courts ):
''' 2 players per court '''
assert num_players<= 26, '26 players max'
player_set= sorted( string.ascii_lowercase[ :num_players ] )
combs= sorted( ''.join( x ) for x in combinations( player_set,
2 ) )
print( combs )
obs= [ [ x, 0 ] for x in combs ]
# obs[ 1 ]-- 0: not used, 1: one player of combination
# used in round, 2: combination used
stack= [ None ]* len( combs )
def rec( obs, dep ):
if dep< len( combs )- 12:
print( '%i teams %i courts dep %i\nobs %r\nstack %r\n'%
( num_players, num_courts, dep, obs, stack ) )
if all( [ x[ 1 ]== 2 for x in obs ] ):
return True
if ( dep+ 1 )% num_courts== 0:
for x in obs: # new round, clear 'obs'
if x[ 1 ]== 1:
x[ 1 ]= 0
else:
for x in obs: # mark 'obs' so player not tried again
if x[ 1 ]!= 0:
continue
for y in stack[ dep ]:
if y in x[ 0 ]:
x[ 1 ]= 1
for i in range( len( combs ) ):
if obs[ i ][ 1 ]== 0:
obs[ i ][ 1 ]= 2
stack[ dep+ 1 ]= obs[ i ][ 0 ]
res= rec( deepcopy( obs ), dep+ 1 )
if res: return True
obs[ i ][ 1 ]= 0
stack[ dep+ 1 ]= None
return False
rec( deepcopy( obs ), -1 )
return [ stack[ i: i+ num_courts ] for i in range( 0, len
( stack ), num_courts ) ]
--
http://mail.python.org/mailman/listinfo/python-list
