Take the 2-minute tour ×

Hi: I'm trying to sort a list of tuples in a custom way:
For example:

lt = [(2,4), (4,5), (5,2)]

must be sorted:

lt = [(5,2), (2,4), (4,5)]

* b tuple is greater than a tuple if a[1] == b[0]
* a tuple is greater than b tuple if a[0] == b[1]

I've implemented a cmp function like this:

def tcmp(a, b):
    if a[1] == b[0]:
       return -1
    elif a[0] == b[1]:
       return 1
       return 0

but sorting the list:


lt show me:

lt = [(2, 4), (4, 5), (5, 2)]

What am I doing wrong?

share|improve this question
I see nothing wrong, except that given your input and comparison function, your initial list is already sorted. –  Ignacio Vazquez-Abrams Dec 29 '10 at 12:38
... And what if a[1] == b[0] AND a[0] == b[1]? What if neither is the case? –  Karl Knechtel Dec 29 '10 at 13:12
add comment

6 Answers

up vote 2 down vote accepted

I'm not sure your comparison function is a valid one in a mathematical sense, i.e. transitive. Given a, b, c a comparison function saying that a > b and b > c implies that a > c. Sorting procedures rely on this property.

Not to mention that by your rules, for a = [1, 2] and b = [2, 1] you have both a[1] == b[0] and a[0] == b[1] which means that a is both greater and smaller than b.

share|improve this answer
Sorry, I've not explained it very well. In my data set, not exists the case (1,2) and (2,1) at the same time. Really the numbers are state id's, and the tuple is a transition representation, i.e. (2,3) means, state(2).next() == 3. –  Antonio Beamud Dec 29 '10 at 12:53
@Antonio: still, without "normal" behavior from the comparison function (such as transitivity) you cannot expect the sort to work properly –  Eli Bendersky Dec 29 '10 at 12:59
You're right. I'm reviewing all the problem. A lot of thanks. –  Antonio Beamud Dec 29 '10 at 13:01
add comment

Sounds a lot to me you are trying to solve one of the Google's Python class problems, which is to sort a list of tuples in increasing order based on their last element.

This how I did it:

def sort_last(tuples):

  def last_value_tuple(t):
    return t[-1]

  return sorted(tuples, key=last_value_tuple)

EDIT: I didn't read the whole thing, and I assumed it was based on the last element of the tuple. Well, still I'm going to leave it here because it can be useful to anyone.

share|improve this answer
add comment

You can write your own custom key function to specify the key value for sorting.


def sort_last(tuples):

    return sorted(tuples, key=last)

def last(a):
    return a[-1]

tuples => sorted tuple by last element

  • [(1, 3), (3, 2), (2, 1)] => [(2, 1), (3, 2), (1, 3)]
  • [(1, 7), (1, 3), (3, 4, 5), (2, 2)] => [(2, 2), (1, 3), (3, 4, 5), (1, 7)]
share|improve this answer
add comment

You could also write your code using lambda

def sort(tuples):
  return sorted (tuples,key=lambda last : last[-1])

so sort([(1, 3), (3, 2), (2, 1)]) would yield [(2, 1), (3, 2), (1, 3)]

share|improve this answer
add comment

Your ordering specification is wrong because it is not transitive.

Transitivity means that if a < b and b < c, then a < c. However, in your case:

(1,2) < (2,3)
(2,3) < (3,1)
(3,1) < (1,2)
share|improve this answer
well, really (1,2) < (2,3), and yes, the problem is about graphs, and this a cycle. Really in my dataset doesn't exists cycles. Anyway, you are right :) –  Antonio Beamud Dec 29 '10 at 12:57
@Antonio Beamud Oh, I switched < and > from your example. Corrected. However, comparison functions must be transitive, because that allows the sorting routine to take shortcuts (like compare a,b and b,c and never a,c). The cycle is just used for proving that your comparison function is wrong. –  phihag Dec 29 '10 at 13:03
add comment

Try lt.sort(tcmp, reverse=True).

(While this may produce the right answer, there may be other problems with your comparison method)

share|improve this answer
add comment

Your Answer


