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

This function takes a permutation in the form of a list and returns the number of inversions in the permutation.

Python, 17 lines
 1
 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)

Created by Samuel James Erickson on Tue, 5 May 2015 (MIT)
Python recipes (4591)
Samuel James Erickson's recipes (4)

Required Modules

  • (none specified)

Other Information and Tasks