11

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)]

Rules:
* 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
    else:
       return 0

but sorting the list: 

lt.sort(tcmp)

lt show me: 

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

What am I doing wrong?

Improve this question
2
  • I see nothing wrong, except that given your input and comparison function, your initial list is already sorted. Commented Dec 29, 2010 at 12:38
  • ... And what if a[1] == b[0] AND a[0] == b[1]? What if neither is the case? Commented Dec 29, 2010 at 13:12

6 Answers 6

Reset to default
15

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

7

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)]

Improve this answer

Comments

4

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

Ex.

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)]
Improve this answer

Comments

2

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.

Improve this answer

3 Comments

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: still, without "normal" behavior from the comparison function (such as transitivity) you cannot expect the sort to work properly
You're right. I'm reviewing all the problem. A lot of thanks.
0

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)
Improve this answer

2 Comments

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 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.
-1

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

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.