For N absolute values ​​of integers, find a combination of N / 2 negative and N / 2 positive values, the sum of which is closest to 0

Question

Let's say that I have an array of 10 numbers, the absolute range of values ​​of which can go from 1 to 10. The values ​​can be repeated. An example of this might be

{2, 4, 2, 6, 9, 10, 1, 7, 6, 3}. 

We can assign a positive or negative sign to each of these numbers, but there should always be 5 negative and 5 positive numbers in each combination, for example

 {-2, -4, 2, -6, 9, 10, 1, 7, -6, -3} {2, -4, -2, 6, -9, 10, -1, 7, -6, 3} 

permutations that follow this rule are possible.

In all possible permutations of the semi-positive and semi-negative values ​​of this set, I would like to find the minimum positive or negative sum whose value is closest to 0.

Any suggestions? I feel that the problem is computationally very intense, and I'm not sure if there is a solution that is not brute force (for example, listing all permutations and then applying a variation of the nearest 3Sum).

Answer 1

Sort the array first, then put the largest number in the negative group and put the second largest in the positive group. set the largest number in a positive group until their sum is greater than zero. Now set another negative number. Repeat it until you set 5 negative values. This is a greedy algorithm. It seems your problem is np-complete, it looks like an AST problem, but the size of your problem is limited to 10, so you can solve it by looking for brute force, you just need to check C (10.5) <10 ^ 5 possibilities and this number is small for today's PCs.

Also, if you could choose a different set size, your problem was the same as the problem with the sum of the subset, which can be solved in pseudo-polynomial time. See: 1 , 2 .

Answer 2

Here is an example in Haskell that lists and compares all 126 possible combinations:

 import Data.List import Data.Ord {-code by Will Ness-} divide :: [a] -> [([a], [a])] divide [] = [([],[])] divide (x:xs) = go ([x],[],xs,1,length xs) where go (a,b,[],i,j) = [(a,b)] go (a,b, s@ (x:xs),i,j) | i>=j = [(a,b++s)] | i>0 = go (x:a, b, xs, i+1, j-1) ++ go (a, x:b, xs, i-1, j-1) | i==0 = go (x:a, b, xs, 1, j-1) ++ go (x:b, a, xs, 1, j-1) {-code by groovy-} minCombi list = let groups = map (\x -> map (negate) (fst x) ++ snd x) (divide list) sums = zip (map (abs . sum) groups) groups in minimumBy (comparing fst) sums 

* Home> minCombi [2, 4, 2, 6, 9, 10, 1, 7, 6, 3]
(0, [- 7, -10, -2, -4, -2,1,9,6,6,3])

Answer 3

This is a java implementation of the algorithm described by amin k.

This is less cool than the Haskell implementation, I have no formal evidence that it works in every case, but it seems to work.

 import java.util.Arrays; import java.util.Random; public class TestPermutations { int[] values = new int[10]; int[] positives = new int[5]; int[] negatives = new int[5]; public static void main(String... args) { new TestPermutations(); } public TestPermutations() { Random ra = new Random(); System.out.println("generating sequence..."); for (int i = 0; i < 10; i++) { values[i] = (ra.nextInt(10) + 1); System.out.print(values[i] + " "); } Arrays.sort(values); int sum = 0; int positiveIndex = 0; int negativeIndex = 0; for (int i = values.length - 1; i >= 0; i--) { if (i == values.length - 1) { negatives[negativeIndex] = - values[i]; negativeIndex++; sum -= values[i]; } else { if (sum <= 0) { if (positiveIndex < 5) { positives[positiveIndex] = values[i]; positiveIndex++; sum += values[i]; } else { negatives[negativeIndex] = - values[i]; negativeIndex++; sum -= values[i]; } } else { if (negativeIndex < 5) { negatives[negativeIndex] = - values[i]; negativeIndex++; sum -= values[i]; } else { positives[positiveIndex] = values[i]; positiveIndex++; sum += values[i]; } } } } System.out.print("\npositives "); for (int pos : positives) { System.out.print(pos + " "); } System.out.print("\nnegatives "); for (int neg : negatives) { System.out.print(neg + " "); } System.out.println("\nsum closest to 0: " + sum); } } 

Answer 4

Have you tried to calculate the differences? That is: Take the first number. Find the value with the smallest difference and sum. Continue to the end. In the worst case, the Algorithm is O (n ^ 2) complexity, which is not entirely desirable, but it is a starting point

Answer 5

Welcome to the world of NP-class problems!

You can calculate the optimal solution using bruteforce or try a laid-back approach (for example, a simplex algorithm) that will bring you a solution in polynomial time according to the complexity of the average case