Sorting through a group of numbers based on sum with Javascript

Question

I was presented with the below problem and I am not sure how to go about it due to the grid laylout and inexperience with math functions.

Write a function to create permutations from the following set of numbers such that the sum of three or less numbers equals to 1 or 2 or 3 or 4 or 5. Then group the permutations based on their sums. For example:

[z,b];[y,a];[x,a];... belong to the permutation set 1

[z,b][y,a];[z,e];[y,a][x,a].... belong to the permutation set 2

   a, b, c, d, e
 z 3, 1, 5, 4, 2
 y 1, 3, 2, 5, 4
 x 1, 4, 3, 5, 2
 w 3, 2, 5, 1, 4
 v 4, 1, 5, 2, 3
 u 3, 2, 4, 5, 1
 t 1, 5, 4, 2, 3
 s 5, 2, 1, 4, 3
 r 5, 3, 2, 4, 1
 q 5, 3, 4, 1, 2

The sum of 3 or fewer numbers is either 1,2,3,4 or 5

For example: [z,a]=>3 [z,b]=>1 + [z,e]=>2 = 3

So, [ [[z,a]], [[z,b],[z,e]] ] is a sample solution set of a permutation of elements whose sum is 3. Also, each of the sets in the solution set contains 3 or fewer elements.

Group the permutations based on their sum From the above example, [ [[z,a]], [[z,b],[z,e]] ] is a permutation set of elements whose sum is 3.

Similarly, there will be more elements in the permutation set of elements whose sum is 3. Also, there will be permutation sets of elements whose sum is either 1,2,4 or 5.

inexperience with math functions. It's not really a maths problem, unless you don't know what a+b+c means.. :) — Keith
– Keith, Commented Jul 17, 2018 at 12:04
I haven't been able to do much code wise since I didn't know how to approach the grid values. For instance I tried putting the numbers of each row in their own object in one big array and then sort them through ascending but I have no idea how to approach the different combinations and handle the sorting. — jsnoobie
– jsnoobie, Commented Jul 17, 2018 at 12:27

Keith · Accepted Answer · 2018-07-17 13:56:44Z

1

Rather than been a math's problem, this is more an coding problem.

Below I've first flattered your array, this just makes it easier for the looping. And then when I want the labels, I just get that by working it out by the index.

After doing this, I've just created a multi-level loop,.. This will iterate every combination 50*50*50, 125000 combinations, at each level it does a check, combination 1, combination with 2, etc. There is also a check to make sure it doesn't duplicate the indexes, eg. 1 1 1, is invalid.

The forEach part is just first looping the inputs, it then passes the value, and what indexes made up that value into the check function. Within this forEach, it does another forEach for the 2nd number, and so forth. So what you end up with on the first 3 samples (excluding dups) would be -> 3 [0], 3 + 1 [0, 1], 3 + 1 + 5 [0,1,2] So this would then get 3:za 4:[za,zb], the last would be skipped as that equals 9.

The if (l1ix <= l0ix) return; is just to make sure we don't get duplicates,.. eg. [za,zb] and [zb,za] are classed as the same, this works as I'm making sure the next level index is always greater than the previous levels index.

Below is an example snippet.

const input = [
 3, 1, 5, 4, 2  ,
 1, 3, 2, 5, 4  ,
 1, 4, 3, 5, 2  ,
 3, 2, 5, 1, 4  ,
 4, 1, 5, 2, 3  ,
 3, 2, 4, 5, 1  ,
 1, 5, 4, 2, 3  ,
 5, 2, 1, 4, 3  ,
 5, 3, 2, 4, 1  ,
 5, 3, 4, 1, 2];
 

const topLabels = "abcde";
const sideLabels = "zyxwvutsrq";
 
function labelForPos(p) {
  return {
    top: topLabels[p % 5],
    side: sideLabels[Math.trunc(p / 5)]
  }
}

const members = {
  1: [],
  2: [],
  3: [],
  4: [],
  5: []
};

function check(sum, ixlist) {
  //make sure all are unique indexes
  if ((new Set(ixlist)).size !== ixlist.length) return;
  if (sum >= 1 && sum <= 5) { 
    members[sum].push("[" +
      ixlist.map(ix => {
        const lb = labelForPos(ix);
        return `[${lb.side},${lb.top}]`;
      }).join(",") + "]"
    );
  }
}


input.forEach((l0, l0ix) => {
  check(l0, [l0ix]);
  input.forEach((l1, l1ix) => {
    if (l1ix <= l0ix) return;
    check(l0 + l1, [l0ix, l1ix]);
    input.forEach((l2, l2ix) => {
      if (l2ix <= l1ix) return;
      check(l0 + l1 + l2, [l0ix, l1ix, l2ix]);
    });
  });
});


Object.entries(members).forEach(([key, v]) => {
  console.log(`${key} (${v.length}) = [${v.join(", ")}]`);
});

edited Jul 17, 2018 at 13:56

answered Jul 17, 2018 at 12:44

Keith

24.4k2 gold badges32 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jsnoobie Over a year ago

Thank you, I didn't realize that the combinations would be this extensive! I understand the checks you've done for the sum but could you explain the what the forEach function is doing for the values?

Keith Over a year ago

@jsnoobie Updated answer with what the forEach is doing, hope that makes sense..

Collectives™ on Stack Overflow

Sorting through a group of numbers based on sum with Javascript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related