How to calculate sum of all permutations of a whole number

0 / 664
sum of permutations of digits

Calculate sum of all permutations of a whole number

 

 

Calculate sum of permutations of digits problem statement:

 

Can the reader give the sum of all the whole numbers that can be formed with the four figures 1, 2, 3, 4? That is, the addition of all such numbers as 1,234,1,423,4,312, etc. You can, of course, write them all out and make the addition, but the interest lies in finding a very simple rule for the sum of all the numbers that can be made with four different digits selected in every possible way, but zero excluded ?

 

There are 2 ways to solve this puzzle, one is to brute force all permutations of the whole number and sum up each of the permutations together which is pretty straightforward, second way is to find a correlation between those permutations and deduce a formula for the same which can be used for any number. We will go through both approaches in this blog.

 

Below code snippet returns the sum of all permutations of the whole number by brute force:-

function permuteAndCalcSum(prefix, string, permute_sum) {
var n = string.length;
if (n === 0) {
permute_sum += parseInt(prefix);
return permute_sum;
} else {
for (var index = 0; index < n; index++) {
permute_sum = permuteAndCalcSum(prefix.concat(string[index]),
string.slice(0, index).concat(string.slice(index + 1, n)), permute_sum);
}
}
return permute_sum;
}

 

The logic behind the above code is fairly simple, it recursively feeds in substrings to the permuteAndCalcSum() function for different prefixes one by one , say for e.g ,  prefixes like 1,2,3,4 for the string ‘1234’ and repeats the same process recursively for corresponding substrings : 234, 134, 124, 123, breaks down these substrings again into smaller substrings till base condition is met.

 

Below are the permutations deduced by this function for numbers 123 and 1234

Permutations of 123:
123
132
213
231
312
321
Permutations of 1234:
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

 

 

From the above output, it’s very easy to find a correlation between the pattern of digits each of the whole number permutations has!!

 

In case of 1234, the digit combination which is repeated for each of the permutations of the whole number is 

 

4 4 3 3 2 2
4 4 3 3 1 1
4 4 2 2 1 1
3 3 2 2 1 1 

 

which means 6 times, which is equal to (lengthOfNumber -1)  = 4-1 = 3! times each of the digits 1,2,3,4 is repeated..

 

For number 123, the digit combination is:-

 

3 3 2 2 1 1

 

which means 2 times, which is equal to (lengthOfNumber -1)  = 3-1 = 2! times each of the digits 1,2,3 is repeated.

 

if we sum up these digits thus obtained we get sum of each of the digits of the whole number permutations. This can be expressed as the following:

 

4*6! + 3*6! + 2*6! + 1*6! = (4+3+2+1)*6! = Sum of all the digits * (n-1)! where n = number of digits in the whole number. In this case, as it’s first n natural numbers without any repetition , sum of digits can be represented as n(n+1)/2, so the final formula for sum of each of the digits in unit’s, ten’s, hundred’s and thousand’s place will be n(n+1)/2 * (n-1)!.

 

Now we have sum represented by each of the digits in the permutation, it’s easy to obtain the sum of all the whole numbers by totalling the face values of each of the digit sums using powers of 10 since it’s a decimal number.

 

 

So, final sum of all permutations = [10(n-1) + 10(n-2) +…….+10(n-n)] * Sum of all the digits * (n-1)! = [10(n-1) + 10(n-2) +…….+10(n-n)] * (n(n+1)/2) * (n-1)! ——–(1)

 

 

We can use the formula given in equation (1) to compute sum of all possible permutations of a given whole number. This formula also works for whole numbers with repetitive digits in place. 

 

Below code snippet represents the formula (1) above using javascript:

 

function calcSumFormula(length) {
var formula_sum = 0;
for (var i = length - 1; i >= 0; i--) {
formula_sum += Math.pow(10, i);
}
formula_sum = (length * (length + 1) / 2) * formula_sum * factorial(length - 1);
return formula_sum;
}

 

The formula and brute force algorithm are generic and can be applied to any number.

 

Combining all the above as a single jsfiddle:-

 

 

Hope you enjoyed reading this. Like us on Golibrary for interesting reads like this.

 

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts