sharing/swapping items between lists

[Aaron Brady]

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 ) ]

 

[MRAB]

Here's my idea: generate all possible pairs:
import itertools
players = [chr(c) for c in xrange(ord('a'),ord('z')+1)]
all_pairs = list(itertools.combinations(players,2))
partition the list:
def choose_nonoverlapping(pairs):
chosen, leftover, used = list(), list(), list()
for p in pairs:
a, b = p
if a in used or b in used:
leftover.append(p)
else:
chosen.append(p)
used.append(a)
used.append(b)
return chosen, leftover
court_count = 10
week_count = 10
pairs = all_pairs
for week in xrange(week_count):
print 'week', week+1
this_week, pairs = choose_nonoverlapping(pairs)
print ', '.join(map(lambda t: ' vs '.join(t), this_week
[:court_count]))
pairs[0:0] = this_week[court_count:]

snip

Your idea arrives at a sub-optimal solution on players= 'abcdef',
court_count= 3.

Correct, by hand (5 weeks):

ab cd ef
ac be df
ad ce bf
ae bd cf
af bc de

Program (7 weeks):
[snip]
However, you do correctly arrive at all the combinations, in better
than the naive 'one pair per week' solution. Further, you produced
the correct solution for players= 'abcdef', for court_count= 1 and
court_count= 2, which I also tested. Damage report?

It does work better when there are a limited number of courts, but
since that was in the original description, I didn't worry too much.

One could product several random shuffles of the list of combinations
and see which produced the shortest list of results. That would add
indeterminancy without guaranteeing an optimal result. But I think
that other people have algorithms for that case, so I'm not too
worried.

I've tried generalizing to competitions with more than two player
(e.g. the Pinewood Derby, where up four cars are in each heat), but
the algorithm falls apart, mostly due to the way
itertools.combinations returns its results.

Here's the basics of my algorithm, for what it's worth. It just returns
the pairs:

def get_pair(player_queue, done_pair):
for first in player_queue:
for second in player_queue:
pair = first, second
if first != second and pair not in done_pair:
return pair
return None

def round_robin(players):
player_queue = players[:]
done_pair = set()
while True:
pair = get_pair(player_queue, done_pair)
if pair is None:
player_queue = players[:]
break
else:
done_pair.add(pair)
done_pair.add((pair[1], pair[0]))
player_queue = [p for p in player_queue if p not in pair] +
list(pair)
yield pair

for pair in round_robin('abcdef'):
print pair