我正在定义一个Python函数来执行贪婪排序。
(生物信息学算法I,2014,Coursera-Stepic 6.4
排序的结果应该是[+1,+2,+3,+4,+5],函数还应该返回初始输入列表中的所有更改步骤。
要对初始输入列表进行排序,必须执行几个反转步骤。它很像pancake flipping problem。在这个问题中,有符号置换([-3,+4,+1,+5,-2])应该改为恒等符号置换([+1,+2,+3,+4,+5])。
样本输入:

 [-3, +4, +1, +5, -2]

样本输出:
[[-1, -4, +3, +5, -2],
 [+1, -4, +3, +5, -2],    # -1  ->  +1
 [+1, +2, -5, -3, +4],    # reversal of (-4, +3, +5, -2)
 [+1, +2, +3, +5, +4],    # reversal of (-5, -3)
 [+1, +2, +3, -4, -5],    # reversal of (+5, +4)
 [+1, +2, +3, +4, -5],    # -4  ->  +4
 [+1, +2, +3, +4, +5]]    # -5  ->  +5   Sorting finished!

我写了一个函数,但结果不正确。
# Implementation
def reversing(seq):
    """
    >>> reversing([+1,+2,-3,-4])
        [+4,+3,-2,-1]
    """
    seq.reverse()
    seq = map(lambda(x): -x, seq)
    return seq


def greedySorting1(lst):
    """
    ApproxReversalDistance (ARD)
    Return a number (ARD) until the result is [1,2,...,n]
    >>> greedySorting1([1,-5,3,-2,-4])
        6
    """
    change = []
    ARD = 0

    for i in range(len(lst)):
        if lst[i] != i+1:
            if i+1 in lst:
                id_i = lst.index(abs(i+1))
            else:
                id_i = lst.index(-abs(i+1))
            lst = lst[:i] + reversing(lst[i:id_i+1]) + lst[id_i+1:]
            ARD += 1
            change.append(lst)
        if lst[i] == -(i+1):
            lst[i] = i+1
            ARD += 1
            change.append(lst)

    return change




# Testing
print greedySorting([-3,+4,+1,+5,-2])

    [[+1, -4, +3, +5, -2],    # Wrong: +1 should be -1
     [+1, -4, +3, +5, -2],
     [+1, +2, -5, -3, +4],
     [+1, +2, +3, +5, +4],
     [+1, +2, +3, +4, -5],    # Wrong: +4 should be -4
     [+1, +2, +3, +4, -5],
     [+1, +2, +3, +4, +5]]

如何修复代码以获得正确的答案(如示例输出)?
谢谢。

最佳答案

这里您正在修改lst位置,因此在change中对它的任何引用都将反映相同的更改

if lst[i] == -(i+1):

您可以确保使用change复制lst[:]中的列表以“分离”
for i in range(len(lst)):
    if lst[i] != i+1:
        if i+1 in lst:
            id_i = lst.index(abs(i+1))
        else:
            id_i = lst.index(-abs(i+1))
        lst = lst[:i] + reversing(lst[i:id_i+1]) + lst[id_i+1:]
        ARD += 1
        change.append(lst[:])
    if lst[i] == -(i+1):
        lst[i] = i+1
        change.append(lst[:])

现在您还可以简化这一行:
lst = lst[:i] + reversing(lst[i:id_i+1]) + lst[id_i+1:]


lst[i: id_i + 1] = reversing(lst[i: id_i + 1])

10-06 05:19
查看更多