Algorithm for Grouping Numbers (Making Teams)

  • Thread starter Thread starter a
  • Start date Start date
A

a

We are writing an app that assigns people to teams based on their curent
score. Teams are 8 people, there are 2 teams. (i would like it to be
flexible, but this is a start). I need an algorithm that creates the 2
teams such that the total score for each team is as close as possible.

Any ideas??

Thanks!
 
Interesting question! We may get multiple results for the it. Anyway, a
important queation, should each team have four people, or the number is
unlimited? For example, a big guy VS seven little babies?

Luke
Microsoft Online Support

Get Secure! www.microsoft.com/security
(This posting is provided "AS IS", with no warranties, and confers no
rights.)
 
Actually, in this situation, we are a gaming center setting up Day of Defeat
tournament, so it will always be 8 v 8. We are writign a string parser that
pulls stats out of the Server Log for the round, then we need to re-assign
teams such that they are 'as even as possible'. The winner is the
individual with the best score.

Thanks!

Kevin
www.thetek.com
 
a said:
We are writing an app that assigns people to teams based on their curent
score. Teams are 8 people, there are 2 teams. (i would like it to be
flexible, but this is a start). I need an algorithm that creates the 2
teams such that the total score for each team is as close as possible.

Any ideas??
Click to expand...

That's a variation on the bin packing problem, which is known to be hard (NP).

http://www.nist.gov/dads/HTML/binpacking.html

Nevertheless, you should find a number of useful algorithms based upon rules
of thumb.

Eg. Order the people from highest score to lowest, assign the first to team 1,
the next two to team 2 and alternate from there.

(Or sing to yourself "eanie meanie minie moe, ..." while pointing at each
person...)

In the case you ask about, you're choosing 8 from 16 (without regard to
order), and the number of possible combinations is the combinatorical 16 C 8
or
16
C
8

or

(16)
( 8)

depending upon what you were taught at school.

That is 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9
divided by 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
which is 13 * 11 * 10 * 9 = 12870

So analysing all 12870 combinations ("brute force") will be fine on today's
computers.

Of course, in the general case, you don't need many more people or teams to
make brute force intractable.
 
Hi Kevin,

I'm working on your query but having a TERRIBLE TIME with this server
problem. For instance your original post has been "deleted from the server". I
never got to see the reply from the MS guy. The header was there, now having
reset my news-store, it won't load. (Though I can see it appended to your
message just now)

Sorry for shouting - I'm very frustrated with losing messages, not being
able to download, etc. etc, etc. :-((

[Takes a deep breath and goes off to make a cup of tea]

So - to your team-building algorithm. I see it in three parts - there's
the generation of teams, the scoring, and the finding of the optimum balance.

One way is to do it in phases - generate the teams, score, sort and
select. This would be acceptable given 16 players and 2 teams as the number
of combinations is only 6435**. Go up to 24 players and 3 teams, though and
that number rises to 24! / (8! x 16!) = 4M (for the first team) times 12870
for
the other two. You don't even want to <think> about 64 and 4 teams!!

Another way is to generate and score in a single phase using the knowledge
of the-best-so-far to decide not to bother with certain areas of the search
space. This is harder to program but will be necessary if you expand the
numbers. Stronger pruning can be done in your situation, as the Ultimate Best
Solution! is not necessary - you want something 'reasonable' and 'seen to be
fair'. If you go for high numbers of players, accuracy will cost too much and
your scoring/pruning will have to become ruthless.

Team Generation.
This is easily done with recursion. (The test harness outweighs the
algorithm!). You can do it by player or team - For each player, assign to each
team in turn. recurse to allocate the next player, and so on - or - For each
team, fill with a combination of players, recurse for the next team. The
second is slightly harder as it incorporates the first method in order to
produce the combinations within the team but is more flexible in that you
could have, say, 3 teams from a set of 20 players - 2 x 7 per side and a team
of 6.

I've written an algorithm that uses the first method. You give it a
list of players and a number of teams. It generates all the unique
possibilities. It requires the same number in each team.

Scoring.
This depends on what you want. You mentioned that you want the teams
scores to be as close as possible, but as Luke mentioned, would you want a
giant and several pygmies versus an average crowd? You probably want some
balance within the teams as well as between them.

Feel free to come back with questions and more details, eg what's your
deadline, and future plans (bigger and better tournaments, etc), will you have
odd-numbers of players (eg, the 7, 7, 6), how do you envisage the scoring,
what
do scores consist of (single value, multi-valued), etc.

What's your programming level? Do you want to be shown and then to go and
do it, or would you benefit from more guidance?

Regards,
Fergus

Permutations and Combinations explained.
http://engineering.uow.edu.au/Courses/Stats/File2417.html

** 6435
The number of combinations of r team members from a selection of n is
given by
n! / r! (n - r)!
which is 16! / (8! x 8!) = 12870 for n = 16, r = 2, but this can be halved
as there are two sets of r players and each complete combination will be
mirrored. {eg T1=ABC, T2=DEF and T1=DEF, T2=ABC are equivalent}.

In the 24 into 3 teams case, the total would be divided by 3! - wow, big
saving!! ;-)
 
Thanks!

I have the scoring down (VB.NET OOP style app). At the end of round one,
each player will have a score. We want to build the 2 teams of 8 so that
the total scores of each team are nearly equal. One post (Mark Hurd)
implies that doing this will be real difficult. I am a decent programmer,
but not an algorithm writer. I would love a freebie, but a point in the
right direction would work also. I would like to eventually pass in a
'PlayerList' (collection of 'Player' Objects) and get back an array of 2
Player Lists, but passing in an array or anything would work.

Thanks!

kevin


Fergus Cooney said:
Hi Kevin,

I'm working on your query but having a TERRIBLE TIME with this server
problem. For instance your original post has been "deleted from the server". I
never got to see the reply from the MS guy. The header was there, now having
reset my news-store, it won't load. (Though I can see it appended to your
message just now)

Sorry for shouting - I'm very frustrated with losing messages, not being
able to download, etc. etc, etc. :-((

[Takes a deep breath and goes off to make a cup of tea]

So - to your team-building algorithm. I see it in three parts - there's
the generation of teams, the scoring, and the finding of the optimum balance.

One way is to do it in phases - generate the teams, score, sort and
select. This would be acceptable given 16 players and 2 teams as the number
of combinations is only 6435**. Go up to 24 players and 3 teams, though and
that number rises to 24! / (8! x 16!) = 4M (for the first team) times 12870
for
the other two. You don't even want to <think> about 64 and 4 teams!!

Another way is to generate and score in a single phase using the knowledge
of the-best-so-far to decide not to bother with certain areas of the search
space. This is harder to program but will be necessary if you expand the
numbers. Stronger pruning can be done in your situation, as the Ultimate Best
Solution! is not necessary - you want something 'reasonable' and 'seen to be
fair'. If you go for high numbers of players, accuracy will cost too much and
your scoring/pruning will have to become ruthless.

Team Generation.
This is easily done with recursion. (The test harness outweighs the
algorithm!). You can do it by player or team - For each player, assign to each
team in turn. recurse to allocate the next player, and so on - or - For each
team, fill with a combination of players, recurse for the next team. The
second is slightly harder as it incorporates the first method in order to
produce the combinations within the team but is more flexible in that you
could have, say, 3 teams from a set of 20 players - 2 x 7 per side and a team
of 6.

I've written an algorithm that uses the first method. You give it a
list of players and a number of teams. It generates all the unique
possibilities. It requires the same number in each team.

Scoring.
This depends on what you want. You mentioned that you want the teams
scores to be as close as possible, but as Luke mentioned, would you want a
giant and several pygmies versus an average crowd? You probably want some
balance within the teams as well as between them.

Feel free to come back with questions and more details, eg what's your
deadline, and future plans (bigger and better tournaments, etc), will you have
odd-numbers of players (eg, the 7, 7, 6), how do you envisage the scoring,
what
do scores consist of (single value, multi-valued), etc.

What's your programming level? Do you want to be shown and then to go and
do it, or would you benefit from more guidance?

Regards,
Fergus

Permutations and Combinations explained.
http://engineering.uow.edu.au/Courses/Stats/File2417.html

** 6435
The number of combinations of r team members from a selection of n is
given by
n! / r! (n - r)!
which is 16! / (8! x 8!) = 12870 for n = 16, r = 2, but this can be halved
as there are two sets of r players and each complete combination will be
mirrored. {eg T1=ABC, T2=DEF and T1=DEF, T2=ABC are equivalent}.

In the 24 into 3 teams case, the total would be divided by 3! - wow, big
saving!! ;-)
Click to expand...
 
The type of algorithm you need is a network algorithm. In your reference
books (or Google), look for where the book talks about (or give examples of)
the "shortest route" or "weighted path" type problems.

Sorry, but it's been years since I've done that type of stuff. I therefore
don't happen to have any specific URLs or references to pass on to you.

Richard Rosenheim
 
That's a variation on the bin packing problem, which is known to be hard (NP).

http://www.nist.gov/dads/HTML/binpacking.html

Nevertheless, you should find a number of useful algorithms based upon rules
of thumb.

Eg. Order the people from highest score to lowest, assign the first to team 1,
the next two to team 2 and alternate from there.

(Or sing to yourself "eanie meanie minie moe, ..." while pointing at each
person...)
Click to expand...

Slightly better than the eanie meanie... The very fact that comments
exist in this code means that you can optimise it ;]

For Each oPlayer in oSortedPlayerCollection

' If either team is full, fill the other team

If oTeam1.Count = 4 Then
oTeam2.Add(oPlayer)
ElseIf oTeam2.Count = 4 Then
oTeam1.Add(oPlayer)

' Put the player in the team with the lowest total

ElseIf oTeam1.TotalScore < oTeam2.TotalScore Then
oTeam1.Add(oPlayer)
Else
oTeam2.Add(oPlayer)
End If
Next

Once that is done, you can iterate down both team lists (which will be
in descending order too). Test each oTeam1.Player(i) and
oTeam2.Player(i) to see if it is worthwhile swapping them (ie. the
absolute difference between oTeam1.TotalScore and oTeam2.TotalScore
reduces). That can give you a refinement (but not neccessarily the
best answer).

For i = 0 To 3

' This is the difference between the team scores

Dim oCurrentDifference As Integer
oCurrentDifference = Abs(oTeam1.TotalScore-oTeam2.TotalScore)

' This is the total score of team 1 if the player is swapped

Dim oTeam1TestScore As Integer
oTeam1TestScore = oTeam1.TotalScore-oTeam1.Player(i).Score + _
oTeam2.Player(i).Score

' This is the total score of team 2 if the player is swapped

Dim oTeam2TestScore As Integer
oTeam2TestScore = oTeam2.TotalScore-oTeam2.Player(i).Score + _
oTeam1.Player(i).Score

' If the players are swapped, this is the new team difference

Dim oTestDifference As Integer
oTestDifference = Abs(oTeam1TestScore-oTeam2TestScore)

' If the difference has improved, swap the players

If oTestDifference < oCurrentDiference Then
Dim oTempPlayer As Player
oTempPlayer = oTeam1.Player(i)
oTeam1.Player(i) = oTeam2.Player(i)
oTeam2.Player(i) = oTempPlayer
End If
Next

I mention this as it's a good way to get very close to a best answer
without using too many resources (and it often gets it). And it gets
better as the number of players (N) increases. Though I do concur with
Mark; there is no reason to avoid a brute-force approach as N is small
in your case.

FYI: One brute force approach is basically as written, but instead you
test for swapping between oPlayer(i) and oPlayer(j). i.e. An
additional loop incrementing an integer value (j) around the whole
lot. See? Easy. You don't need the initial sort, incidentally, as the
ordering and original team membership (and order therein) is
irrelivant.

Now, as you're sorting out player arrangement... how about
facilitating the ability to have two players who like each other being
allocated to the same team, and/or two players who hate each other on
different teams? Trickier... Much tricker... ;)

Rgds,
 
Wow, thanks! Never thought about building a team and looking for swaps!

(I figure, instead of writing the app to deal with the case where someone
wants to be on a certain team, I'll accept a payoff and do it by hand! lol)

_Andy_ said:
That's a variation on the bin packing problem, which is known to be hard (NP).

http://www.nist.gov/dads/HTML/binpacking.html

Nevertheless, you should find a number of useful algorithms based upon rules
of thumb.

Eg. Order the people from highest score to lowest, assign the first to team 1,
the next two to team 2 and alternate from there.

(Or sing to yourself "eanie meanie minie moe, ..." while pointing at each
person...)
Click to expand...

Slightly better than the eanie meanie... The very fact that comments
exist in this code means that you can optimise it ;]

For Each oPlayer in oSortedPlayerCollection

' If either team is full, fill the other team

If oTeam1.Count = 4 Then
oTeam2.Add(oPlayer)
ElseIf oTeam2.Count = 4 Then
oTeam1.Add(oPlayer)

' Put the player in the team with the lowest total

ElseIf oTeam1.TotalScore < oTeam2.TotalScore Then
oTeam1.Add(oPlayer)
Else
oTeam2.Add(oPlayer)
End If
Next

Once that is done, you can iterate down both team lists (which will be
in descending order too). Test each oTeam1.Player(i) and
oTeam2.Player(i) to see if it is worthwhile swapping them (ie. the
absolute difference between oTeam1.TotalScore and oTeam2.TotalScore
reduces). That can give you a refinement (but not neccessarily the
best answer).

For i = 0 To 3

' This is the difference between the team scores

Dim oCurrentDifference As Integer
oCurrentDifference = Abs(oTeam1.TotalScore-oTeam2.TotalScore)

' This is the total score of team 1 if the player is swapped

Dim oTeam1TestScore As Integer
oTeam1TestScore = oTeam1.TotalScore-oTeam1.Player(i).Score + _
oTeam2.Player(i).Score

' This is the total score of team 2 if the player is swapped

Dim oTeam2TestScore As Integer
oTeam2TestScore = oTeam2.TotalScore-oTeam2.Player(i).Score + _
oTeam1.Player(i).Score

' If the players are swapped, this is the new team difference

Dim oTestDifference As Integer
oTestDifference = Abs(oTeam1TestScore-oTeam2TestScore)

' If the difference has improved, swap the players

If oTestDifference < oCurrentDiference Then
Dim oTempPlayer As Player
oTempPlayer = oTeam1.Player(i)
oTeam1.Player(i) = oTeam2.Player(i)
oTeam2.Player(i) = oTempPlayer
End If
Next

I mention this as it's a good way to get very close to a best answer
without using too many resources (and it often gets it). And it gets
better as the number of players (N) increases. Though I do concur with
Mark; there is no reason to avoid a brute-force approach as N is small
in your case.

FYI: One brute force approach is basically as written, but instead you
test for swapping between oPlayer(i) and oPlayer(j). i.e. An
additional loop incrementing an integer value (j) around the whole
lot. See? Easy. You don't need the initial sort, incidentally, as the
ordering and original team membership (and order therein) is
irrelivant.

Now, as you're sorting out player arrangement... how about
facilitating the ability to have two players who like each other being
allocated to the same team, and/or two players who hate each other on
different teams? Trickier... Much tricker... ;)

Rgds,
Click to expand...
 
Here are my thoughts:

First calculate the total score for the 16 people: TotalScore, and then get
the average score for each team: TotalScore/2

Then (not valid code, just Algorithm, and the score are in an array a(15) ):

for i=1 to 15
for j=1 to 15
for k=1 to 15
if i<>j<>k then
distance=abs(a(0)+a(i)+a(j)+a(k)-TotalScore/2)
end if
next
next
next

When you get the min distance, you get the best match.

Luke
Microsoft Online Support

Get Secure! www.microsoft.com/security
(This posting is provided "AS IS", with no warranties, and confers no
rights.)
 
Hi Luke,

I don't understand your method. Why only three loops when there are 16
people and 8 per team?

Regards,
Fergus
 
Hi Kevin,

|| I am a decent programmer, but not an algorithm writer.

I love algorithms - I couldn't resist doing this one!! ;-)

|| I would love a freebie , ..

Have a freebie.

|| but a point in the right direction would work also

which points you in one of the right directions.

|| I would like to eventually pass in a 'PlayerList'

Yep.

|| and get back an array of 2 Player Lists

Actually it'll give all the pairs of teams that reach the best score. You
can then pick one or make a further selection based on some within-team
criteria.

|| Thanks!

You're most welcome and I enjoyed doing it. :-)

Regards,
Fergus
 
Hi Fergus,

Yes, you are right. I ignored the 4 loops in the code. Any other comments
on my algorithm? Your suggestion are welsome.

Regards,

Luke
Microsoft Online Support

Get Secure! www.microsoft.com/security
(This posting is provided "AS IS", with no warranties, and confers no
rights.)
 
Howdy Luke,

In one of my other posts I gave a link to an explanation of permutations
and combinations. Simply put, the permutations are all the possible
arrangements of a set and the combinations are all the <unique> arrangements.

Let's consider N = 4 players (A, B, C and D) and two 2-player teams.

A pair of nested loops (which check that the same player isn't being added
twice) can be used.

for i = A to D
for j = A to D
if i <> j then
'Team 1 is player(i) & player (j) - Team 2 is the others.
next
next

This will give us Team 1's with:
{A, B}, {A, C}, {A, D}
{B, A}, {B, C}, {B, D}
{C, A}, {C, B}, {C, D}
{D, A}, {D, B}, {D, C}

For each i, it will pair up with (N - 1) j's

Now if you look at that you'll notice {A, B} and {B, A}. These are in fact
the same team. And this duplication occurs for each team. The reason this
happens is that the j loop looks 'backwards' as well as forwards. So if i is
on B, j will consider A. But the i loop has already dealt with all the A's.

So this nested loop method generates all the <possible> arrangements. This
doesn't look too serious with just 2 loops as it's only doubling the number of
teams.

Let's look at the maths, though.
For every i, there are (N - 1) j's

That's N x (N - 1) = 4 x 3 = 12

If we add another loop (to make 3-player teams from a set of 4), it's
going to be
N x (N - 1) x (N - 2) = 4 x 3 x 2 = 24

Let's do the 3-player teams by hand and only show the unique teams.
{A, B, C}, {A, B, D}, {A, C, D}
{B, C, D}

That's it. Just the 4. So the nested loop method above generates 24
permutations but there are in fact only 4 unique combinations.

When you get to the 16 player level, the number of possible arrangements
is <huge> - 16 factorial / 8 factorial (16! / 8!) = 16 x 15 x 14 x ... 10 x 9
= about half a billion.

The number of combinations, however, is a mere 12870.

These can be generated by a minor but important change to the nested for
loops. Remember that the problem was j looking backwards? Here's the correct
form where it only looks forwards:

for i = A to D - 1
for j = i + 1 to D
'Team A is player(i) & player (j) - Team B is the others.
next
next

[This is the same form as the loop in Selection Sort.]

This now gives us the following
{A, B}, {A, C}, {A, D}
{X, X}, {B, C}, {B, D}
{X, X}, {X, X}, {C, D}
{X, X}, {X, X}, {X, X}
where (X, X) is an arrangement that has been skipped.

In practice, nested loops are rarely used - due to the team housekeeping
that must be done, plus the fact that each loop being hard-coded makes it
non-scalable.

The solution is recursion whereby you assign each player to a team and
then generate all the combinations of the <succeeding> players in a team one
smaller.

So, with the 3-player teams:

Generate all the 3-player teams from {A, B, C, D)
Put player A into the team.
Generate all the 2-player teams from {B, C, D)
| Add player B into the team.
| Generate all the 1-player teams from {C, D)
| | Add player C into the team.
| | Output team. {A, B, C}
| | Remove C
| | Add player D into the team.
| | Output team. {A, B, D}
| | Remove D
| Remove B
| Add player C into the team.
| Generate all the 1-player teams from {D)
| | Add player D into the team.
| | Output team. {A, C, D}
| | Remove D
| Remove C
Remove A
Put player B into the team.
Generate all the 2-player teams from {C, D)
| Add player C into the team.
| Generate all the 1-player teams from {D)
| | Add player D into the team.
| | Output team. {B, C, D}
| | Remove D
| Remove C
Remove B

I don't know if you've seen the solution (ie. a zipped VB Solution) that I
posted, but it shows the above in action. Perhaps that's going too far, lol
and you have enough to chew on here! ;-))

[Oops - I've just discovered that I <didn't post> the solution!! LOL - I'd
better do that now.]

Regards,
Fergus

Permutations and Combinations - the maths of.
http://engineering.uow.edu.au/Courses/Stats/File2417.html
 
Hi Derian,

Lol, thank you, kind sir! :-)

Regards,
Fergus

[Now, if someone'll just hire me...]
 
THANKS!

And, you are Hired! But the project is on hold. (I hear that all the time)

Kevin (aka 'a')
 
Back
Top