given N absolute values of integers find the combination of N/2 negative and N/2 positive values whose sum is closest to 0

Question

Let's say that I have an array of 10 numbers whose absolute value range can go from 1 to 10. Values can be repeated. An example of this could be

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

To each of these numbers we can assign a positive or negative sign, but there should be always 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}

are possible permutation that follow this rule.

I would like to find, in all the possible permutations of half-positive and half-negative values of the given set, the minimum positive or negative sum whose value is closest to 0.

Any suggestions? I feel that the problem is computationally very intensive and I'm not sure there is a solution that is not a brute force one (for example enumerating all the permutations and then applying a variation of the 3Sum closest).

Answer 1

First sort the array, then put the biggest number into negative group and put Second-biggest into positive group. set a biggest number into positive group until sum of them is more than zero. Now set an other negative number.repeat it until you set 5 negative. This is greedy algorithm. Seems your problem is np-complete, it looks like AST problem but, size of your problem is limited to 10, so you can solve it by brute force search, you just have to check C(10,5)<10^5 possibilities and this number is small for today PCs.

Also if was able to choose different size of sets, your problem was same as subset sum problem which can be solve in pseudo-polynomial time See it :1 , 2.

Answer 2

Here's 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

*Main> 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.

It's less cool than the Haskell implementation, I have no formal proof that it works in every case, but it seems to be working.

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 computing differences? Ie: Take the first number. Find the value with the lowest difference, and sum. Continue until finished. In the worst case, the Algorithm is O(n^2) complexity, which isn't exactly desirable but it's a starting point

Answer 5

Welcome to the world of the NP-class problems!

You can compute the optimal solution by bruteforce or trying a relaxed approach (like the simplex algorithm) which will bring you the solution in polinomial time on the average-case complexity