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******@onlin e.microsoft.com > wrote in message
news:wR******** *****@cpmsftngx a06.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******** ********@TK2MSF TNGP10.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******** ******@TK2MSFTN GP11.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******@ozema il.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 oSortedPlayerCo llection

' If either team is full, fill the other team

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

' Put the player in the team with the lowest total

ElseIf oTeam1.TotalSco re < oTeam2.TotalSco re Then
oTeam1.Add(oPla yer)
Else
oTeam2.Add(oPla yer)
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.TotalSco re and oTeam2.TotalSco re
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 oCurrentDiffere nce As Integer
oCurrentDiffere nce = Abs(oTeam1.Tota lScore-oTeam2.TotalSco re)

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

Dim oTeam1TestScore As Integer
oTeam1TestScore = oTeam1.TotalSco re-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.TotalSco re-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(oTeam1TestS core-oTeam2TestScore )

' If the difference has improved, swap the players

If oTestDifference < oCurrentDiferen ce 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******@nospa mthanks.gov> wrote in message
news:m5******** *************** *********@4ax.c om...

On Wed, 1 Oct 2003 23:40:15 +0930, "Mark Hurd"
<ma******@ozema il.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 oSortedPlayerCo llection

' If either team is full, fill the other team

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

' Put the player in the team with the lowest total

ElseIf oTeam1.TotalSco re < oTeam2.TotalSco re Then
oTeam1.Add(oPla yer)
Else
oTeam2.Add(oPla yer)
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.TotalSco re and oTeam2.TotalSco re
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 oCurrentDiffere nce As Integer
oCurrentDiffere nce = Abs(oTeam1.Tota lScore-oTeam2.TotalSco re)

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

Dim oTeam1TestScore As Integer
oTeam1TestScore = oTeam1.TotalSco re-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.TotalSco re-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(oTeam1TestS core-oTeam2TestScore )

' If the difference has improved, swap the players

If oTestDifference < oCurrentDiferen ce 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