Miles semanticist at gmail.com
Fri Mar 13 20:13:25 CET 2009


On Fri, Mar 13, 2009 at 2:12 PM, John Posner wrote:
>
>>     I have 2 lists
>> a = [(4, 1), (7, 3), (3, 2), (2, 4)]
>> b = [2, 4, 1, 3]
>>
>>     Now, I want to order _a_ (a[1]) based on _b_.
>>     i.e. the second element in tuple should be the same as
>> b.
>>     i.e. Output would be [(3, 2), (2, 4), (4, 1), (7, 3)]
>
> Essentially, you're sorting a list. The Pythonic approach is to use the sort() function, hiding the details in a "custom comparison function":
>
> def compare_func(first, second):
>    b = [2, 4, 1, 3]
>    return cmp(b.index(first[1]), b.index(second[1]))
>
> if __name__ == '__main__':
>    a = [(4, 1), (7, 3), (3, 2), (2, 4)]
>    a.sort(cmp=compare_func)
>    print a

A version that runs in O(n ln n) instead of O(n^2 ln n):

a = [(4, 1), (7, 3), (3, 2), (2, 4)]
b = [2, 4, 1, 3]
bdict = dict((v,k) for (k,v) in enumerate(b))
a.sort(key=lambda k: bdict[k[1]])

If you don't want to build the intermediary dict, a less efficient
version that runs in O(n^2):

a.sort(key=lambda k: b.index(k[1]))

Which is mostly similar to John's solution, but still more efficient
because it only does a b.index call once per 'a' item instead of twice
per comparison.

-Miles



More information about the Python-list mailing list