Find combinations of closest sums of an array's subsets

yvzyvz 0
Viewed 25

Say, I have a set of numbers that always has an even count. i.e. num=[2,4,6,10,8,7,4,5], 8 numbers.

I want to find all possible combinations of two subset of these numbers (using each of them) that have equal count (4 each), and have the closest possible sum - equal sum if achievable .

For example:

a1 = 10 + 2 + 6 + 4 = 22

b1 = 8 + 7 + 4 + 5 = 24,

a2 = 10 + 6 + 5 + 2 = 23

b2 = 7 + 4 + 8 + 4 = 23,

. . .

I looked up some other questions that were asked, but they did not have these constraints in them. In Excel, I am using ''solver'' to solve this and I m wondering if it could be solved in python.

combinations sum arrays
1 Answers

Oh I don't know about complexity (probably O(n2) or worse) but I solved it using recursion, covering all options. I hope.

It loops twice over the original list, taking each pair of numbers then pushing it to the result of the same process without that pair. Eventually it will cover all options so just checking the difference each time, saving the minimal for the result.

This program finds a smallest sum diff partition, but it might as well return all combinations.

var arr = [2, 4, 6, 10, 8, 7, 4, 71]


function sum(arr) {
  return arr.reduce((p, c) => p + c, 0)
}

console.log(split_2(arr))

function split_2(arr) {
  if (arr.length == 2) {
    return [
      [arr[0]],
      [arr[1]]
    ];
  }
  var original = [...arr];

  var best = Infinity;
  var result = [];
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = i + 1; j < arr.length; j++) {
      var b = arr.splice(j, 1);
      var a = arr.splice(i, 1);
      var min = Math.min(a, b);
      var max = Math.max(a, b);

      var [s1, s2] = split_2(arr);
      if (sum(s1) < sum(s2)) {
        s1.push(max)
        s2.push(min)
      } else {
        s1.push(min)
        s2.push(max)
      }
      var diff = Math.abs(sum(s1) - sum(s2));
      if (diff < best) {
        best = diff;
        result = [s1, s2];
        if (diff == 0) {
          return result;
        }
      }
      arr = original;
    }
  }

  return result;

}

IT goldman0
Related