This function takes a permutation in the form of a list and returns the number of inversions in the permutation.
Python, 17 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def inversion(permList):
"""
Description - This function returns the number of inversions in a
permutation.
Preconditions - The parameter permList is a list of unique positve numbers.
Postconditions - The number of inversions in permList has been returned.
Input - permList : list
Output - numInversions : int
"""
if len(permList)==1:
return 0
else:
numInversion=len(permList)-permList.index(max(permList))-1
permList.remove(max(permList))
return numInversion+inversion(permList)
|
A user would want to use this function to find the number of inversions in a permutation. I choose to use a recursive function because it makes the function more readable. There are no known issues.
References: http://mathworld.wolfram.com/PermutationInversion.html,
https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)
