如何就地对列表应用置换？（排序键的逆）

Question

这是我想做的一个例子

spam_list = ["We", "are", "the", "knights", "who", "say", "Ni"]
spam_order = [0,1,2,4,5,6,3]
spam_list.magical_sort(spam_order)
print(spam_list)

["We", "are", "the", "who", "say", "Ni", "knights"]

我可以用 enumerate、list 等方法来实现，但我想直接对 spam_list 进行操作，就像 list.sort() 那样，而不是像 sorted() 那样复制一份

编辑：我加了一个字符串的例子，以避免在 spam_list 的索引和数值之间产生混淆

编辑：结果发现这个问题和 Python 如何就地排序并行数组？ 是重复的。好吧，我不能因为一致性的问题就删除这么多的努力。

Answer 1

但是我想直接影响 spam_list，就像 list.sort() 一样，而不是像 sorted() 那样复制它。

其实只有一个解决方案，正好满足你的要求。其他所有的解决方案都隐含地在复制一个或两个列表（或者把它变成字典等）。你想要的是一种方法，可以在原地对两个列表进行排序，使用 O(1) 的额外空间，并且用一个列表作为另一个列表的键。我个人是愿意接受额外的空间复杂度的，但如果你真的想这样做，可以试试这个：

(补充：原提问者可能并不在乎 .sort 的效率，而是因为它会改变状态；一般来说，这种需求是比较危险的，非底层语言会尽量避免甚至禁止这种情况，但使用切片赋值的解决方案会实现“原地”语义)

• 创建一个自定义字典子类（实际上是一个 Zip 类），它由你要排序的两个列表支持。
• 索引 myZip[i] 会返回元组 (list1[i],list2[i])
• 赋值 myZip[i]=(x1,x2) 会转化为 list1[i]=x1, list2[i]=x2。
• 用这个来执行 myZip(spam_list,spam_order).sort()，现在 spam_list 和 spam_order 都是在原地排序的。

示例：

#!/usr/bin/python3

class LiveZip(list):
    def __init__(self, list1, list2):
        self.list1 = list1
        self.list2 = list2

    def __len__(self):
        return len(self.list1)

    def __getitem__(self, i):
        return (self.list1[i], self.list2[i])

    def __setitem__(self, i, tuple):
        x1,x2 = tuple
        self.list1[i] = x1
        self.list2[i] = x2

spam_list = ["We", "are", "the", "knights", "who", "say", "Ni"]
spam_order = [0,1,2,4,5,6,3]

#spam_list.magical_sort(spam_order)
proxy = LiveZip(spam_order, spam_list)

现在我们来看看它是否有效...

#proxy.sort()
#fail --> oops, the internal implementation is not meant to be subclassed! lame
# It turns out that the python [].sort method does NOT work without passing in
# a list to the constructor (i.e. the internal implementation does not use the
# public interface), so you HAVE to implement your own sort if you want to not
# use any extra space. This kind of dumb. But the approach above means you can 
# just use any standard textbook in-place sorting algorithm:
def myInPlaceSort(x):
    # [replace with in-place textbook sorting algorithm]

现在它有效了：

myInPlaceSort(proxy)

print(spam_list)

不幸的是，没有办法只在 O(1) 空间内排序一个列表而不排序另一个；如果你不想排序两个列表，那你不如用你最初的方法，构建一个虚拟列表。

不过你可以这样做：

spam_list.sort(key=lambda x:x)

但如果 key 或 cmp 函数引用了任何集合（例如，如果你传入了一个你必须构建的字典的 dict.__getitem__），这和你最初的 O(N) 空间方法没有什么区别，除非你恰好有这样的字典。

结果发现这是一个重复的问题，链接是 Python sort parallel arrays in place?，但那个问题也没有正确答案，除了 这个，它和我的答案等效，但没有示例代码。除非你有非常优化或专业的代码，我建议你还是用你最初的解决方案，它在空间复杂度上和其他解决方案是等效的。

补充2：

正如 senderle 指出的，提问者其实并不想排序，而是想应用一个排列。要实现这个，你可以并且应该使用其他答案建议的简单索引 [spam_list[i] for i in spam_order]，但仍然必须进行显式或隐式的复制，因为你仍然需要中间数据。（无关紧要，记录一下，应用逆排列我认为是并行排序与恒等的逆，你可以用一个来得到另一个，尽管排序的时间效率较低。_,spam_order_inverse = parallelSort(spam_order, range(N))，然后按 spam_order_inverse 排序。我把上面的排序讨论留作记录。）

补充3：

不过，可以在 O(#cycles) 空间内实现原地排列，但时间效率很差。每个排列都可以分解为在子集上并行应用的离散排列。这些子集称为循环或轨道。周期等于它们的大小。因此，你可以大胆尝试如下操作：

Create a temp variable.

For index i=0...N:
    Put x_i into temp, assign NULL to x_i
    Swap temp with x_p(i)
    Swap temp with x_p(p(i))
    ...
    Swap temp with x_p(..p(i)..), which is x_i
    Put a "do not repeat" marker on the smallest element you visited larger than i
    Whenever you encounter a "do not repeat" marker, perform the loop again but
      without swapping, moving the marker to the smallest element larger than i    
    To avoid having to perform the loop again, use a bloom filter

这将在 O(N^2) 时间和 O(#cycles) 空间内运行，如果不使用布隆过滤器，或者如果使用它们，则大约是 O(N) 时间和 O(#cycle + bloomfilter_space) 空间。

Answer 2

你可以给排序函数一个特别的 key 参数：

order = dict(zip(spam_list, spam_order))
spam_list.sort(key=order.get)

补充：正如 @ninjagecko 在 他的回答 中指出的，这种方法其实效率不高，因为它会复制两个列表来创建查找用的字典。不过，根据提问者给出的修改示例，这是唯一的方法，因为必须建立一些索引。好处是，对于字符串来说，值不会被复制，所以额外的开销仅仅是字典本身的开销。

Answer 3

你可以试试：

spam_list = [spam_list[i] for i in spam_order]