abbarnes

Count Inversions [Python 3]

Jan 21st, 2018
306
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.36 KB | None | 0 0
  1. #Count Inversions
  2. #Counts the number of inversions in a list.  Inverions defined as occurence of list[i] > list[j] for all combinations of i,j where i<j
  3. # uses python3
  4.  
  5. #NOTE:  ONLY MINIMAL TESTING DONE AT THIS POINT
  6. #todo: test more lists
  7.  
  8. import logging as log
  9.  
  10. def merge_count(list0, list1):
  11.     log.info("Merging ", list0, list1)
  12.     count = 0
  13.     merged = []
  14.     while list0 and list1:
  15.         if list0[0] <= list1[0]:
  16.             merged.append(list0.pop(0))
  17.         else:
  18.             merged.append(list1.pop(0))
  19.             count += len(list0)
  20.     merged += list0
  21.     merged += list1
  22.     log.info("Result:  ", merged, " counted ", count, " inversions")
  23.     return(merged, count)
  24.  
  25. def Count_Inversions(inv_list, inversions = 0):
  26.     log.info("Processing ", inv_list, " with inv count ", inversions)
  27.     #base case
  28.     length = len(inv_list)
  29.     if length <= 1:
  30.         log.info("hit bottom with list ", inv_list, " inv count ", inversions)
  31.         return (inv_list,0)
  32.     #recursive case
  33.     index = int(length/2)
  34.     list0 = inv_list[:index]
  35.     list1 = inv_list[index:]
  36.     log.info("Splitting ", inv_list, " into ", list0, " and ", list1)
  37.  
  38.     left = Count_Inversions(list0)
  39.     right = Count_Inversions(list1)
  40.     #mc = merge_count(list0, list1)
  41.     merged = merge_count(left[0],right[0])
  42.     return (merged[0], left[1] + right[1] + merged[1])
Advertisement
Add Comment
Please, Sign In to add comment