给定一个未排序的python列表,我如何找到排序所需的最小移动集

Question

我有一个存储在远程数据库中的项目列表,可能是未分类的,我想对它们进行排序.数据库接受它们的命令:

move item1 before item2
move item3 after item2

因此,给出一个表单列表:

[1,3,2,7,6,0,4]

......我怎样才能得到一系列动作:

move 2 before 3
move 7 after 6
move 0 before 1
move 4 before 6

我假设对bubblesort算法的修改可行,但我特别寻找仍然是pythonic的最有效的实现,并且生成最少的移动命令.

更新:列表长度为1000-10000,所有项目都是唯一的 - 没有重复.只有极少数项目 - 1-10 - 在任何给定时间都会出错.时间是一个问题 - 它应该需要几秒钟,而不是几分钟 - 但它不一定非常快.

更新2:我还想将每个项目仅移动一次

Answer 1

当你想减少移动序列的数量时，我能想到的最佳方法是在排序列表上使用二分搜索来确定每个元素的插入点。如果任何元素已经处于正确位置，则无需移动它。

这将生成n - d序列移动，其中n是元素数量，d是处于正确位置的元素数量。

• 对于已经排序的列表，序列移动的次数是n - d = n - n = 0
• 对于所有元素都位于错误位置的列表，序列移动的次数为n - d = n - 0 = n

执行

def gen_move(seq):
    from bisect import bisect_left
    out = seq[0:1]
    for elem in seq[1:]:
        index = bisect_left(out, elem)
        if seq[index] != elem:
            if index == 0:
                print "Move {} before {}".format(elem, out[index])
            else:
                print "Move {} after {}".format(elem, out[index - 1])
        out.insert(index, elem)
    print out

演示

gen_move([1,3,2,7,6,0,4])
Move 2 after 1
Move 6 after 3
Move 0 before 1
Move 4 after 3
[0, 1, 2, 3, 4, 6, 7]

gen_move(range(10)[::-1])
Move 8 before 9
Move 7 before 8
Move 6 before 7
Move 5 before 6
Move 4 before 5
Move 3 before 4
Move 2 before 3
Move 1 before 2
Move 0 before 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

gen_move(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

表现

In [5]: %timeit gen_move(range(10000, 0, -1))
10000 loops, best of 3: 84 us per loop

时间复杂度

sum(1 ln 1 + 2 ln 2 + 3 ln 3 + ..... n ln n) < O(n ln n)

空间复杂度

O(n)