How to find lexicographical order of an array of N integers(i.e. 1,2,3,...,n) in its permutations in O(n) time?
Ex:- lexicographical order of {2,3,1,4} is 9 in its permutations
Asked
Active
Viewed 365 times
0
-
Do you know up front which integers make up the set (i.e. only 1,2,3,4 here)? If they can also be `{777, 99999, -8888, 5000000}` (which yields the same result), I imagine it will be more difficult. – Thilo Oct 08 '15 at 04:18
-
Related: http://stackoverflow.com/questions/21293906/find-the-lexicographic-order-of-an-integer-partition?rq=1 http://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others/7919887#7919887 – Thilo Oct 08 '15 at 04:21