from sympy import subfactorial from math import comb from itertools import count, accumulate, pairwise, permutations from more_itertools import nth_combination, nth def number_of_derangements_for_permutation_at_index(n, idx): #n = len(seq) for k, (low_acc, high_acc) in enumerate(pairwise(accumulate((comb(n,k) * subfactorial(k) for k in count(2)), initial=1)), start=2): if low_acc <= idx < high_acc: return k, low_acc def is_derangement(seq, perm): return all(i != j for i,j in zip(seq, perm)) def lift_permutation(seq, deranged, permutation): result = list(seq) for i,j in zip(deranged, permutation): result[i] = seq[j] return result def nth_permutation(seq, idx): if idx == 0: return list(seq) n = len(seq) k, acc = number_of_derangements_for_permutation_at_index(n, idx) idx_q, idx_r = divmod(idx - acc, subfactorial(k)) deranged = nth_combination(range(n), k, idx_q) derangement = nth((p for p in permutations(deranged) if is_derangement(deranged, p)),  idx_r) # TODO: FIND EFFICIENT VERSION OF THIS LINE return lift_permutation(seq, deranged, derangement) 

As a result, this last step takes time proportional to idx_r, where idx_r is the index of the derangement, a number between 0 and factorial(k), where k is the number of elements which are deranged by the returned permutation.

from sympy import subfactorial from math import comb from itertools import count, accumulate, pairwise, permutations from more_itertools import nth_combination, nth def number_of_derangements_for_permutation_at_index(n, idx): #n = len(seq) for k, (low_acc, high_acc) in enumerate(pairwise(accumulate((comb(n,k) * subfactorial(k) for k in count(2)), initial=1)), start=2): if low_acc <= idx < high_acc: return k, low_acc def is_derangement(seq, perm): return all(i != j for i,j in zip(seq, perm)) def lift_permutation(seq, deranged, permutation): result = list(seq) for i,j in zip(deranged, permutation): result[i] = seq[j] return result # THIS FUNCTION NOT EFFICIENT def nth_derangement(seq, idx): return nth((p for p in permutations(seq) if is_derangement(seq, p)),  idx)  def nth_permutation(seq, idx): if idx == 0: return list(seq) n = len(seq) k, acc = number_of_derangements_for_permutation_at_index(n, idx) idx_q, idx_r = divmod(idx - acc, subfactorial(k)) deranged = nth_combination(range(n), k, idx_q) derangement = nth_derangement(deranged, idx_r) # TODO: FIND EFFICIENT VERSION return lift_permutation(seq, deranged, derangement) 

The first permutation is the identity; then the next (n choose 2) permutations just swap two elements; then the next (n choose 3)(subfactorial(3)) permutations derange 3 elements; then the next (n choose 4)(subfactorial(4)) permutations derange 4 elements; etc. To find the Nth permutation, first figure out how many elements it deranges by finding the largest K such that sum[k = 0 ^ K] (n choose k) subfactorial(K) ⩽ N.

from sympy import subfactorial from math import comb from itertools import count, accumulate, pairwise, permutations from more_itertools import nth_combination, nth def number_of_derangements_for_permutation_at_index(n, idx): #n = len(seq) for k, (low_acc, high_acc) in enumerate(pairwise(accumulate((comb(n,k) * subfactorial(k) for k in count(2)), initial=1)), start=2): if low_acc <= idx < high_acc: return k, low_acc def is_derangement(seq, perm): return all(i != j for i,j in zip(seq, perm)) def lift_permutation(seq, deranged, permutation): result = list(seq) for i,j in zip(deranged, permutation): result[i] = seq[j] return result def nth_permutation(seq, idx): if idx == 0: return list(seq) n = len(seq) k, acc = number_of_derangements_for_permutation_at_index(n, idx) idx_q, idx_r = divmod(idx - acc, subfactorial(k)) deranged = nth_combination(range(n), k, idx_q) derangement = nth((p for p in permutations(deranged) if is_derangement(deranged, p)), idx_r) return lift_permutation(seq, deranged, derangement) 

Testing for speed on large data:

The first permutation is the identity; then the next (n choose 2) permutations just swap two elements; then the next (n choose 3)(subfactorial(3)) permutations derange 3 elements; then the next (n choose 4)(subfactorial(4)) permutations derange 4 elements; etc. To find the Nth permutation, first figure out how many elements it deranges by finding the largest K such that sum[k = 0 ^ K] (n choose k) subfactorial(k) ⩽ N.

from sympy import subfactorial from math import comb from itertools import count, accumulate, pairwise, permutations from more_itertools import nth_combination, nth def number_of_derangements_for_permutation_at_index(n, idx): #n = len(seq) for k, (low_acc, high_acc) in enumerate(pairwise(accumulate((comb(n,k) * subfactorial(k) for k in count(2)), initial=1)), start=2): if low_acc <= idx < high_acc: return k, low_acc def is_derangement(seq, perm): return all(i != j for i,j in zip(seq, perm)) def lift_permutation(seq, deranged, permutation): result = list(seq) for i,j in zip(deranged, permutation): result[i] = seq[j] return result def nth_permutation(seq, idx): if idx == 0: return list(seq) n = len(seq) k, acc = number_of_derangements_for_permutation_at_index(n, idx) idx_q, idx_r = divmod(idx - acc, subfactorial(k)) deranged = nth_combination(range(n), k, idx_q) derangement = nth((p for p in permutations(deranged) if is_derangement(deranged, p)), idx_r) # TODO: FIND EFFICIENT VERSION OF THIS LINE return lift_permutation(seq, deranged, derangement) 

Testing for speed on medium data:

from math import factorial seq = 'abcdefghij' n = len(seq) # 10 N = factorial(n) // 2 # 1814400 perm = ''.join(nth_permutation(seq, N)) print(perm) # fcjdibaehg