Algorithm for Grouping Numbers (Making Teams)

[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!

[MSFT]

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.)

[a]

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
"MSFT" <lu******@online.microsoft.com> wrote in message
news:wR*************@cpmsftngxa06.phx.gbl...

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.)

[Mark Hurd]

a wrote:

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

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.

--
Regards,
Mark Hurd, B.Sc.(Ma.) (Hons.)

[Fergus Cooney]

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/Course.../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!! ;-)

[a]

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" <fi******@tesco.net> wrote in message
news:%2****************@TK2MSFTNGP10.phx.gbl...

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/Course.../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!! ;-)

[Richard L Rosenheim]

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
"a" <[e-mail]> wrote in message news:ew**************@TK2MSFTNGP11.phx.gbl...

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!

[_Andy_]

On Wed, 1 Oct 2003 23:40:15 +0930, "Mark Hurd"
<ma******@ozemail.com.au> wrote:

a wrote:

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

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...)

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,

[a]

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_" <wi******@nospamthanks.gov> wrote in message
news:m5********************************@4ax.com...

On Wed, 1 Oct 2003 23:40:15 +0930, "Mark Hurd"
<ma******@ozemail.com.au> wrote:

a wrote:

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

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 rulesof 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...)

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,

[Fergus Cooney]

Hi Kevin,

Which approach do you want to take?

Regards,
Fergus

[MSFT]

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.)

[Fergus Cooney]

Hi Luke,

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

Regards,
Fergus

[Fergus Cooney]

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

[MSFT]

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.)

[derian]

fergus, you are quite gifted!

"Fergus Cooney" <fi******@tesco.net> wrote in message
news:uU**************@TK2MSFTNGP09.phx.gbl...

Hi Kevin,

My apologies.

There I was waxing lyrical and I forgot to post the solution!!

Here it is. :-)

Regards,
Fergus

[Fergus Cooney]

Hi Derian,

Lol, thank you, kind sir! :-)

Regards,
Fergus

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

[a]

THANKS!

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

Kevin (aka 'a')
"Fergus Cooney" <fi******@tesco.net> wrote in message
news:uU**************@TK2MSFTNGP09.phx.gbl...

Hi Kevin,

My apologies.

There I was waxing lyrical and I forgot to post the solution!!

Here it is. :-)

Regards,
Fergus