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

Question

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

I.e. get_permutation(l,i) != get_permutation(l,j) if i!=j for all i, j s.t. 0 <= i and j < len(l)!).

Moreover, this function has to run in O(n).

For example, this function would comply the with the requirements, if it weren't for the exponential order:

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

Does anyone has a solution for the above described problem?

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

Answer 1

If you don't care about which permutations get which indices, an O(n) solution becomes possible if we consider that arithmetic operations with arbitrary integers are O(1).

For example, see the paper "Ranking and unranking permutations in linear time" by Wendy Myrvold and Frank Ruskey.

In short, there are two ideas.

---

(1) Consider Fisher-Yates shuffle method to generate a random permutation (pseudocode below):

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

This transform is injective: if we give it a different sequence of random integers, it is guaranteed to produce a different permutation. So, we substitute random integers by non-random ones: the first one is 0, the second one 0 or 1, ..., the last one can be any integer from 0 to n-1.

---

(2) There are n! permutations of order n. What we want to do now is to write an integer from 0 to n!-1 in factorial number 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 will get a unique sequence to feed the above pseudocode with.

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

---

In practice, for small n, O(n^2) or O(n log n) methods to rank or unrank a permutation, and also methods requiring O(2^n) or O(n!) memory to store some precomputed values, may be faster than an O(n) method involving integer division, which is a relatively slow operation on modern processors. For n large enough so that the n! does not fit into a machine word, the "O(n) if order-n! integer operations are O(1)" argument stops working. So, you may be better off for both small and large n if you don't insist on it being theoretically O(n).

Answer 2

Based on http://www.2ality.com/2013/03/permutations.html here's a possible solution. As @Gassa pointed out, elements.pop is not constant in order, and hence the solution is not linear in the length of the list. Therefore, I won't mark this as an accepted answer. But, it 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)

Answer 3

Update: possible dupe of Finding n-th permutation without computing others, see there for algorithm.

If len(l) will be small, you could precompute perm_index = permutations(range(len(l))) and use it as a list of lists of indexes into your actual data.

Moreover, if you have a list of permutations 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 takes advantage of the fact that the permutations are in sorted order when generated.