Fastest way to get Nth combination without repetition from a larg number of symbols

N-th permutation

The iea is that whichever digit you select for the first position, what remains is a permutation of (n-1) elements, so the digit selected to the first position is floor(idx / (n-1)!). Apply this recursively and you have the permutation you want.

from functools import lru_cache
@lru_cache
def factorial(n):
    if n <= 1: return 1
    else: return n * factorial(n-1);

def nth_permutation(idx, length, alphabet=None, prefix=()):
    if alphabet is None:
        alphabet = [i for i in range(length)]
    if length == 0:
        return prefix
    else:
        branch_count = factorial(length-1)
        for d in alphabet:
            if d not in prefix:
                if branch_count <= idx:
                    idx -= branch_count;
                else:
                    return nth_permutation(idx, 
                              length-1, alphabet, prefix + (d,))

This will return a tuple representing the requested permutation, if you want you can pass a custom alphabet.

Examples

nth_permutation(1, 10)
# (0, 1, 2, 3, 4, 5, 6, 7, 9, 8)
nth_permutation(1000, 10)
# (0, 1, 2, 4, 6, 5, 8, 9, 3, 7)
1000
nth_permutation(3628799, 10)
# (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
nth_permutation(10**89, 64)
# [[50 27 40 11 60 12 10 49]
# [63 29 41  0  2 48 43 47]
# [57  6 59 56 17 58 52 39]
# [13 51 25 23 45 24 26  7]
# [46 20 36 62 14 55 31  3]
# [ 4  5 53 15  8 28 16 21]
# [32 30 35 18 19 37 61 44]
# [38 42 54  9 33 34  1 22]]

Permutation index

The index of a given permutation is the index of the first element multiplied by (n-1)! added to the rank of the permutation of the remaining terms.

def permutation_index(item, alphabet=None):
    if alphabet is None:
        alphabet = sorted(item)
    n = len(item)
    r = 0
    for i, v in enumerate(item):
        # for every (item[j] > item[i]) we have to increase (n - i)!
        # the factorials are computed recursively
        # grouped in r
        r = sum(1 for u in item[i+1:] 
                if alphabet.index(u) < alphabet.index(v)) + r * (n - i)
    return r;

Consistency check

permutation_index(nth_permutation(1234567890, 16))