Re: [Tutor] Sorting Nested Lists

[Walter Prins]

Hi,

On 9 January 2012 12:31, Sarma Tangirala  wrote:
> Given a nested list, how do I sort the uppermost list based on one key and
> when a special condition occurs a sort on another key should be performed?
>
> For example, [[1,2], [2, 2], [3, 2], [4, 0]] would be sorted, in my example
> as, [[4, 0], [3, 2], [2, 2], [1, 2]]. That is, sort on the second value and
> in case they are equal, reverse sort on the first value.
>
> I tried doing this using sorted and using a custom cmp function but not sure
> about how to define the cmp function.

See the following page (particularly the section that describes
"multiple levels of sorting") for how to do (I think) what you want
(though this does not use the compare function):
http://wiki.python.org/moin/HowTo/Sorting

If you really want to have this done via the compare function method
then post back again.

Walter
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Sorting Nested Lists

[Sarma Tangirala]

On 9 January 2012 18:26, Steven D'Aprano  wrote:

> Sarma Tangirala wrote:
>
>> Hi list,
>>
>> I was banging my head about a pythonic way of doing the following,
>>
>> Given a nested list, how do I sort the uppermost list based on one key and
>> when a special condition occurs a sort on another key should be performed?
>> For example, [[1,2], [2, 2], [3, 2], [4, 0]] would be sorted, in my
>> example
>> as, [[4, 0], [3, 2], [2, 2], [1, 2]]. That is, sort on the second value
>> and
>> in case they are equal, reverse sort on the first value.
>>
>
> That is not exactly a good example. There are at least two other ways to
> get the result you show, both much more obvious:
>
> py> L = [[1,2], [2, 2], [3, 2], [4, 0]]
> py> list(reversed(L))
>
> [[4, 0], [3, 2], [2, 2], [1, 2]]
> py> sorted(L, reverse=True)
>
> [[4, 0], [3, 2], [2, 2], [1, 2]]
>
>
> If I ignore your example, and just use the description:
>
> "sort on the second value, and in case they are equal, reverse sort on the
> first value"
>
> the way to do this is with a double sort. Note that this works because
> Python's sort is stable: in the event of ties, the first item remains
> first. In earlier versions of Python, this was not always the case.
>
> So, given this list:
>
> L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]
>
> first sort in reverse by the first item, then by the second:
>
>
> py> L.sort(key=lambda sublist: sublist[0], reverse=True)
> py> L.sort(key=lambda sublist: sublist[1])
> py> print L
> [[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]
>
>
>
> Note that using a key function is MUCH more efficient than a cmp function.
> Comparison functions end up doing much more work, and hence are very much
> slower, than a key function.
>
> Also note that in recent versions of Python, you can do without the lambda
> function and use the special "itemgetter" function:
>
>
> py> from operator import itemgetter
> py> L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]
> py> L.sort(key=itemgetter(0), reverse=True)
> py> L.sort(key=itemgetter(1))
> py> print L
> [[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]
>
>
I tried this a lot yesterday but seemed to get a wrong answer but now I
realize its because of a bad test case. Thank you.


>
> Last but not least, I will show how to do it using a custom cmp function.
> But I recommend that you don't use this!
>
> def my_cmp(list1, list2):
>x = cmp(list1[1], list2[1])
>if x == 0:  # a tie
>x = cmp(list2[0], list1[0])  # swap the order for reverse sort
># or if you prefer, x = -cmp(list1[0], list2[0])
>return x
>
> sorted(L, my_cmp)
>
>
>
>
> --
> Steven
> __**_
> Tutor maillist  -  Tutor@python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/**mailman/listinfo/tutor
>



-- 
Sarma Tangirala,
Class of 2012,
Department of Information Science and Technology,
College of Engineering Guindy - Anna University
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Sorting Nested Lists

[Peter Otten]

Sarma Tangirala wrote:

> I was banging my head about a pythonic way of doing the following,
> 
> Given a nested list, how do I sort the uppermost list based on one key and
> when a special condition occurs a sort on another key should be performed?
> 
> For example, [[1,2], [2, 2], [3, 2], [4, 0]] would be sorted, in my
> example as, [[4, 0], [3, 2], [2, 2], [1, 2]]. That is, sort on the second
> value and in case they are equal, reverse sort on the first value.
> 
> I tried doing this using sorted and using a custom cmp function but not
> sure about how to define the cmp function.

Python's list.sort() is "stable", it doesn't change the order of items that 
compare equal. Therefore you can achieve your goal by sorting twice:

>>> items = [[1,2], [2, 2], [3, 2], [0, 0]]
>>> items.sort(key=itemgetter(0), reverse=True)
>>> items
[[3, 2], [2, 2], [1, 2], [0, 0]]
>>> items.sort(key=itemgetter(1))
>>> items
[[0, 0], [3, 2], [2, 2], [1, 2]]

(I changed your last item to [0, 0] to allow me to demonstrate that two 
sorts are indeed necessary)

Using a more complex key is also possible,

>>> sorted([[1,2], [2, 2], [3, 2], [0, 0]], key=lambda item: (item[1], -
item[0]))
[[0, 0], [3, 2], [2, 2], [1, 2]]

but I think that is less elegant.

___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Sorting Nested Lists

[Steven D'Aprano]

Sarma Tangirala wrote:

Hi list,

I was banging my head about a pythonic way of doing the following,

Given a nested list, how do I sort the uppermost list based on one key and
when a special condition occurs a sort on another key should be performed?
For example, [[1,2], [2, 2], [3, 2], [4, 0]] would be sorted, in my example
as, [[4, 0], [3, 2], [2, 2], [1, 2]]. That is, sort on the second value and
in case they are equal, reverse sort on the first value.


That is not exactly a good example. There are at least two other ways to get 
the result you show, both much more obvious:


py> L = [[1,2], [2, 2], [3, 2], [4, 0]]
py> list(reversed(L))
[[4, 0], [3, 2], [2, 2], [1, 2]]
py> sorted(L, reverse=True)
[[4, 0], [3, 2], [2, 2], [1, 2]]


If I ignore your example, and just use the description:

"sort on the second value, and in case they are equal, reverse sort on the 
first value"


the way to do this is with a double sort. Note that this works because 
Python's sort is stable: in the event of ties, the first item remains first. 
In earlier versions of Python, this was not always the case.


So, given this list:

L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]

first sort in reverse by the first item, then by the second:


py> L.sort(key=lambda sublist: sublist[0], reverse=True)
py> L.sort(key=lambda sublist: sublist[1])
py> print L
[[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]



Note that using a key function is MUCH more efficient than a cmp function. 
Comparison functions end up doing much more work, and hence are very much 
slower, than a key function.


Also note that in recent versions of Python, you can do without the lambda 
function and use the special "itemgetter" function:



py> from operator import itemgetter
py> L = [[1,2], [4,0], [3,2], [2,2], [5,1], [1,1]]
py> L.sort(key=itemgetter(0), reverse=True)
py> L.sort(key=itemgetter(1))
py> print L
[[4, 0], [5, 1], [1, 1], [3, 2], [2, 2], [1, 2]]


Last but not least, I will show how to do it using a custom cmp function. But 
I recommend that you don't use this!


def my_cmp(list1, list2):
x = cmp(list1[1], list2[1])
if x == 0:  # a tie
x = cmp(list2[0], list1[0])  # swap the order for reverse sort
# or if you prefer, x = -cmp(list1[0], list2[0])
return x

sorted(L, my_cmp)




--
Steven
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor