Javascript, all possible sums of an array members (up to 4)

Question

I am unable to figure out how to write a function that will calculate all possible sums of of the elements of an array, with a max of 4 elements per addition.

Given

x = [1, 32, 921, 9213, 97, 23, 97, 81, 965, 82, 965, 823]

I need to go from (1+32) ~ (965+823) to (1+32+921+9213) ~ (965+82+965+823), calculating all the possible sums.

The output should be an array like this:

{33: [1, 32], 922: [1, 921], .... 2835: [965, 82, 965, 823]}

filled by all the possible sums.

It's not for homework, and what I was looking for is explained down there by Travis J: it was about permutations. Thanks everybody, I hope this could be useful also to someone else.

@TravisJ—I think you mean combinations. Addition doesn't care about order. ;-) — RobG, Dec 19 '14 at 00:09
Spend some time thinking about how you would do this problem with pencil and paper, working systematically. — Pointy, Dec 19 '14 at 00:12
@KyleMuir I did some test with Python (on which I'm most familiar), trying to build a recursive function that increase the list indexes, but I haven't gone so far. — Guido, Dec 19 '14 at 00:12
@RobG - Agree about the order, but part of a recursive permutation is the ability to choose a subset, and permutation algorithms lend themselves to not repeating very easily. Technically, the term combinations does fit here more than permutations, but the permutation algorithm is what will get this done. — Travis J, Dec 19 '14 at 00:14
The answer to [*Get all combinations of elements in array*](http://stackoverflow.com/questions/20583801/get-all-combinations-of-elements-in-array/20583875#20583875) gives some hints, even though the question is closed. There is also [*Get all the combinations of N elements of multidimensional array*](http://stackoverflow.com/questions/18233874/get-all-the-combinations-of-n-elements-of-multidimensional-array). — RobG, Dec 19 '14 at 00:14
Thank you @RobG I already did the "up to 2 members" function, I haven't found the way to go further — Guido, Dec 19 '14 at 00:16
Do you just want all possible sums? Or, do you want to know the number of combinations that produced each sum also? — jfriend00, Dec 19 '14 at 00:16
@RobG - See below for an implementation of a permutation subset. — Travis J, Dec 19 '14 at 00:48
The way you've described it you're looking for all possible sums of *consecutive* numbers up to 4 consecutive numbers; and that's pretty easy. — Ja͢ck, Dec 19 '14 at 00:49
@TravisJ solved the problem. I have added more explanations, because the question was closed as unclear: I hope the details I've added would be enough to reopen it. — Guido, Feb 07 '15 at 13:25

score 4 · Accepted Answer · answered Dec 19 '14 at 00:41

4

jsFiddle Demo

You can use a permutation subset recursive algorithm to find the set of all of the sums and also their combinations.

var x = [1, 32, 921, 9213, 97, 23, 97, 81, 965, 82, 965, 823];
var sums = [];
var sets = [];
function SubSets(read, queued){
 if( read.length == 4 || (read.length <= 4 && queued.length == 0) ){
  if( read.length > 0 ){
   var total = read.reduce(function(a,b){return a+b;},0);
   if(sums.indexOf(total)==-1){
    sums.push(total);
    sets.push(read.slice().sort());
   }
  }
 }else{
  SubSets(read.concat(queued[0]),queued.slice(1));
  SubSets(read,queued.slice(1));
 }
}
SubSets([],x);
console.log(sums.sort(function(a,b){return a-b;}));
//log sums without sort to have them line up to sets or modify previous structure
console.log(sets);

answered Dec 19 '14 at 00:41

Travis J

81,153
41
202
273

That doesn't seem to get the right number of combinations (or maybe I'm calculating them incorrectly). The general formula for combinations of *k* members of a population of *n* is given by: `n! / (( n - k)! * k!)`. Summing for n = 12 and k = 2 to 4 gives 781, the above gives 426 results. There are 495 combinations where k = 4. Have I missed something (very probably I have)? – RobG Dec 19 '14 at 01:40
@RobG - I believe your number may be correct for a unique set. However, this set included duplicate numbers. Moreover, since there were additions, it included duplicate totals. I had both of those removed and that is what led to the smaller number. So I think your math is probably accurate for the domain described. – Travis J Dec 19 '14 at 05:22
@TravisJ—if all combinations are summed, then duplicate values removed, there are 418 remaining. If duplicates are removed first (97, 965), then duplicate results also removed, there are 334 remaining. Dups removed using: `arr.sort(function(a, b){return a-b}).filter(function(v, i){return !i || v != arr[i-1]});`. – RobG Dec 19 '14 at 07:48
The initial idea was to compare results of the additions with the members of a second array, and return the matching sets, if equal. Accomplished, thanks to this code, in a blazing fast way. This means I doesn't care about duplicates. Also, it's usable on a small set of data (up to 10 or so), and I had to apply some filters to reduce the array size, cause the initial array length is 60 ~ 90 members, and turned out it needs too much computing power. Everything worked like a charm and I really have to say thank you. – Guido Dec 19 '14 at 10:41
@TravisJ—Ah, the difference is that you are summing 1 to 4 terms, I was summing 2 to 4 (since summing single terms didn't make any sense to me). – RobG Dec 20 '14 at 00:24
@user3699166—in terms of speed, TravisJ's answer is less code (and he created it pretty quickly), but the algorithm at GitHub is much faster in terms of performance (see [*http://jsperf.com/sum-combinations*](http://jsperf.com/sum-combinations)) and is also general. – RobG Dec 20 '14 at 00:26

score 0 · Answer 2 · answered Dec 19 '14 at 02:30

There is a function to generate combinations of k members of a population of n here: https://gist.github.com/axelpale/3118596.

I won't reproduce the function here. You can combine it with another function to sum the combinations generated from an input array, e.g.

// Add combinations of k members of set
function getComboSums(set, k) {
  return k_combinations(arr, n).map(function(a){
    var sum=0;
    a.forEach(function(v){sum += v})
    return sum;
  });
}

This can be combined with another function to get all combinations from 2 to 4 and concatenate them all together. Note that the total number of combinations in a set of 12 members is 781.

// Add all combinations from kStart to kEnd of set
function getComboSumRange(set, kStart, kEnd) {
  var result = [];
  for (var i=kStart; i <= kEnd; i++) {
    result = result.concat(getComboSums(set, i));
  }
  return result;
}

Then given:

var arr = [1, 32, 921, 9213, 97, 23, 97, 81, 965, 82, 965, 823];

console.log(getComboSumRange(arr, 2, 4)) // length is 781

The length of 781 agrees with the calculated number of terms based on the formula for finding combinations of k in n:

n! / (k!(n - k)!)

and summing for k = 2 -> 4.

The result looks like:

[33, 922, 9214, 98, 24, 98 ...  2834, 1951, 2835];

You can see the terms start with:

arr[0] + arr[1], arr[0] + arr[2]], ...

and end with:

... arr[7] + arr[9] + arr[10] + arr[11], arr[8] + arr[9] + arr[10] + arr[11]

Javascript, all possible sums of an array members (up to 4)

2 Answers2

Linked