python - python中的贪心排序

Question

我正在定义一个执行贪婪排序的 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]]

如何修复我的代码以获得正确的答案，例如示例输出？
谢谢。

Answer 1

此处您正在就地修改 lst，因此在 change 中对它的任何引用都将反射(reflect)相同的更改

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

您可以通过使用 lst[:] 制作副本来确保“解耦”change 中的列表

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