💡 Problem Formulation: Determining the relative order of elements in a list is a common task in Python. This article addresses how to map the elements of a list to their corresponding indices in a sorted version of the list. For instance, given the input list [3, 1, 2], the desired output would be [2, 0, 1], which is the index of each element in the sorted list [1, 2, 3].
Method 1: Using Enumerate and Sorted
This method involves creating an enumeration of the input list, sorting it by values, and then mapping the original indices to their position in the sorted list. It’s straightforward but may not be the most efficient for very large lists due to the creation of intermediate tuples.
Here’s an example:
lst = [3, 1, 2] sorted_lst = sorted(enumerate(lst), key=lambda x: x[1]) indices = [index for rank, (index, value) in enumerate(sorted_lst)] print(indices)
Output:
[2, 0, 1]
This code snippet uses the enumerate function to pair each element with its index, sorts this pair list by the elements, and then extracts the original indices in the order that reflects their ranks in the sorted list.
Method 2: Using Argsort via NumPy
NumPy provides an argsort function that returns the indices that would sort an array. This is an efficient and vectorized solution, best suited for numeric data and when already working within the NumPy ecosystem.
Here’s an example:
import numpy as np lst = [3, 1, 2] indices = np.argsort(lst).tolist() print(indices)
Output:
[1, 2, 0]
This snippet uses the np.argsort() function, which returns an array of indices that would sort the original list. Here, tolist() converts the resulting NumPy array back into a Python list.
Method 3: Using a Dictionary Comprehension
A dictionary comprehension can be used to create a mapping from list values to their indices in a single pass. This can be especially useful when dealing with unique elements and requires no imports. The dictionary will hold elements as keys and their order in the sorted array as values.
Here’s an example:
lst = [3, 1, 2]
index_map = {val: idx for idx, val in enumerate(sorted(lst))}
indices = [index_map[x] for x in lst]
print(indices)Output:
[2, 0, 1]
This code creates a dictionary index_map where each list item maps to its respective index in the sorted list. Then it loops through the original list and creates indices, an ordered list of indices.
Method 4: Using Sort and Lambda
Python’s sort method can be cleverly used with a lambda function that keeps track of the indices of elements as they are being sorted. This method is similar to the first, but it uses the list’s own sort method, which can be more efficient than sorted().
Here’s an example:
lst = [3, 1, 2] indexed_lst = list(enumerate(lst)) indexed_lst.sort(key=lambda x: x[1]) indices = [index for index, value in indexed_lst] print(indices)
Output:
[2, 0, 1]
This snippet works by first creating a list of tuples, where each tuple is an (index, value) pair. Then, it sorts this list based on the values, and finally, it extracts only the indices, which reflect the order of values if sorted.
Bonus One-Liner Method 5: Using List Comprehension and the index() Method
This succinct method uses a list comprehension to map each element in the original list to its index in the sorted list. Note that this method is not optimal for large lists or lists with non-unique elements due to the repeated call to index().
Here’s an example:
lst = [3, 1, 2] sorted_lst = sorted(lst) indices = [sorted_lst.index(x) for x in lst] print(indices)
Output:
[2, 0, 1]
The above code sorts the list and then for each element in the original list, it finds the index of that element in the sorted list, mapping it to its relative order.
Summary/Discussion
- Method 1: Enumerate and Sorted. Easy to understand. Intermediate memory usage due to tuple creation.
- Method 2: Argsort via NumPy. Highly efficient and concise. Requires NumPy and thereby breaks purity of Python only solution.
- Method 3: Dictionary Comprehension. Elegant one-liner. Assumes unique list elements.
- Method 4: Sort and Lambda. In-place sorting. Less memory overhead but mutates the original list.
- Method 5: List Comprehension with
index(). Very concise. Inefficient for large or repetitive lists.