Sorting without transitivity

[Frank Niessink]

Hi all,

[It's been while since I've dealt with transitivity and stuff, so
I hope I got the terminology right]

I have objects that are not transitivily ordered, e.g.:

A > B
A == C
B == C

Now I have a list [A, B, C] and I want to sort it.
The resulting list should have B before A, I don't care where
C is. However, the Python list.sort() method (Python 2.2.2 on cygwin)
doesn't put A and B in the right order.

How can I get the desired behavior? Should I implement my own
sort algorithm? Any pointers?

Thanks in advance, Frank

PS: Below follows a demonstration of my problem:


import unittest

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return 'Point(%d, %d)'%(self.x, self.y)

    def __cmp__(self, other):
        if self.x == other.x and self.y == other.y:
            return 0
        elif self.x <= other.x and self.y <= other.y:
            return -1
        elif self.x >= other.x and self.y >= other.y:
            return 1
        else:
            return 0


class PointTest(unittest.TestCase):
    def setUp(self):
        self.origin = Point(0, 0)

    def testOrigin(self):
        self.assertEqual(self.origin, self.origin)

    def testReallySmaller(self):
        oneOne = Point(1, 1)
        self.failUnless(self.origin < oneOne)

    def testOnlyXSmaller(self):
        oneZero = Point(1, 0)
        self.failUnless(self.origin < oneZero)

    def testOnlyYSmaller(self):
        zeroOne = Point(0, 1)
        self.failUnless(self.origin < zeroOne)

    def testNotSmallerNotBigger(self):
        a = Point(1, 2)
        b = Point(2, 1)
        self.assertEqual(a, b)


class SortTest(unittest.TestCase):

    def testSortPoints(self):
        """ This test fails """
        a = Point(0, 1) # a < b
        b = Point(0, 2) 
        c = Point(1, 0)
        pointList = [b, c, a]
        pointList.sort()
        self.failUnless(pointList.index(a) < pointList.index(b))


if __name__ == '__main__':
    unittest.main()


-- 
The moment became a longer moment, and suddenly it was a very long moment,
so long one could hardly tell where all the time was coming from.
	-- Douglas Adams, 'So long, and thanks for all the fish'