Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #Count Inversions
- #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
- # uses python3
- #NOTE: ONLY MINIMAL TESTING DONE AT THIS POINT
- #todo: test more lists
- import logging as log
- def merge_count(list0, list1):
- log.info("Merging ", list0, list1)
- count = 0
- merged = []
- while list0 and list1:
- if list0[0] <= list1[0]:
- merged.append(list0.pop(0))
- else:
- merged.append(list1.pop(0))
- count += len(list0)
- merged += list0
- merged += list1
- log.info("Result: ", merged, " counted ", count, " inversions")
- return(merged, count)
- def Count_Inversions(inv_list, inversions = 0):
- log.info("Processing ", inv_list, " with inv count ", inversions)
- #base case
- length = len(inv_list)
- if length <= 1:
- log.info("hit bottom with list ", inv_list, " inv count ", inversions)
- return (inv_list,0)
- #recursive case
- index = int(length/2)
- list0 = inv_list[:index]
- list1 = inv_list[index:]
- log.info("Splitting ", inv_list, " into ", list0, " and ", list1)
- left = Count_Inversions(list0)
- right = Count_Inversions(list1)
- #mc = merge_count(list0, list1)
- merged = merge_count(left[0],right[0])
- return (merged[0], left[1] + right[1] + merged[1])
Advertisement
Add Comment
Please, Sign In to add comment