マージソートを使用して反転を数えるアルゴリズムが失敗するケース

Question

数字の配列の逆数を数えるために次のコードを書いています。それをテストした入力に対して正しい結果が得られますテストケース、私はテストケースにアクセスできないが、どのケースが失敗するかを知ることができないので、実際にここでいくつかの助けをすることができる。

def count_inversion(array): 
     """ 
     counts number of inversions in array using divide and conquer 
     an inversion is a pair (x,y) such that x > y, example in array 
     [3,1,2] there are two inversions (3,1), (3,2) 
     """ 
     length = len(array) 
     if length == 1 or length == 0: 
      return array,0 
     elif length == 2: 
      if array[0] > array[1]: 
       array.sort() 
       return array,1 
      else: 
       return array,0 
     else: 
      left_array,left_count = count_inversion(array[:length/2]) 
      right_array,right_count = count_inversion(array[length/2:]) 
      across_arr,across_count = count_split(left_array,right_array) 
      return across_arr,left_count + right_count + across_count 

def count_split(left,right): 
    """ 
    counts the number of inversions across split pair 
    left and right, by piggy backing on merge routine 
    of merge sort 
    """ 
    l = 0 
    r = 0 
    merge = [] 
    count = 0 
    inversions = 0 
    last_r = 0 
    try: 
     while True: 
      if left[l] > right[r]: 
       merge.append(right[r]) 
       if r == 0 or r == last_r: 
        inversions = 0 
       inversions += 1 
       r = r + 1 
      else: 
       merge.append(left[l]) 
       count = count + inversions 
       l = l + 1 
       last_r = r 

    except IndexError: 
     if r == len(right): 
      while l < len(left): 
       count += inversions 
       merge.append(left[l]) 
       l = l + 1 
     else: 
      while r < len(right): 
       merge.append(right[r]) 
       r = r + 1 
    return merge,count 

if __name__ == '__main__': 
    f = open('inversions.txt') 
    arr = [] 
    for line in f: 
     arr.append(int(line)) 
    # arr is a list of integers which are not sorted in any sense 
    # we are required to count number of inversions in arr 
    print count_inversion(arr)[1] 

Answer 1

てみ

3 4 6 1 2 5 

あなたの答え - 5
本当の答え - 7

これは宿題/オンライン裁判官のように、においが、私はあなたのミスがどこかにあると言うでしょう例外ブロック内。