Recently I got this question posed to me.
Imagine a 5 digit number (with no digit repeating and 1st digit is not zero) - example. 54312
If you rank all the 5 digit numbers you can make with the 5 digits, how big is the number given (54312) - what is its rank?
And it has to be given as an algorithm (or formula) so that the same algorithm works for any other 5 digit number or 6 or 7 digit number.
Hmm.
With 2 digits, we can create 2! number of 2 digit numbers. For example with 3,5
we can create 35, 53. With 3 digits, 3,5,8 we can have 3 as the 1st digit and create 2! numbers with the other digits 5,8. We can create 2! more numbers with 5 as the first digit and 3,8 as the other two digits. And one more set of 2! numbers having 8 as the 1st digit and 3,5 as the other two digits. Hence 3*2! =3! is the total number of numbers possible with 3 digits (none repeating and no zeros - just to keep it simple).
With 4 digits, the answer is 4! and with 5 digits it is 5!. Obviously this algorithm will work only up to 9 digits since no digit can repeat and zero isn't allowed.
Now to find out the rank of a given 5 digit number (either we need to find the number of numbers bigger than the given number or smaller than the given number). Let's say we find the number of number bigger than the given number.
Let's take the number 34512
Take the 1st digit (from Left) = 3
How many digits can be higher than this digit 3? 4 and 5. Two digits can be bigger. With each digit in the leftmost place, we can have 4! numbers with different combinations of digits from 2nd to 5th digits from L to R. So a total of 4!*2 (2 standing for 4,5 the two digits bigger than 3) numbers are possible based only on the leftmost digit.
Now come to the 2nd digit 4. How many digits are bigger than 4? Only 5. Freezing 35 as the first two digits, how many numbers can be formed with the other three digits? 3!*1 (one standing for 5, the only digit than is bigger than 4)
Now we come to the 3rd digit 5. 5 is the biggest number. Hence we cant any bigger number coming from the 3 digit.
4th digit 1.
How many digits are bigger than 1? Only 2. The last two digits can be 12 or 21. Only one number is possible.
Now adding all the numbers bigger than the given number, we have 4!*2+3!*1+2!*0+1=48+6+0+1=55.
So the logic is:
take the 1st digit (leftmost): find how many digits are bigger than the one we have. Multiply that number by (n-1)!.
Repeat this with the 2nd digit and 3rd digit and so on. When you come to the last 2 digits, there are only two numbers possible. Either ours is the biggest or there is another number which is bigger. Add up all the numbers. That provides the rank.
Incidentally, the number of possible combinations of 5 digits is 5! = 120.