Algorithm to find all combination from an array of objects

user_6690145 0
Viewed 56

Recently a friend of mine proposed to solve a simple problem and I'm struggle to find the best algorithm to solve it.

There's a list of athletes, every athlete has a name, a weight and can have multiple roles, at least 1 maximum 3 ( Internal, Median and External ). A team is composed by 6 athletes ( 2 internals, 2 medians and 2 externals ). There is also a weight limit which is at 540kg.

What is the best algorithm to find all possible combination for this problem?

Right now I find all combination iterating through the list of athletes, all of its roles and removing all combinations that overpass a limit.

Do you have any better algorithm to solve this problem? What is the best method to approach a problem like this in order to solve it?

Thank you

combinations time-complexity algorithm
1 Answers

What is the best algorithm to find all possible combination for this problem?

In the worst case, where you have n >= 6 athletes, each weighing so little that the limit doesn't matter, and each able to play all roles, the number of teams grows very, very quickly, even if you don't want to multiply-count the teams that have the same set of players assigned to different roles.

The exact number in this case is "n choose 6" or:

n * (n - 1) * (n - 2) * (n - 3) * (n - 4) * (n - 5) / 720

This is an O(n6) problem. This is going to be slow no matter what if n is larger than, like, 30. Once n > 123, the quantity won't fit in an unsigned 32-bit integer anymore.

If the team size can vary, then the problem is O(nk), where k is the team size. This is no longer polynomial; in fact, it's harder than NP-Complete. It would be able to enumerate solutions to the Knapsack Problem, which is ♯P complete.[1]

Thus, this is an engineering problem more than it is an algorithms problem.

Right now I find all combination iterating through the list of athletes, all of its roles and removing all combinations that overpass a limit.

This is pretty much what I would do, only you can make it somewhat more efficient by pruning partial teams as early as possible. Here are some ideas I had:

  1. Sort the list of athletes by weight so that when you go over the weight limit, you can stop looking at the later athletes in the list.
  2. Keep track of how many roles have a possible athlete to fulfill them, given the partial team. When you reach the fifth member, you know the athlete must have a role in one of the shorthanded roles.
    1. For example, if you have a team of four athletes so far with no median players, you must only consider median players for the next two.
    2. To make this easier, create (sorted) auxiliary lists for each role that contain pointers to the players that can have that role.
user_21379960
Related