sharing/swapping items between lists
MRAB
google at mrabarnett.plus.com
Wed Apr 15 17:08:01 EDT 2009
samwyse wrote:
> On Apr 15, 8:13 am, Aaron Brady <castiro... at gmail.com> wrote:
>> On Apr 15, 6:57 am, samwyse <samw... at gmail.com> wrote:
>>
>>> 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
More information about the Python-list
mailing list