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:
1
1 2
1 2 3
1 2 3 4
1 2 3 5
1 2 4
1 2 4 5
1 2 5
1 3
1 3 4
1 3 4 5
1 3 5
1 4
1 4 5
1 5
2
2 3
2 3 4
2 3 4 5
2 3 5
2 4
2 4 5
2 5
3
3 4
3 4 5
3 5
4
4 5
5
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.
1
2
3
4
5
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.
1
1 2
1 2 3
1 2 4
1 2 5
1 3
1 3 4
1 3 5
1 4
1 4 5
1 5
2
2 3
2 3 4
2 3 5
2 4
2 4 5
2 5
3
3 4
3 4 5
3 5
4
4 5
5
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
Top comments (0)