Given a list, find the indices used to get the elements from the list in sorted order
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | # Based on a post by Peter Otten on comp.lang.python 2004/09/04.
# This uses the 'key' option to sort and the 'sorted' function, both
# new in Python 2.4.
def permutation_indices(data):
return sorted(range(len(data)), key = data.__getitem__)
if __name__ == "__main__":
import sys
chars = "Sing a song of six-pence."
print chars
print "0 1 2 "
print "01234567890123456789012345"
print
indices = permutation_indices(chars)
for i in indices:
print "%4s %r" % (i, chars[i])
# Sing a song of six-pence.
# 0 1 2
# 01234567890123456789012345
#
# 4 ' '
# 6 ' '
# 11 ' '
# 14 ' '
# 18 '-'
# 24 '.'
# 0 'S'
# 5 'a'
# 22 'c'
# 20 'e'
# 23 'e'
# 13 'f'
# 3 'g'
# 10 'g'
# 1 'i'
# 16 'i'
# 2 'n'
# 9 'n'
# 21 'n'
# 8 'o'
# 12 'o'
# 19 'p'
# 7 's'
# 15 's'
# 17 'x'
|
Sometimes you need to know how a list would be sorted but not actually sort it. In the original context on comp.lang.python there was a histogram function which returned a list where the length of the list was the number of colors in the color table and the elements the repeat count of the corresponding color. To list the color values in order you need to find the position of the largest item in the histogram and get the color with the same index, then the second largest, etc.
The standard solution for this is the "DSU" (for Decorate-Sort-Undecorate), also called the Schwartzian transform from the Perl community. The 'key' parameter was added to sort in Python 2.4 to make it easier to do DSU. The key insight by Peter Otten is that the list to decorate isn't the input list, it's the indices list, and the input list's __getitem__ can be used to get the key for that index.
We benchmarked several other alternatives (see the thread "list conversion question") and this was the fastest and simplest.
O(n) access! Using indexing operation of lists is O(N). You should use dictionary instead.
I myself went into trouble, when manipulating a graph of over 3,00,000 vertices!
I don't understand what's meant by the first sentence of the discussion.
O(n) list indexing? I think not. TEST
OUTPUT
It doesn't seem to be O(n) for either n = length of list, or n = index value. Indeed, it would be quite mystifying if it were so as Python "Lists" are not lists in the LISP or "Linked List" sense but rather a sort of array that grows as necessary.
// Ben
(Big "O" notation) expresses... ...the efficiency of an operation (for example, the time required, or memory consumed) as a function of some measure of the size of the input.
O(n) means that the time require grows at the same rate as the size of the input. In this concrete example, it's unclear if the original poster meant n to reflect the size of the array or the index within the array being accessed.
More information can be found at: http://en.wikipedia.org/wiki/Big_O_notation
fixed typos. "permutaton" -> "permutation" in the title, and fixed first sentence.