CODEWITHSUNDEEP
javascriptalgorithm
Guido
Guido

Reputation: 319

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

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.

Upvotes: 5

Views: 3557

Answers (2)

RobG
RobG

Reputation: 147363

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]

Upvotes: 0

Travis J
Travis J

Reputation: 82267

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);

Upvotes: 4

Related Questions