Welcome, guest | Sign In | My Account | Store | Cart

Although Recipe 578227 was straight-forward to derive, I came across this Stack Overflow answer that gives another method for generating the sign based on comparing the perm and the sorted perm.

Python, 13 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def perm_parity2(a):
    '''\
    Using algorithm from http://stackoverflow.com/questions/337664/counting-inversions-in-an-array/6424847#6424847
    But substituting Pythons in-built TimSort'''

    a = list(a)
    b = sorted(a)
    inversions = 0
    while a:
        first = a.pop(0)
        inversions += b.index(first)
        b.remove(first)
    return -1 if inversions % 2 else 1

I have implemented the method in the code, but I use Pythons in-built sort implementation instead of their mergesort.

I timed this and the previous function on finding the sign of the same random shuffle of 10, 20, 30,..110 numbers. The old algorithm is of worse time complexity (in blue). Comparison of algorithms.

1 comment

Paddy McCarthy (author) 11 years, 7 months ago  # | flag

The image did not come through above. Try this instead.