64 symbols have 64! permutations. How to get one of these permutations from its index/rank and how to get index/rank of one of these permutations in the fastest way in Java or Python or C#?
These permutations have no repetitions, and the length of each of the permutations is equal to the number of symbols given to the function.
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]]
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))