重新排列基于键的排序列表

I have a list of tuples (x, ind) where x is the item and ind is it's target index in the resulting list. The list is in random order, but it can be assumed that if there are N items in the list, the values of ind in the tuples will be in [0,N) without repetition (i.e. all the valid indices will exist exactly once). How do I get a list where each tuple's position is ind?

我有一个元组列表（x，ind），其中x是项目，ind是结果列表中的目标索引。列表是随机顺序，但可以假设如果列表中有N个项目，则元组中ind的值将在[0，N]中不重复（即所有有效索引将只存在一次） 。如何获得每个元组位置的列表？

Please do not confuse with the many existing answers of how to sort by key.

请不要混淆如何按键排序的许多现有答案。

Obviously, sorting by the ind key is easy, but there would be the unnecessary extra O(n*logn) cost to what should be a O(n) operation because of the aforementioned assumption about ind values.

显然，使用ind键进行排序很容易，但由于上述关于ind值的假设，因此应该是O（n）操作的不必要的额外O（n * logn）成本。

So:

所以：

l = [('item1',1), ('item0',0), ('item2',2), ('item4',4), ('item3',3)]
l2 = magic_rearrange(l, key=lambda x: x[1])
print(l2)

Should give:

应该给：

[('item0',0), ('item1',1), ('item2',2), ('item3',3), ('item4',4)]

3 个解决方案

#1

Assuming your indices are unique, here's one way. You can initialise a new list and just insert elements in their right position.

假设您的指数是唯一的，这是一种方法。您可以初始化新列表，只需将元素插入正确的位置即可。

def magic_rearrange(l1):
    l2 = [None] * len(l1)
    for i in l1:
        l2[i[1]] = i
    return l2

And a demo:

还有一个演示：

>>> l = [('item1',1), ('item0',0), ('item2',2), ('item4',4), ('item3',3)]
>>> magic_rearrange(l)
[('item0', 0), ('item1', 1), ('item2', 2), ('item3', 3), ('item4', 4)]

---

There's a quicker way to do this, if you use numpy's fancy indexing.

如果你使用numpy的花式索引，有一种更快的方法。

import numpy as np
def magic_rearrange(l1):
    l2 = np.repeat(None, len(l1))
    l2[[x[1] for x in l1]] = l1
    return l2

And a demo:

还有一个演示：

>>> magic_rearrange(l)
array([('item0', 0), ('item1', 1), ('item2', 2), ('item3', 3), ('item4', 4)], dtype=object)

#2

Create the list first and then replace:

首先创建列表，然后替换：

def magic_rearrange(l, key):
   # creates list to not change original list
   new_list = list(l)
   # reorder on new list
   for original_index, new_index in enumerate(map(key, l)):
       new_list[new_index] = l[original_index]
   return new_list

#3

Here you go.

干得好。

def magic_rearrange (input_list, key = lambda x: x):
    result_list = [None] * len (input_list)
    for p in input_list:
        result_list[key (p)] = p
    return result_list

We just create a list of the desired length, and then put each element in its place. The order of operations can be arbitrary, but each element will eventually get to its position in the resulting list. This is O(N) if copying a single list element and obtaining the key are both O(1). The key = lambda x: x is for the default order, which is comparing the whole elements (however useless since the result is just list(range(N))).

我们只创建一个所需长度的列表，然后将每个元素放在其位置。操作顺序可以是任意的，但每个元素最终都会到达结果列表中的位置。如果复制单个列表元素并且获得密钥都是O（1），则这是O（N）。 key = lambda x：x用于默认顺序，它比较整个元素（但是无用，因为结果只是list（range（N）））。