2
$\begingroup$

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.

  • 0
    Is there a limit to the number of players? What about the skill rating values?2012-04-30
  • 0
    Range of number of players: 4 to 8, Range of skill: 0 to 10.2012-04-30
  • 3
    If I am not mistaken this is related to the knapsack problem. http://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.2012-04-30
  • 0
    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.2012-04-30
  • 0
    Also lookup subset sum problem.2012-04-30
  • 0
    Each team has to be of 4 players? if not you can use the algorithm describe on video 7 [here](http://people.csail.mit.edu/bdean/6.046/dp/)..2012-05-04

1 Answers 1

2

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.

  • 0
    Ok, what about if there are 5, 6, 7, or 8 players?2012-04-30
  • 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.2012-04-30
  • 0
    @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.2012-04-30
  • 0
    Oh ok Austin, I never thought of it like that, I saw it as 8! combinations, or some 46,000 total. Thanks a lot.2012-05-01