Algorithm - Combinations, of Four, and Sum

Using sequence: 1, 2, 3, 4, 5

I was looking for combinations of:

One
Two
Three
Four

Explanation and example

In the following sample are combinations of:

One
Two
Three
Four

Combinations are by columns. Each colum represents combination of amount of numbers it holds.

Read the sample top-down.

The sample:

Task

Take each number and combine it with each of the subsequent ones. Then take next number and do the same.
Ignore the last element in combinations of one.

For input sequence A, for example:

A[1] A[2], A[1] A[3], to A[1] A[A.length]

A[2] A[3], A[2] A[A.length]

Repeating the steps until the end.

COMBINATIONS-OF-TWO(A)
  combinations = [];
  count = 1;
  for i=1 to A.length - 1
    for j=i+1 to A.length
      combinations[count] = [i, j];
      count++;
  return combinations;

Conclusions and implementation

Using mathematical induction we conclude that:

One

Combinations of one take each element from an array.

Two

Combinations of two take each combination of one
Then append each subsequent element to each.
Ignoring last element in combination of one.

Three

Combinations of three take each combination of two.
Then append each subsequent element to each.
Ignoring last 2 elements in combination of one.
Ignoring last 1 element in combination of two.

Four

Combination of four take each combination of three.
Then append each subsequent element to each.
Ignoring last 3 elements in combination of one.
Ignoring last 2 elements in combination of two.
Ignoring last 1 elements in combination of three.

Implementation

COMBINATIONS-OF-FOUR(A)
  combinations = [];
  // use counter because loops
  // don't track amount combinations
  count = 1;

  // combinations of one
  for i to A.length - 3

    // combinations of two
    for j=i+1 to A.length - 2

      // combinations of three
      for z=j+1 to A.length - 1

        // each subsequent element
        // on top of combination of three
        // gives combination of four
        for k=z+1 to A.length
          combinations[count] = [i, j, z, k];
          count++;

  return combinations;

As a bonus, here is implementation using JavaScript. Copy-Paste runnable.

function combinationsOfFour(A) {
  let combinations = [];
  let count = 0;
  let i, j, z, k;
  const len = A.length;

  for (i = 0; i < len - 3; i++) {
    for (j = i + 1; j < len - 2;j++) {
      for (z = j + 1; z < len - 1; z++) {
        for (k = z + 1; k < len; k++) {
          combinations[count] = [i, j, z, k];
          count++;
        }
      }
    }
  }

  return combinations;
}

const numbers = [0, 1, 2, 3, 4];
console.log(combinationsOfFour(numbers));

Find valid sums of 4

Now, I'll modify the algorithm. I need to return quadruples with indices whose values match sum.

// find sums of 4 that match sum
SUMS-OF-FOUR(A, sum)
  sums = [];
  // use sum counter because loops
  // don't track amount of sums we have
  count = 1;

  // combinations of one
  for i to A.length - 3
    for j=i+1 to A.length - 2
      for z=j+1 to A.length - 1
        for k=z+1 to A.length
          // if combination of four
          // is the sum we need
          if A[i] + A[j] + A[z] + A[k] == sum
            // save the indices representing sum
            sums[count] =[i, j, z, k];
            count++;

  return sums;

How many loops do I need?

I figured out how many loops I need. I did that by observing behavior which I used.

Using sequence 1, 2, 3, 4, 5 get combinations of one.

That was linear. Now, do it for combinations of two.

Using sequence 1, 2, 3, 4, 5, get combinations of two.

First number:

1
  append 2 => 1, 2
  append 3 => 1, 3
  append 4 => 1, 4
  append 5 => 1, 5

Second number:

2
  append 3 => 2, 3
  append 4 => 2, 4
  append 5 => 2, 5

Notice the loop behavior? I was doing that all the time. It took me a few hours until I realized how many iterations my mind does.

Using mathematical induction, we conclude the following

We can repeat the steps for combination of n.
Combinations of one use one loop, and are linear.
Combinations of two use two loops, and are quadratic.
Combinations of three use three loops, and are cubic.

Implementing combinations for any valid r

Using the sequence 1, 2, 3, 4, 5.

Given the transformations up to level 3, or r=3.

We can observe columns as levels or combinations r. Each combination is transformation of previous one. To get to combination of 2, we transform each combination of 1. For each previous combination, we take last value (index). Then append each subsequent index to that combination. That gives us new combination. Creating equal amount of combinations as subsequent iterations. Exception is initial combinations, they are empty. We have to populate them. We keep transforming combinations untill we exhaust amount of values per level. We need one level for each transformation.

Implementation

COMBINATIONS(array, r, combinations = [])
  if combinations.length == 0
    // populate combinations of 1
    for i=1 to array.length
      combinations[i] = [i]

  if r > 1
    // next combinations
    next = []
    count = 1
    // transform each combination
    // to next one
    for i=1 to combinations.length
      // take current combination
      c = combinations[i]
      // take last index
      last = c[c.length]
      // append next indexes to
      // current combination
      for j=last+1 to array.length
        // copy current combination
        next[count] = c
        // append index to current comb.
        // which creates new one
        next[count][c.length + 1] = j
        count++

    COMBINATIONS(array, r-1, next)
  else
    return combinations

Constraints to consider

array must be array of numbers
1 <= r <= ar
- info: we can't make non-repeated combination of 6 from 5 numbers
- info: combinations of 0 make no sense?
combinations must be either
- empty array (because of initial value)
- array of numbers