Day 91: Variations

Take all the natural numbers in which each digit occurs at most once and sort them in the ascending order. Given this ordering, write two functions: (1) order->number: find a number N at index I, (2) number->order: find an index I of number N.

Notes: (a) zero is a natural number, (b) consider index to be zero-based

left column: index, right column: number

I drew this problem when I was at my very first exam at university. This exam was also the very first I failed in and had to repeat few weeks later. Almost 20 years later, I would like to give myself a second chance.

Could a viable solution be to generate all the variations and sort them out? Well, there are 8,877,691 variations and machine was 386 with 1MB of memory. Remind me, how big the data has to be to call them Big data?

This is clearly a combinatorial problem and requires a little bit of thinking and a lots of counting.

I tried to avoid most of built-in functions except for a fixed list, which is easy to implement even in Pascal. But still, I have a feeling that my solution is too complicated. Did I miss something?

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

algorithm

def variation_to_order(variation):
alphabet = list('0123456789')
n = len(variation)
    order = 1
order -= ffact(9, n - 1)
for i in range(1, n):
order += ffact(10, i) - ffact(9, i - 1)
    for i in range(n):
index = alphabet.index(variation[i])
order += index * ffact(9 - i, n - i - 1)
del alphabet[index]
    return order

def order_to_variation(order):
for n in range(1, 11):
k = ffact(10, n) - ffact(9, n - 1)
if k >= order:
break
order -= k
    order -= (n != 1)
alphabet = list('0123456789')
variation = ''
    for i in range(n):
k = ffact(9 - i, n - i - 1)
index = order // k + (i == 0) - (n == 1)
order %= k
variation += alphabet[index]
del alphabet[index]
    return variation

def ffact(n, k, _cache={}):
if (n, k) not in _cache:
f = 1
for i in range(k):
f *= n - i

_cache[n, k] = f

return _cache[n, k]

run

> variation_to_order('9876543210')
8877690

run

print(' variation    order')
for _ in range(10):
i = randrange(8877691)
variation = order_to_variation(i)
order = variation_to_order(variation)
assert i == order
print('%10s ## %d' % (variation, order))
>>>
 variation    order
13497085 ## 760661
91076428 ## 2186637
5394218760 ## 7221978
972538064 ## 5544432
3906817245 ## 6663589
432069781 ## 3565883
801362957 ## 4887112
47359618 ## 1387152
859367012 ## 5125627
86732051 ## 2120257
Like what you read? Give Tomáš Bouda a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.