Permutation of sort ... creating team proposals

[Gerhard Häring]

* Thomas Weholt <2002 at weholt.org> [2002-08-24 15:51 +0000]:
> Hi,
> 
> I've planned to host a lanparty soon and want help to determine what teams
> we should go with. We need two teams and I've put together a list of players
> and given each a rating of experience from newbie to hardcore with some gray
> areas inbetween. Now I'd like to use python to generate team proposals,
> using all players, each team balanced both in terms of experience and number
> of players.
> 
> Take this list :
> 
> players = [('thomas', 5), ('john', 4), ('joe', 3), ('gary', 4'), ('jonas',
> 2), ('eirik', 1), ('anders', 5), ('rune', 5), ('shirley', 2), ('jedi', 3) ]
> 
> Rating goes from 1 = newbie to 5 = hardcore. Each team should have aprox.
> equal  number of players and equal sum of experience, but number of players
> may vary if sum of experience stays the same.
> 
> How can I use python generate some team-proposals ?? I was thinking of using
> some sort of permutation, but cannot get the hang of it. Haven't even got
> one line of code to show you.

I have, it doesn't vary the number of players, though :-)

It uses a permutation function that I wrote once when experimenting with
generators, there are of course tons of alternative implementations out
there:

#!/usr/bin/env python2.2
from __future__ import generators
import operator, random

def permutations(items):
    """Yields all permutations of the items."""
    if items == []:
        yield []
    else:
        for i in range(len(items)):
            for j in permutations(items[:i] + items[i+1:]):
                yield [items[i]] + j

players = [('thomas', 5), ('john', 4), ('joe', 3), ('gary', 4), ('jonas', 2), \
    ('eirik', 1), ('anders', 5), ('rune', 5), ('shirley', 2), ('jedi', 3) ]

# So we don't get the same result every time:
random.shuffle(players)

def add_skills(players):
    return reduce(operator.__add__, [p[1] for p in players])

# Skill sum total
skill_sum = add_skills(players)

# Split team in half at which list pos:
SPLIT_POS = len(players) / 2

# Set to 0 to find all possible combinations
BREAK_AFTER_FOUND = 1

# How much may the skills of the two teams differ?
OK_DIFFER_SKILLS = 0.05

for perm in permutations(players):
    team1, team2 = perm[:SPLIT_POS], perm[SPLIT_POS:]
    if abs(add_skills(team1) / float(skill_sum) - 0.5) <= OK_DIFFER_SKILLS:
        print "-" * 50
        print "team1:", team1, "have skill", add_skills(team1)
        print "team2:", team2, "have skill", add_skills(team2)
        if BREAK_AFTER_FOUND:
            break
-- 
This sig powered by Python!
Außentemperatur in München: 24.5 °C      Wind: 2.5 m/s