Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I am given eight numbers: 10, 8, 8, 7, 6. 5, 5, 4

I am told to divide the group of numbers in to two different groups, four numbers each. What formula or method is there for running every possible combination of numbers possible, and in the end output two groups who's numbers' sum is even or as close as possible.

I am looking for an algorithm for an Android application I am developing. The user inputs the names and skill of each player playing in a game of the users choice. The application will read the inputs and list the best combination of players so that the teams are as fair as possible for the given skill levels. Please let me know if you have any questions or need any more information. Thank you.

share|improve this question
    
Is there a limit to the number of players? What about the skill rating values? –  Aryabhata Apr 30 '12 at 21:45
    
Range of number of players: 4 to 8, Range of skill: 0 to 10. –  Jonah Apr 30 '12 at 21:46
3  
If I am not mistaken this is related to the knapsack problem. en.wikipedia.org/wiki/Knapsack_problem and thus NP-complete. A lot of algorithms give decent results though and with a small enough set (8players?) you could even try every reasonable possibility by brute force. –  example Apr 30 '12 at 21:51
    
Thank you for the link to the Knapsack Problem, I have never heard of that. Do you have any idea how I could come up with a set formula for this? Since this will be applied to a computer program, I cannot sit and manually work each scenario out on paper. –  Jonah Apr 30 '12 at 21:59
    
Also lookup subset sum problem. –  Aryabhata Apr 30 '12 at 22:51

1 Answer 1

If you want to run all possible combinations, there are ${n \choose n/2}=\frac {n!}{((n/2)!)^2}$ of them. Some bounds are given in Wikipedia. If you generate the combinations, one approach is given here. You start with the first n/2 as the first combination, then move the last element one later until you can't any more, move the next to last one later and the last as early as possible, and so on.

A heuristic that will often get you close is to assign the highest to group 1, the second and third to group 2, the fourth and fifth to group 1, etc. Much less work and maybe close enough.

share|improve this answer
    
Ok, what about if there are 5, 6, 7, or 8 players? –  Jonah Apr 30 '12 at 21:54
2  
You could, without loss of generality, assign some player to team 1. You only need to look at the number of ways to complete team 1. For example, with 8 players, you would need to check $\binom{7}{3} = 35$ collections of teammates for the fixed player on team 1. This is very reasonable computationally. –  Austin Mohr Apr 30 '12 at 22:04
    
@Jonah: If there are no more than 8, the compute load is very small. If there is an odd number, do you want the totals equal as possible or the average? These are different. –  Ross Millikan Apr 30 '12 at 22:55
    
Oh ok Austin, I never thought of it like that, I saw it as 8! combinations, or some 46,000 total. Thanks a lot. –  Jonah May 1 '12 at 1:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.