Get permutation as a function of a unique given index in O (n)

Question

I would like to have a get_permutation function, which, given the list l and index i , returns a permutation l such that the permutations are unique for all i greater than 0 and lower than n! (where n = len(l) ).

those. get_permutation(l,i) != get_permutation(l,j) if i!=j for all i , j st 0 <= i and j < len(l)! )

In addition, this function must be performed in O(n) .

For example, this function would meet the requirements if it were not for the exponential order:

 def get_permutation(l, i): return list(itertools.permutations(l))[i] 

Does anyone have a solution for the problem described above?

EDIT: I want the permutation from the index NOT to indicate from the permutation

Answer 1

If it doesn't matter to you which permutations which indexes will get, then the solution O (n) becomes possible, given that arithmetic operations with arbitrary integers are O (1).

For example, see the article “ Ranking and Unlocking Permutations in Linear Time ” by Wendy Mirwold and Frank Rusik.

In short, there are two ideas.

---

(1) Consider the Fisher-Yates shuffle method for generating random permutation (pseudo code below):

 p = [0, 1, ..., n-1] for i := 0 upto n-1: j := random_integer (0, i) exchange p[i] and p[j] 

This transformation is injective: if we give it another sequence of random integers, then it is guaranteed that it will perform another permutation. Thus, we replace random integers with nonrandom ones: the first is 0, the second is 0 or 1, ..., the last can be any integer from 0 to n-1.

---

(2) There are n! permutations of order n. Now we want to write an integer from 0 to n! -1 in the factorial system : the last digit is always 0, the previous one is 0 or 1, ..., and there are n possibilities from 0 to n-1 for the first digit. Thus, we get a unique sequence for filing the above pseudocode using.

Now, if we consider the division of our number by an integer from 1 to n by the operation O (1), the conversion of the number into the factorial system O (n) of such divisions. This, strictly speaking, is not true: for large n, the number n! contains the order of binary digits O (n log n), and the cost of separation is proportional to the number of digits.

---

In practice, for small n, O (n ^ 2) or O (n log n) methods to rank or cancel permutation, as well as methods that require storage of O (2 ^ n) or O (n!) For storage, some previously calculated values ​​may be faster than the O (n) method, which includes integer division, which is a relatively slow operation on modern processors. For n large enough for n! does not fit into the machine word, "O (n) if the order-n! integer operations are an O (1) argument", stops working. Thus, you might be better off for small and large n if you do not insist that it is theoretically O (n).

Answer 2

Update: possible workaround. Search for the nth permutation without calculating other parameters ; see where there is an algorithm.

If len(l) is small, you can pre-copy perm_index = permutations(range(len(l))) and use it as a list of index lists in your actual data.

Also, if you have a permutation list from range(len(l)) and you need one for for range(len(l) - 1) , you can do something like:

 [x - 1 for x in perm_index[i][1:]] 

which uses the fact that permutations are sorted when created.

Answer 3

This solution works in O(1) (complexity of execution, amortized cost of searching in dictionaries):

code

 #!/usr/bin/env python import itertools def get_permutation(): memoize = {} def _memoizer(l, i): if str(l) in memoize and i not in memoize[str(l)]: memoize[str(l)][i] = memoize[str(l)]['permutations'].next() else: p = itertools.permutations(l) memoize[str(l)] = {'permutations': p} memoize[str(l)][i] = memoize[str(l)]['permutations'].next() return memoize[str(l)][i] return _memoizer if __name__ == '__main__': get_permutation = get_permutation() l1 = list(range(10)) l2 = list(range(5)) print(get_permutation(l1, 1)) print(get_permutation(l1, 20)) print(get_permutation(l2, 3)) 

Output

 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) (0, 1, 2, 3, 4, 5, 6, 7, 9, 8) (0, 1, 2, 3, 4) 

How it works

The code stores all past calls in the dictionary. It also saves the permutation object. Therefore, if a new permutation is requested, the next permutation is used.

The code uses itertools.permutations

Answer 4

Based on http://www.2ality.com/2013/03/permutations.html a solution can be found here. As @Gassa noted, elements.pop is not constant in order, and therefore the solution is not linear in the length of the list. Therefore, I will not mark this as an accepted answer. But he does the job.

 def integerToCode(idx, permSize): if (permSize <= 1): return [0] multiplier = math.factorial(permSize-1) digit =idx / multiplier return [digit] + integerToCode(idx % multiplier, permSize-1) def codeToPermutation(elements, code): return map(lambda i: elements.pop(i), code) def get_permutation(l, i): c = integerToCode(i, len(l)) return codeToPermutation(list(l), c)