8

I've came across the following problem statement.

You have a list of natural numbers of size N and you must distribute the values in two lists A and B of size N/2, so that the squared sum of A elements is the nearest possible to the multiplication of the B elements.

Example: Consider the list 7 11 1 9 10 3 5 13 9 12.
The optimized distribution is:
List A: 5 9 9 12 13
List B: 1 3 7 10 11
which leads to the difference abs( (5+9+9+12+13)^2 - (1*3*7*10*11) ) = 6
Your program should therefore output 6, which is the minimum difference that can be achieved.

What I've tried:

I've tried Greedy approach in order to solve this problem. I took two variables sum and mul. Now I started taking elements from the given set one by one and tried adding it in both the variables and calculated current square of sum and multiplication. Now finalize the element in one of the two sets, such that the combination gives minimum possible value.

But this approach is not working in the given example itselt. I can't figure out what approach could be used here.

I'm not asking for exact code for the solution. Any possible approach and the reason why it is working, would be fine.

EDIT:

Source: CodinGame, Community puzzle

Kaushal28
  • 5,377
  • 5
  • 41
  • 72
  • What problem do you encounter with your approach? – Adriaan Koster Jun 12 '17 at 14:41
  • How about get all the possible combinations of size n/2 (here is an example https://stackoverflow.com/questions/2201113/combinatoric-n-choose-r-in-java-math) for each combination calculate sqrSum and product put all the results in one collection go over it at some point you will see sqrtSum and product as neighbors find the pair with the smallest difference – urag Jun 12 '17 at 14:54
  • 2
    @urag It's worth noting that will take exponential time - if n is even as small as around 50, you'd going to have problems. Usually the exponential time brute-force solution is obvious for problems like these, the key is to find a smarter way of solving the problem. – Bernhard Barker Jun 12 '17 at 15:25
  • @urag yes. Your algo. will have exponential time. Isn't it possible to solve in some polynomial time algo ? – Kaushal28 Jun 12 '17 at 15:29
  • @AdriaanKoster the difference is not always minimum in my approach. – Kaushal28 Jun 12 '17 at 15:29

2 Answers2

1

Try out this: 

import java.util.Arrays;

public class Test {

    public static void main(String [] args){
        int [] arr = {7, 11, 1, 9, 10, 3, 5, 13, 9, 12}; 
        int [][] res = combinations(5, arr);
        int N = Arrays.stream(arr).reduce(1, (a, b) -> a * b);
        int min = Integer.MAX_VALUE; 
        int [] opt = new int [5];
        for (int [] i : res){
            int k = (int) Math.abs( Math.pow(Arrays.stream(i).sum(), 2) - N/(Arrays.stream(i).reduce(1, (a, b) -> a * b)));
            if(k < min){
                min = k;
                opt = i;
            }
        }
        Arrays.sort(opt);
        System.out.println("minimum difference is "+ min + " with the subset containing this elements " + Arrays.toString(opt));
    }

    // returns all k-sized subsets of a n-sized set 
    public static int[][] combinations(int k, int[] set) {
        int c = (int) binomial(set.length, k);
        int[][] res = new int[c][Math.max(0, k)];
        int[] ind = k < 0 ? null : new int[k];
        for (int i = 0; i < k; ++i) { 
            ind[i] = i; 
        }
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < k; ++j) {
                res[i][j] = set[ind[j]];
            }
            int x = ind.length - 1;
            boolean loop;
            do {
                loop = false;
                ind[x] = ind[x] + 1;
                if (ind[x] > set.length - (k - x)) {
                    --x;
                    loop = x >= 0;
                } else {
                    for (int x1 = x + 1; x1 < ind.length; ++x1) {
                        ind[x1] = ind[x1 - 1] + 1;
                    }
                }
            } while (loop);
        }
        return res;
    }
    // returns n choose k; 
    // there are n choose k combinations without repetition and without observance of the sequence
    // 
    private static long binomial(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k > n - k) {
            k = n - k;
        }
        long c = 1;
        for (int i = 1; i < k+1; ++i) {
            c = c * (n - (k - i));
            c = c / i;
        }
        return c;
    }
}

Code taken from this stackoverflow answer, also take a look at this wikipedia article about Combinations.

Jordi Castilla
  • 26,609
  • 8
  • 70
  • 109
Eritrean
  • 15,851
  • 3
  • 22
  • 28
  • Hi! thanks for your time. But unfortunately this is not working. It is giving correct answer for the given example, but no further testcases were passed. I forgot to mention the source of my question. Please see the edits for for other testcases, I'm adding the problem link there. – Kaushal28 Jun 14 '17 at 18:46
0

I am not sure if there is any exact solution in polynomial time. But you could try a simulated annealing based approach.

My approach would be:

  1. Initialize listA and listB to a random state
  2. With probability p run greedy step, otherwise run a random step
  3. Keep track of the state and corresponding error (with a HashMap)

Greedy step: Find one element you can move between the list that optimizes the error.

Random Step: Pick a random element from either of these two sets and calculate the error. If the error is better, keep it. Otherwise with probability of q keep it.

At either of these two steps make sure that the new state is not already explored (or at least discourage it).

Set p to a small value (<0.1) and q could depend on the error difference.

ElKamina
  • 7,747
  • 28
  • 43