Skip to main content
Code Review

Return to Question

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Note: The same topic for Java is here!here!

Note: The same topic for Java is here!

Note: The same topic for Java is here!

I added an explanation to the Example section, and added another example.
Source Link
Santana Afton
Santana Afton
  • 267
  • 1
  • 5

ExampleTime 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(12,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))

Permutations of size 1 took 4.83249833749e-05 seconds.
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

Example:

I ran the following code:

for j in range(1,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))

Permutations of size 1 took 4.83249833749e-05 seconds.
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.

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

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
Source Link
Santana Afton
Santana Afton
  • 267
  • 1
  • 5

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

Example:

I ran the following code:

for j in range(1,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 1 took 4.83249833749e-05 seconds.
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.