Zydox/SpringAutohost — Issue #4: balancing algorithm
Author: abma
Created: 2012-01-10 23:27:20+00:00
State: open

a simple balacing algorithm. imo already performs very well:

import random

class Balance():
def __init__(self, players):
self.players=players

def getTeamSum(self, team):
sum=0
for player in team:
sum = sum + player
return sum
def makeRandomTeams(self, teamcount):
""" creates a random team """
tmp = self.players[:] # create copy of players
teams = {}
for i in range(0, teamcount):
teams[i]=[]
i=0
while len(tmp)>0: # fetch a random item + push into a team until tmp list is empty
teams[i].append(tmp.pop(random.randint(0,len(tmp)-1)))
i=(i + 1) % teamcount
return teams

def rating(self, teams, teamcount):
""" rate how good we balanced
this is done by creating a sum of all players of a team
and compare the sums of all teams
"""

sums = {}
avg = 0
for key in teams.keys(): # calculate strength of each team
sums[key]=self.getTeamSum(teams[key])
avg = avg + sums[key]
avg = avg / teamcount # average strength of all teams
rating = 0
for key in sums.keys(): # sum difference of teams from the average
rating = rating + abs(avg - sums[key])
return rating

def balance(self, teamcount, tries=10):
"""
returns balanced teams
"""
lastrating = float("Inf")
lastteam = None
for i in range(0, tries):
teams=self.makeRandomTeams(teamcount)
rating = self.rating(teams, teamcount)
if rating==0: # perfect rating, directly return
return rating, teams
if rating