6

I have a list of 10 items, and another list of 10 randomly not repeated numbers as following:

l = [a,b,c,d,e,f,g,h,i,j]
m = [1,4,5,9,2,6,3,7,8,10]

I want to rearrange l, so that each item in l takes its corresponding index from m.

For example, b should become the fourth and e sould become the second.

I'm really stuck at the algorithm and the logic bugs me, so I don't have any idea on how to approach thi.

How can I do that?

smci
  • 32,567
  • 20
  • 113
  • 146
Anis Souames
  • 334
  • 1
  • 4
  • 13
  • Why do you want to sort the list `l`? You can always just use the indexes from `m` directly in any calculation: `l[m[i] - 1]` – Code-Apprentice Jan 09 '17 at 14:21
  • 1
    @tobias_k I disagree with this duplicate. It's true that sorting `l` by `m` would produce the expected result, but "sorting" is not the same thing as "reordering". There are more efficient (i.e. `O(n)`) solutions to this problem than sorting, which is `O(n log n)`. I'd like to reopen this question. – Aran-Fey May 21 '18 at 11:11
  • It seems safe to assume `m` is the 10 distinct integers 1...10. No repetitions, no gaps, no non-integers. – smci May 22 '18 at 06:07

3 Answers3

14

If you're just trying to get elements moved around based on the other lists positions, you can loop over all elements of m and grab that element of l using list comprehension 

l2 = [l[i - 1] for i in m]

But if you do want the ordering based on the other list, you're going to need to zip them together, sort on the index, then extract the elements

[y for x,y in sorted(zip(m,l))]
OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
  • I love you... Ordering based on another list (your second example) is something I was trying to figure out for a good while. – Jakey May 21 '18 at 11:00
3

Note: I'm assuming that m is always contiguous (i.e. there are no "gaps"), and starts at 1.

If so, you can get what you want quite easily, using a list comprehension, zip() and sorted().

Let's take it step by step:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
>>> m = [1, 4, 5, 9, 2, 6, 3, 7, 8, 10]

zip() pairs each element of m with an element of l:

>>> zip(m, l)
[(1, 'a'), (4, 'b'), (5, 'c'), (9, 'd'), (2, 'e'), (6, 'f'), (3, 'g'), (7, 'h'), (8, 'i'), (10, 'j')]

sorted() returns a sorted copy of the list of pairs:

>>> sorted(zip(m, l))
[(1, 'a'), (2, 'e'), (3, 'g'), (4, 'b'), (5, 'c'), (6, 'f'), (7, 'h'), (8, 'i'), (9, 'd'), (10, 'j')]

Finally, a list comprehension takes just the second item from each pair:

>>> [x for i, x in sorted(zip(m, l))]
['a', 'e', 'g', 'b', 'c', 'f', 'h', 'i', 'd', 'j']
Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
0

This can be done in linear O(n) time with the help of a dict:

l = ['a','b','c','d','e','f','g','h','i','j']
m = [ 1,  4,  5,  9,  2,  6,  3,  7,  8,  10]

values_by_index = dict(zip(m, l))
result = [values_by_index[index+1] for index in range(len(m))]

print(result)
# output: ['a', 'e', 'g', 'b', 'c', 'f', 'h', 'i', 'd', 'j']

The first line creates dict that maps indices to values, which looks like this:

>>> values_by_index
{1: 'a', 4: 'b', 5: 'c', 9: 'd', 2: 'e', 6: 'f', 3: 'g', 7: 'h', 8: 'i', 10: 'j'}

In the second line we simply loop over the indices 1 through 10 and grab the corresponding value from the dict, which is a O(1) operation in the average case.

If you have 0-based indices, simply remove the +1 from index+1.

Aran-Fey
  • 39,665
  • 11
  • 104
  • 149