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