CODEWITHSUNDEEP
pythonalgorithmlistdata-structures
stav
stav

Reputation: 1775

Rearrange list based on key WITHOUT sorting

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?

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.

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)]

Upvotes: 2

Views: 217

Answers (3)

cs95
cs95

Reputation: 402852

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.

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)

Upvotes: 5

Gassa
Gassa

Reputation: 8844

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))).

Upvotes: 0

Reut Sharabani
Reut Sharabani

Reputation: 31339

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

Upvotes: 2

Related Questions