How can I reorder a list?

Question

Given an arbitrary array of size n, I'd like to reorganize the elements of the array based on the array's discrete indices.

Python example:

# Unique array of size n
[ "a", "b", "c", "d", "e", ... <n> ]

# Indices of array
[ 0, 1, 2, 3, 4, ... <index_of_n> ]

# Desired re-organization function 'indexMove'
indexMove(
    [ "a", "b", "c", "d", "e", ... <n> ],
    [ <index_of_n>, 4, 0, 2, 3, ... 1 ]
)

# Desired output from indexMove operation
[ <n>, "e", "a", "c", "d", ... "b" ]

What is the fastest way to perform this operation (achieving the smallest time complexity)?

Answer 1

You can do it like this

mylist = ['a', 'b', 'c', 'd', 'e']
myorder = [3, 2, 0, 1, 4]
mylist = [mylist[i] for i in myorder]
print(mylist)         # prints: ['d', 'c', 'a', 'b', 'e']

Answer 2

>>> a = [1, 2, 3]
>>> a[0], a[2] = a[2], a[0]
>>> a
[3, 2, 1]

Answer 3

>>> import random
>>> x = [1,2,3,4,5]
>>> random.shuffle(x)
>>> x
[5, 2, 4, 3, 1]

Answer 4

Is the final order defined by a list of indices ?

>>> items = [1, None, "chicken", int]
>>> order = [3, 0, 1, 2]

>>> ordered_list = [items[i] for i in order]
>>> ordered_list
[<type 'int'>, 1, None, 'chicken']

edit: meh. AJ was faster... How can I reorder a list in python?

Answer 5

>>> a=["a","b","c","d","e"]
>>> a[0],a[3] = a[3],a[0]
>>> a
['d', 'b', 'c', 'a', 'e']

Answer 6

You can provide your own sort function to list.sort():

The sort() method takes optional arguments for controlling the comparisons.

• cmp specifies a custom comparison function of two arguments (list items) which should return a negative, zero or positive number depending on whether the first argument is considered smaller than, equal to, or larger than the second argument: cmp=lambda x,y: cmp(x.lower(), y.lower()). The default value is None.

• key specifies a function of one argument that is used to extract a comparison key from each list element: key=str.lower. The default value is None.

• reverse is a boolean value. If set to True, then the list elements are sorted as if each comparison were reversed.

In general, the key and reverse conversion processes are much faster than specifying an equivalent cmp function. This is because cmp is called multiple times for each list element while key and reverse touch each element only once.

Answer 7

If you use numpy there's a neat way to do it:

items = np.array(["a","b","c","d"])
indices = np.arange(items.shape[0])
np.random.shuffle(indices)
print(indices)
print(items[indices])

This code returns:

[1 3 2 0]
['b' 'd' 'c' 'a']

Answer 8

If you do not care so much about efficiency, you could rely on numpy's array indexing to make it elegant:

a = ['123', 'abc', 456]
order = [2, 0, 1]
a2 = list( np.array(a, dtype=object)[order] )

Answer 9

One more thing which can be considered is the other interpretation as pointed out by darkless

Code in Python 2.7

Mainly:

1. Reorder by value - Already solved by AJ above

2. Reorder by index

   mylist = ['a', 'b', 'c', 'd', 'e']
   myorder = [3, 2, 0, 1, 4]
   
   mylist = sorted(zip(mylist, myorder), key=lambda x: x[1])
   print [item[0] for item in mylist]
   

This will print ['c', 'd', 'b', 'a', 'e']

Answer 10

From what I understand of your question, it appears that you want to apply a permutation that you specify on a list. This is done by specifying another list (lets call it p) that holds the indices of the elements of the original list that should appear in the permuted list. You then use p to make a new list by simply substituting the element at each position by that whose index is in that position in p.

def apply_permutation(lst, p):
    return [lst[x] for x in p]

arr=list("abcde")
new_order=[3,2,0,1,4]

print apply_permutation(arr,new_order)

This prints ['d', 'c', 'a', 'b', 'e'].

This actually creates a new list, but it can be trivially modified to permute the original "in place".

Answer 11

newList = [oldList[3]]
newList.extend(oldList[:3])
newList.extend(oldList[4:])

Answer 12

This is what I used when I stumbled upon this problem.

def order(list_item, i): # reorder at index i
    order_at = list_item.index(i)
    ordered_list = list_item[order_at:] + list_item[:order_at]
    return ordered_list

EX: for the the lowercase letters

order(string.ascii_lowercase, 'h'):
>>> 'hijklmnopqrstuvwxyzabcdefg'

It simply just shifts the list to a specified index