# Permutation of sort ... creating team proposals

Gerhard Häring gerhard.haering at gmx.de
Sat Aug 24 18:21:44 CEST 2002

```* 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)

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

# Skill sum total

# 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
--