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
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
