我正在定义一个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])