合并排序来算分割倒在Python [英] Merge sort to count split inversions in Python

问题描述

我想使用归并 - 这是我得到的 - 数列表中的分割反转的数量（即，其中在第一未排序的列表中一半的元素应该出现在第二个给定的元素之后一半的未分类的列表中的;例如[3 2 1 4]将包含分裂反转（3，1），但不是（3,2），为3和2都是在上）。当我到了最后的打印语句，我得到了答案，我期待的 - 在这种情况下，9 - 但返回值都是靠不住的，因为它的返回通过递归拆分值。我已经试过各种索引的组合都无济于事。任何帮助吗？ （使用Python 2.7）

（根据记录，这是一个Coursera功课的问题，但我只是学习的乐趣 - 没有一个人的评级这除了我）

 高清归并（LST）：
    '''递归分成两半进行排序列表'''
    如果len（LST）为1：
        回报LST
    中间= INT（LEN（LST）/ 2）
    左=归并（LST [：中]）
    右=归并（LST [中：]）
    排序列表=合并（左，右）
    返回排序列表

DEF合并（左，右）：
    '''归并的子程序来分割列表进行排序。同时返回数
    拆分倒置（即，一些从排序第二的每个occurence
    上半年出现了一批从排序上半场前列表）'''
    I，J = 0,0
    分裂= 0
    结果= []
    而I＆LT;的len（左）和j＆其中; LEN（右）：
        如果离开[1]  - ;正确的研究[J]：
            result.append（左[I]）
            I + = 1
        其他：
            result.append（右[J]。）
            J + 1 =
            拆分+ = LEN（左[我：]）
    结果+ =左[我：]
    结果+ =右[J：]
    打印结果，拆分
    返回结果，拆分


打印归并（[7,2,6,4,5,1,3,8]）
 

解决方案

修改你的归并函数忽略中间分裂。

 高清归并（LST）：
    '''递归分成两半进行排序列表'''
    如果len（LST）== 1：
        返回LST，0
    中间= LEN（LST）/ 2
    左=归并（LST [：中]）[0]＃忽略中间分裂
    右=归并（LST [中：]）[0]＃忽略中间分裂
    排序列表，分裂=合并（左，右）
    返回排序列表，拆分
 

I am trying to use mergesort--which I get--to count the number of split inversions in a list (that is, where an element in the first half of the unsorted list should appear after a given element in the second half of the unsorted list; for example [3 2 1 4] would contain the split inversion (3, 1), but not (3, 2) as 3 and 2 are both in the first half). When I get to the final print statement, I am getting the answer I expect--in this case 9--but the return value is all wonky since it's returning the split value through the recursion. I've tried all sorts of combinations of indexing to no avail. Any help? (using Python 2.7)

(For the record, this is a Coursera homework problem, but I'm just learning for fun--no one's grading this other than me.)

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) is 1:
        return lst
    middle = int(len(lst)/2)
    left  = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    sortedlist = merge(left, right)
    return sortedlist

def merge(left, right):
    '''Subroutine of mergesort to sort split lists.  Also returns number
    of split inversions (i.e., each occurence of a number from the sorted second
    half of the list appearing before a number from the sorted first half)'''
    i, j = 0, 0
    splits = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            splits += len(left[i:])
    result += left[i:]
    result += right[j:]
    print result, splits
    return result, splits


print mergesort([7,2,6,4,5,1,3,8])

解决方案

Modify your mergesort function to disregard the intermediate splits.

def mergesort(lst):
    '''Recursively divides list in halves to be sorted'''
    if len(lst) == 1:
        return lst, 0
    middle = len(lst)/2
    left = mergesort(lst[:middle])[0]  # Ignore intermediate splits
    right = mergesort(lst[middle:])[0]  # Ignore intermediate splits
    sortedlist, splits = merge(left, right)
    return sortedlist, splits

这篇关于合并排序来算分割倒在Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！