5

リスト内の分割反転の数をカウントするために、マージソートを使用しようとしています（つまり、ソートされていないリストの前半の要素が、リストの後半の特定の要素の後に表示される必要があります）。ソートされていないリスト; たとえば、[3 2 1 4] には分割反転 (3, 1) が含まれますが、3 と 2 は両方とも前半にあるため (3, 2) は含まれません)。最後の print ステートメントにたどり着くと、期待どおりの答え (この場合は 9) が得られますが、再帰によって分割された値が返されるため、戻り値はすべて不安定です。あらゆる種類のインデックス作成の組み合わせを試しましたが、役に立ちませんでした。何か助けはありますか？(Python 2.7 を使用)

(記録として、これは Coursera の宿題の問題ですが、私はただの楽しみのために学習しているだけです。私以外にこの問題を採点している人はいません。)

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])
4

3 に答える 3

3

mergesort中間分割を無視するように関数を変更します。

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
于 2013-01-13T17:37:33.173 に答える
2

コードにいくつか問題があります。

  • int()の結果ではありませんlen() / 2。Python3を使用している場合は、//演算子で整数除算を直接使用します。
  • の最初の行の比較mergesort()は間違っています。isまず、平等を比較するために使用しないでください。オペレーターはis身元確認のみを目的としています。同じ値を持つ2つの異なる整数がある場合、それらは等しいが同一ではありません。小さい整数の場合、少なくとも一部のPython方言が値をインターンするため、比較は機能すると思いますが、保証されていないものに依存しています。それでも、==空のリストの場合を忘れたため、使用も機能しません。
  • 実際の問題（「不安定な戻り値」）は、1つの名前で（タプルとして）格納し、再帰merge()呼び出しにパラメーターとして渡す2つの値を返すという事実が原因だと思います。
于 2013-01-13T17:34:25.013 に答える