Sometime ago I needed to cope with the problem to compute all permutations of numbers which sum a to a specific value. An additional constraint was that the sum must be composed by a fixed amount of numbers. For example: compute all permnutations of four numbers witch sum up to 10.
1+2+3+4 = 10 0+3+4+3 = 10 2+1+1+6 = 10 ...
and afterwards some futher computations with these permutations must be performed. This post copes with the problem of computing all permutations (for a fixed amount) of numbers which sum up to a specific value. If you want to know (as an example) which 4 numbers sum up to 10 a naive approach would trial an error through all combinations to find out which combinations would end up with the prefered sum. An corresponding algorithm would look like the following
int NUM_ELEMENTS = 10;
// llop through all combinations
for (int a = 0; a <= TARGET_SUM; a++) {
for (int b = 0; b <= TARGET_SUM; b++) {
for (int c = 0; c <= TARGET_SUM; c++) {
for (int d = 0; d <= TARGET_SUM; d++) {
int sum = a + b + c + d;
// if the sum equals our preferred sum do something
if (sum == TARGET_SUM) {
computeMyStuff(a, b, c, d);
}
}
}
}
}
For 4 numbers with a prefered sum of 10 that would be 10000 combinations. When using 0 as an valid value there are even 14641 combinations!. But this is more an trial and error approach and no systematic way for computing these sums. The above algorithm does a lot of unnessesary work. Additionaly it is very time consuming and inefficient because it iterates over every possible combination. For the case that a=9, the inner loops of b, c and d will loop over all values from 0 to 10 which makes 1331 iterations from which only 3 combinations result in the prefered sum of 10. Besides the computational overhead in the above algorithm one needs to nest more and more loops if one wants to compute permutation which consist of more than 4 different numbers.
Lets see how we can derive an algorithm that allows us to compute these permutations in an efficient way. We start by looking at the pattern of the output which is generated by the above (naive) approach
... 0 + 0 + 0 + 10 = 10 0 + 0 + 1 + 9 = 10 0 + 0 + 2 + 8 = 10 0 + 0 + 3 + 7 = 10 0 + 0 + 4 + 6 = 10 0 + 0 + 5 + 5 = 10 0 + 0 + 6 + 4 = 10 0 + 0 + 7 + 3 = 10 0 + 0 + 8 + 2 = 10 0 + 0 + 9 + 1 = 10 0 + 0 + 10 + 0 = 10 0 + 1 + 0 + 9 = 10 0 + 1 + 1 + 8 = 10 0 + 1 + 2 + 7 = 10 0 + 1 + 3 + 6 = 10 0 + 1 + 4 + 5 = 10 0 + 1 + 5 + 4 = 10 0 + 1 + 6 + 3 = 10 0 + 1 + 7 + 2 = 10 0 + 1 + 8 + 1 = 10 ...
If we have n numbers where we number these from 0 to n from left to right, we can see that all numbers from 0 to n-1 are always increaseing and only the number at position n is repeadingly decreasing. This is exactly how we will design our new efficient algorithm. It will start increasing the number at position n-1. If this number is larger than our prefered sum, we will reset it to 0 an add the add carry to the number n-2. We will do this (from right to left) until there is no more add carry left. Afterward we need to find out which value the number at position n will have. This can be done by summing up all values of numbers from 0 to n-1 (from left to right) and afterwards compute the difference between the previously computed sum and the preferd sum. This result is the value of the n-th number.
Here comes the step by step description of the final algorithm. First of all we need a list in which we will store our values
int[] values = new int[NUM_ELEMENTS];
Afterward we will initialize the most right element with the value of our prefered sum. This will also be our first permutation, because we will first use a permuation and afterwards change it to get the next one, not the other way around.
values[NUM_ELEMENTS - 1] = TARGET_SUM;
In the next step, we will start incrementing the values from n-1 to 0 and compute the values of the n-th element, which is the most challenging part.
In order to find out if there is an “overflow” of a value which results in an add carry we will first sum up all values from 0 to n-2 and afterwards increment n-1. In the case that we have an consecutive add carry, we need to forward the add carry until no more add carry arises. To achive this we use the outer for loop which interates backwards over all values to handle the add carry.
for (int i = NUM_ELEMENTS - 1; i > 0; i--) {
tmpSum = 0;
for (int j = 0; j < i; j++) {
tmpSum += values[j];
}
if (inc) {
if (tmpSum + values[i] > TARGET_SUM) {
values[i] = 0;
values[i - 1] += 1;
}
}else if (tmpSum + values[i] + 1 > TARGET_SUM) {
values[i] = 0;
values[i - 1] += 1;
inc = true;
}
}
The last part is computing the value of the n-th element which is just the difference between all other values and the prefered sum
for (int i = 0; i < NUM_ELEMENTS - 1; i++) {
tmpSum += values[i];
}
values[NUM_ELEMENTS - 1] = TARGET_SUM - tmpSum;
Below you will find the whole algorithm which computes all possible combinations in the above described efficient way, without doing any unneccesary work. It is also independent of the amount of numbers which should sum up to the prefered value.
private static final int NUM_ELEMENTS = 10;
private static final int TARGET_SUM = 30;
public static void main(String[] args) {
int[] values = new int[NUM_ELEMENTS];
int tmpSum = 0;
boolean inc = false;
values[NUM_ELEMENTS - 1] = TARGET_SUM;
while (values[0] != TARGET_SUM) {
// at this point you can compute anything you want with the current permutation
computeMyStuff(values);
inc = false;
tmpSum = 0;
for (int i = NUM_ELEMENTS - 1; i > 0; i--) {
tmpSum = 0;
for (int j = 0; j < i; j++) {
tmpSum += values[j];
}
if (inc) {
if (tmpSum + values[i] > TARGET_SUM) {
values[i] = 0;
values[i - 1] += 1;
}
} else if (tmpSum + values[i] + 1 > TARGET_SUM) {
values[i] = 0;
values[i - 1] += 1;
inc = true;
}
}
tmpSum = 0;
for (int i = 0; i < NUM_ELEMENTS - 1; i++) {
tmpSum += values[i];
}
values[NUM_ELEMENTS - 1] = TARGET_SUM - tmpSum;
}
}
If you have any questions or suggestions please leave a comment 🙂
Leave a Reply