Finding permutation from given lexicographical rank I wrote the following little piece of Python code to take in some integer, and return a permutation that has that rank in the lexicographical ordering of permutations. While this works, I'm worried that the number of calls to pop() and append() might be slowing this down. This function is part of a larger program, which will call FromRank() millions of times, and any small efficiency may make a large impact down the road. 

Note: The same topic for Java is here!

Input:

There are four arguments: rank, level, ordered, and perm. rank is the rank given. level is the number of uncertain digits of the permutation minus one. Hence, if the size of a permutation is 8 digits, then level is initially 7. ordered is initially list(range(size)) and is always sorted. perm keeps track of the permutation, and is initially an empty list.

Code:

def FromRank(rank,level,ordered,perm):
    fact = math.factorial(level)
    section = rank // fact
    if len(ordered) == 1:
        perm.extend(ordered)
        return perm
    elif rank % fact == 0:
        ordered.sort()
        nxt = ordered.pop(section - 1)
        perm.append(nxt)
        ordered.sort(reverse = True)
        perm.extend(ordered)
        return perm
    elif rank &lt; fact:
        ordered.sort()
        first = ordered.pop(0)
        perm.append(first)
        return FromRank(rank,level - 1,ordered,perm)
    else:
        ordered.sort()
        nxt = ordered.pop(section)
        perm.append(nxt)
        rank = rank - (rank // fact) * fact
        return FromRank(rank,level - 1,ordered,perm)


Time Complexity Example:

While the goal of this function is to work on a single rank, I ran the following code to see how runtime would ramp up with an increasing number of permutations to handle. And, although this function would never be running on permutations larger than 20, I included a section giving the runtimes for a single permutation of increasing size. 

I ran this to see how the function would respond to volume

for j in range(2,11):
    start_time = timeit.default_timer()

    for i in range(1,math.factorial(j)+1):
        x = FromRank(i,j-1,list(range(j)),[])))

    elapsed_time = timeit.default_timer() - start_time
    print("Permutations of size {} took {} seconds."\
              .format(j,elapsed_time))


and got the following times:

Permutations of size 2 took 0.000249750356557 seconds.
Permutations of size 3 took 0.00016293644837 seconds.
Permutations of size 4 took 0.000660726542604 seconds.
Permutations of size 5 took 0.00366414564209 seconds.
Permutations of size 6 took 0.0185743274595 seconds.
Permutations of size 7 took 0.160154982071 seconds.
Permutations of size 8 took 1.48163329891 seconds.
Permutations of size 9 took 15.2436537109 seconds.
Permutations of size 10 took 177.243403105 seconds.


I then ran the following to see how the function would respond to large permutations:

for size in [10,50,100,500,1000]:
    start_time = timeit.default_timer()
    x = FromRank(size ** 2, size - 1, list(range(size)), [])
    elapsed_time = timeit.default_timer() - start_time
    print(elapsed_time)


and got the following times:

0.000118032702744
0.00074668514128
0.00260142366255
0.110989229516
0.684973282271
Style

Python has a style guide called PEP 8 which is definitly worth reading and and worth following if you do not have good reasons not to. In you case, your function name for instance is not compliant to PEP8. You'll find tools online to check your code compliancy to PEP8 in a automated way if you want to.

API / Function signature

Your function signature is a bit unclear. This situation often happens when recursive solutions are applied. A good way to solve this would be to define another function calling the complicated function with the right arguments or to use default arguments.

If I understood everything properly, the point if to get the n-th performutation from a list. A simple way to do so would be to have a function taking the rank and the lst as an argument.

Testing

In order to keep things simple, it is a good option to write a simple (even if inefficient) solution to be able to see patterns and/or write tests to ensure that your more efficient works and is indeed more efficient.

A very simple solution could be written like this :

def from_rank(rank, lst):
    sorted_perm = sorted(itertools.permutations(lst))
    return sorted_perm[rank]


And you can write some simple tests like this :

tests_cases = ([], [1], [1, 2], [1, 2, 3], [3, 2, 1], [2, 2], [2, 2, 2])
for lst in tests_cases:
    for i in range(math.factorial(len(lst))):
        a = list(from_rank(i, lst))
        b = list(from_rank2(i, lst))
        if a != b:
            print(i, a, b)


Another more simple solution

Your solution involves both recursion and mutations of data. This can make things very hard to understand. A more simple idea could be to say that from the rank, it is easy to know which element will be the first of the permatation. Indeed, if your list has n elements, you know that there are (n-1)! permations of length n-1 and so the rank-th permutation will have for its first element the rank / ((n-1)!)-th elements. You can repeat the same thinking for a smaller list consistent of the remaining elements with the remaining part of the rank.

This can be written:

def from_rank2(rank, lst):
    my_lst = sorted(lst)
    ret = []
    while my_lst:
        fact = math.factorial(len(my_lst) - 1)
        idx, rank = divmod(rank, fact)
        ret.append(my_lst.pop(idx))
    assert rank == 0  # invalid rank - out of range
    return ret


Please note that this solution does not seem to handle very well lists with repeated elements. You can easily enhance your test suite to show it :

tests_cases = ([], [1], [1, 2], [1, 2, 3], [3, 2, 1], [2, 2], [2, 2, 2], [2, 2, 3], [1, 2, 5, 4, 3, 2])