Disarium disaster and rank permutations

Disarium numbers

We are asked to write a script to generate first 19 Disarium numbers. A Disarium number is an integer where the sum of each digit raised to the power of its position in the number, is equal to the number.

Clearly 1 to 9 inclusive are Disarium numbers because they all contain 1 digit and n ^ 1 == n.

The next 8 are easily found, ranging from 89 to 2427. One further one needs a little more effort: 2646798.  I found them simply by examining 1 .. (big integer). It pays to do the examination from the last digit back to the first, because you can give up as soon as the sum exceeds the number under examination.

So there's 18 of them without much effort. But what of the nineteenth?

I left my algorithm running while I had a leisurely lunch (it's 39 degrees here, after all) and came back to find ... nothing.  So if there are any more DNs, they are quite big.

But, aha! Mohammad didn't specify where we should start, so I am claiming that 0 is a Disarium number, because 0^1 == 0, and that makes 2646798 the 19th.

So Disarium disaster averted!

Ranking permutations

Mohammad tells us that we are given a list of integers with no duplicates, e.g. [0, 1, 2] and are to write two functions: 

• permutation2rank() which will take the list and determine its rank (starting at 0) in the set of possible permutations arranged in lexicographic order, and 
• rank2permutation() which will take the list and a rank number and produce just that permutation.

He also kindly point us to an algorithm - and even some sample code.  I have to say I didn't find the permutation2rank code too easy to follow, but from the textual description above it I more-or-less did the same in Perl.

The algorithm insists on the permuted set being a set of consecutive integers starting from 0, and while Mohammad doesn't restrict us to that, I think it's good enough for a hot afternoon.

The slightly tricky bit is that as you create a single permutation, your choice of what comes next gets steadily less. So given 0, 1, 2, 3, 4, you've got a choice between 5 options for the first digit of your perm, but only 4 for the next now that you've used up one digit already, and once you get to the 5th digit you've already used up 4 of the 5 and have no choice left for the fifth.

So the principal of the algorithm is to calculate the contribution to the rank from each digit, and add them together. If we are given 3, 2, 1, 0 we first calculate where the 3s start, then the offset from there to where the 3, 2s start, then the offset to where the 3, 2, 1s start - and of course that's also where they finish, because there's only one perm - 3, 2, 1, 0.

I chose to do this slightly differently from the linked article by maintaining an array @ranks.  For, say, a six-member perm, @ranks start out like this:

@ranks == [0, 1, 2, 3, 4, 5]

Let's say our given perm is [3, 4, 2, 1, 0].  Where do the perms starting with 3 start in the ranking? Well, after the 3 blocks of 0s, 1s and 2s. If I know (and I do) how big these blocks are, I know that our rank is going to be at least 3 of these big blocks.

Now we come to the second component of the perm which is 4. Now you might think that there will be 4 smaller blocks - the ones starting 3, 0; 3,1 ;3,2 ; 3,3 ... but no! that's not right because there won't be a 3, 3 because we've already used the only 3.

So backtrack a bit. After we did the first block of 3s, we need to eliminate 3 from the rankings and that's where @ranks comes in. After we've used 3, we change @ranks to be:

@ranks == [0, 1, 2, -1, 3, 4]  

The second element of our given perm is 4, and it's rank (within the block starting with 3) is $rank[4] - which is 3. It's in the 4th (counting from 0) sub-block after 3, 0; 3,1 and 3,2.

It is rather complex and hard to get your head round, but I hope that helps a bit.

So now we come to rank2permutation. The logic is quite similar: again we are looking at blocks starting with the same 0th, 1st, 2nd ... numbers and deducing where our desired row sits.

I've provided an example where the perm is 15 numbers, ie 0 ..14. Soon after that we'll run out of integers, but that's for another day.