I am trying to find the optimal way to sort a collection of integers into bins that all have the same sum. For simplicity we can subtract the average so we are only interested in bins that add to zero. Take for example, X = np.array([-2368, -2143, -1903, -1903, -1888, -1648, -1528, -1318, -1213, -1153, -1033, -928, -793, -703, -508, -493, -463, -448, -418, -358, -223, -118, -88, 137, 227, 257, 347, 347, 377, 557, 632, 632, 692, 812, 827, 1007, 1022, 1262, 1352, 1727, 1892, 2267, 2297, 2327, 2642]) I know, there exists a way for this to form 3 groups of 15 numbers each, where each group adds to zero. But for the life of me, it is not obvious how to systematically find that solution (there could be many such solutions, I only need one). In this smaller example, we could probably just try every combination, but if the array had a million numbers being split into 1000 bins, such an exhaustion would not work. Continue reading...
