The parity of a given permutation is whether an odd or even number of swaps between any two elements are needed to transform the given permutation to the first permutation.
The sign of the permutation is +1 for an even parity and -1 for an odd parity.
This python function returns the sign of a permutation of all the integers 0..N. When the program is run it shows the sign of permutations as generated by the standard function itertools.permutations.
The function uses a modified selection sort to compute the parity.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def perm_parity(lst):
'''\
Given a permutation of the digits 0..N in order as a list,
returns its parity (or sign): +1 for even parity; -1 for odd.
'''
parity = 1
for i in range(0,len(lst)-1):
if lst[i] != i:
parity *= -1
mn = min(range(i,len(lst)), key=lst.__getitem__)
lst[i],lst[mn] = lst[mn],lst[i]
return parity
if __name__ == '__main__':
from itertools import permutations
for p in permutations(range(3)):
l = list(p)
print "%2i %r" % (perm_parity(l), p)
|
I came across the use of sign and parity when looking at how the determinant of a matrix can be described. I found that the Python permutations where not generated in alternating parity order, which can be done, so wanted to take a look at what the parity pattern was.