Geek Answers Handbook

Given the list of elements in lexicographic order (ie ['A', 'b', 'c', 'd']), find the nth permutation - Average time to solve?

I came across this interview question:

Given the list of elements in lexicographic order (ie ['a', 'b', 'c', 'd']), find the nth permutation

I tried it myself and it took me about 30 minutes to solve. (I ended up with a ~ 8-9 linear solution in Python). Just curious - how long does it take to solve this problem? Am I taking too long?

+3
source share
3 answers

9 min including test

import math def nthperm(li, n): n -= 1 s = len(li) res = [] if math.factorial(s) <= n: return None for x in range(s-1,-1,-1): f = math.factorial(x) d = n / f n -= d * f res.append(li[d]) del(li[d]) return res #now that fast... nthperm(range(40), 123456789012345678901234567890)
+10
source

Maybe something is missing for me, I thought we could easily find it using nth from itertools Recipes and permutations :

 from itertools import permutations, islice def nth(iterable, n, default=None): "Returns the nth item or a default value" return next(islice(iterable, n, None), default) def main(): data = ['a', 'b', 'c', 'd'] n = 7 # 0 indexed print nth(permutations(data), n) if __name__ == "__main__": main()
0
source

Just in case, someone is interested in a solution that can find the "i-th" permutation when you look at the "r-length-permutations" (as represented by the r itertools.permutations argument):

 from math import factorial def ith_permutation(i, seq, r=None): li = list(seq) length = len(li) if r is None: r = length res = [] current_factorial = factorial(length) // factorial(length - r) if current_factorial <= i: raise ValueError('out of range') for x in range(length, length-r, -1): current_factorial //= x div, mod = divmod(i, current_factorial) i = mod res.append(li[div]) del(li[div]) return res

For instance:

 >>> ith_permutationutation(10, [0, 1, 2, 3, 4], 2) [2, 3] >>> # correctness check: >>> from itertools import permutations >>> list(permutations([0, 1, 2, 3, 4], 2))[10] (2, 3)

Including a more complete test:

 s = range(8) for n in range(len(s)): for idx, item in enumerate(permutations(s, n)): assert list(item) == ith_permutation(idx, s, n)

Some parts of Karoli Horvath's answer were used here.

0
source

More articles:


All Articles