# 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 ## 21866375394218760 ## 7221978 972538064 ## 55444323906817245 ## 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.