N-fold partitioning of an array with equal sum in each section

Question

For an array of integers a , two numbers N and M , we return the N group of integers from a , so that each group is summed with M

For example, say:

• a = [1,2,3,4,5]
• N = 2
• M = 5

Then the algorithm can return [2, 3], [1, 4] or [5], [2, 3] or, possibly, others.

What algorithms can I use here?

Edit:

I did not know that this NP problem is complete. Therefore, perhaps this will help if I provided more detailed information about my specific scenario:

So, I'm trying to create a match-up application. Given the number of teams N and the number of players in team M , the application listens for customer requests. Each client request will give the number of players that the client represents. Therefore, if I need 2 teams of 5 players, then if 5 clients send requests, each of which represents 1, 2, 3, 4, 5 players, respectively, then my application should generate a match between clients [1, 4] and clients [2, 3] , It can also create a match between [1, 4] and [5] ; I do not care.

One of the consequences is that any client representing more than M or less than 0 players is invalid. Hope this simplifies the problem.

Answer 1

Here is my own Python solution that uses dynamic programming. The algorithm is given below here .

 def get_subset(lst, s): '''Given a list of integer `lst` and an integer s, returns a subset of lst that sums to s, as well as lst minus that subset ''' q = {} for i in range(len(lst)): for j in range(1, s+1): if lst[i] == j: q[(i, j)] = (True, [j]) elif i >= 1 and q[(i-1, j)][0]: q[(i, j)] = (True, q[(i-1, j)][1]) elif i >= 1 and j >= lst[i] and q[(i-1, j-lst[i])][0]: q[(i, j)] = (True, q[(i-1, j-lst[i])][1] + [lst[i]]) else: q[(i, j)] = (False, []) if q[(i, s)][0]: for k in q[(i, s)][1]: lst.remove(k) return q[(i, s)][1], lst return None, lst def get_n_subset(n, lst, s): ''' Returns n subsets of lst, each of which sums to s''' solutions = [] for i in range(n): sol, lst = get_subset(lst, s) solutions.append(sol) return solutions, lst # print(get_n_subset(7, [1, 2, 3, 4, 5, 7, 8, 4, 1, 2, 3, 1, 1, 1, 2], 5)) # [stdout]: ([[2, 3], [1, 4], [5], [4, 1], [2, 3], [1, 1, 1, 2], None], [7, 8]) 

Answer 2

this seems to be a variation of the problem of summing a subset. since this problem is np-complete, there will be no efficient algorithm without additional restrictions.

note that it is already difficult to find one subset of the original set whose elements are summed up to M

Answer 3

People too easily give up NP-complete problems. Just because the NP problem is complete does not mean that in the general case there are no more efficient algorithms. That is, you cannot guarantee that for all inputs there is an answer that can be calculated faster than brute force search, but for many problems you probably have methods that are faster than a full search for most inputs.

For this problem, there are certainly “perverted” sets of numbers that will lead to the worst search time, because you can say that there is a large vector of integers, but only one solution, and you should end up trying a very large number of combinations.

But for naughty sets, there are probably many solutions, and an effective way to “topple” over a good split will work much faster than NP time.

How you decide this will depend on what you expect from more general options. It also matters if the integers are positive or negative values ​​are allowed.

In this case, I will assume that:

• N is small with respect to the length of the vector
• All integers are positive.
• Integers cannot be reused.

Algorithm:

• Sorting a vector, v.
• Eliminate items in excess of M. They cannot be part of any solution.
• Add all the remaining numbers to v, divide them by N. If the result is less than M, there is no solution.
• Create a new array w, whose size is v. For each w [i] we summarize all the numbers in v [i + 1 - end]

So, if v were 5 4 3 2 1, w would be 10, 6, 3, 1, 0.

Until you find enough sets:

• Choose the largest number, x, if it is equal to M, emits a set of solutions with only x and removes it from the vector, remove the first element from w.

Still not enough sets? (probably), then again until you find enough sets:

• The solution theory is ([a, b, c], R), where [a, b, c] is a partial set of elements v and the remainder R. R = M-sum [a, b, c]. Extension of the theory - adding a number to a partial set and subtracting this number from R. As theories expand, if R == 0, this is a possible solution.

Create theories recursively: iterate over elements v, like v [i], creating theories, ([v [i]], R), and now recursively expand each theory from one part of v. Binary search in v to find the first element equal to or less than R, v [j]. Start with v [j] and continue each theory with elements v from j, until R> w [k].

The numbers v [j] to v [k] are the only numbers that are used to expand the theory and still get R to 0. Numbers larger than v [j] will make R negative. Less than v [k], and more numbers are left in the array, even if you used all of them to get R to 0