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

#### 1 comment

Paddy McCarthy (author) 11 years, 9 months ago

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

 Created by Paddy McCarthy on Tue, 7 Aug 2012 (MIT)

### Required Modules

• (none specified)