python 中的贪婪排序

Question

我正在定义一个执行贪婪排序的 Python 函数。
（生物信息学算法 I，2014 年，Coursera - Stepic 6.4）

排序的结果应该是 [+1, +2, +3, +4, +5] 并且函数也应该 return 从初始输入列表开始的所有变化步骤。

要对初始输入列表进行排序，几个反转步骤是必不可少的。它很像 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

当我解决这个问题时，我发现用两个匹配的索引数组中的符号和数字来解决这个问题要容易得多，并且在每次迭代时复制列表和符号以用作参考（不就 runtime/memory 分配而言，伤害和你想的一样多。

另一件对您有帮助的事情是使用嵌套 for 循环，以帮助您跟踪 "reversal".

中数字和符号的切换

Answer 2

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

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

您可以确保 "decouple" 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])

python 中的贪婪排序

GreedySorting in python

python

algorithm

greedy