Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
n-th permutation and dichotomy solution in Clear category for Permutation Index by Phil15
from itertools import accumulate
factorials = list(accumulate(range(1, 30), lambda x, y: x * y))
def nth_permutation(seq, n):
while seq:
k, n = divmod(n, factorials[len(seq)-2])
yield seq.pop(k)
def permutation_index(perm):
seq, start, end = sorted(perm), 0, factorials[len(perm)-1]
while start < end:
index = (start + end) // 2
p = tuple(nth_permutation(seq[:], index))
if p == perm:
return index + 1
if p < perm:
start = index + 1
else:
end = index
Sept. 28, 2019
