Finding permutation from given lexicographical rank

Question

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 < 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

Is there a reason you didn't build your code around the permutations function in the itertools module? — Curt F.
– Curt F., Commented Jun 22, 2016 at 21:26
I understand that itertools.permutations() generates permutations, and I am more interested in finding a specific permutation based on its order. Unless I'm not seeing what you're saying? — Santana Afton
– Santana Afton, Commented Jun 23, 2016 at 14:39
I did a quick test of your code vs.itertools.permutations, and the itertools function was much faster. Maybe I don't really understand what your code does. I added a print x to your double for loop that tests your code, it seemed like it generates permutations too. Maybe you could add docstrings, doctests, or other information to your code so that it is easy to understand expected inputs and outputs? — Curt F.
– Curt F., Commented Jun 23, 2016 at 21:28
I just edited the post -- let me know if this is any clearer. — Santana Afton
– Santana Afton, Commented Jun 24, 2016 at 4:14

SylvainD · Accepted Answer · 2016-06-24 09:20:06Z

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])

Stack Exchange Network

Finding permutation from given lexicographical rank

Input:

Code:

Time Complexity Example:

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Finding permutation from given lexicographical rank

Input:

Code:

Time Complexity Example:

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions