CODEWITHSUNDEEP
python
Nathaniel Ford
Nathaniel Ford

Reputation: 21239

Implementation of __lt__ to sort list

I don't understand why my __lt__ implementation seems to be failing.

This is my class:

import random, string, datetime
from functools import total_ordering


@total_ordering
class Rotation(object):
    """Describes a rotation of an input based on getting the original and then offsetting it."""

    def __init__(self, original, idx):
        self.original = original
        self.idx = idx

    def getOffset(self, offset):
        return self.original[(self.idx + offset) % len(self.original)]

    def __eq__(self, other):
        print("checking equality")
        if self.idx == other.idx:
            return True
        for offset in range(len(self.original)):
            if self.getOffset(offset) is not other.getOffset(offset):
                print("this={} is not that={}".format(self.getOffset(offset), other.getOffset(
                        offset)))
                return False
        return True

    def __lt__(self, other):
        for offset in range(len(self.original)):
            if self.getOffset(offset) < other.getOffset(offset):
                # print("this={} is less than that={}".format(self.getOffset(offset), other.getOffset(
                #         offset)))
                return True
        print("Not less than")
        return False

    def __str__(self):
        return self.getOffset(-1)

    def __repr__(self):
        return "".join(map(lambda x: str(x), [self.getOffset(idx) for idx in range(len(
                self.original))]))

def rotation_sort(input):
    original = list(input)
    rotations = [Rotation(original, idx) for idx in range(len(original))]
    result = sorted(rotations)
    print("original={} rotations={} result={}".format(original, rotations, result))
    return "".join(map(lambda x: str(x), result))

def test(input):
    start = datetime.datetime.now()
    result = rotation_sort(input)
    end = datetime.datetime.now()
    runtime = end - start
    print("input={} runtime={} head={} tail={}".format(input[:5], runtime.seconds, result[:5],
                                                       result[-5:]))

test('bacb')

Running this script I get the following output:

$ python2 strange_sort.py
original=['b', 'a', 'c', 'b'] rotations=[bacb, acbb, cbba, bbac] result=[bbac, cbba, acbb, bacb]
input=bacb runtime=0 head=cabb tail=cabb

I do not understand why the result is not properly sorted. I would have expected result=[acbb, bacb, bbac, cbba]?

For context: the idea is to try and find a faster way to 'sort' all the rotations of a string than finding all the permutations and sorting them individually. (That idea will work on strings of length of hundreds or thousands but not hundreds of thousands.) To prove the sorting the __str__ pulls the last character in the string. To implement the sorting, each 'rotation' (which knows where in the original it starts) compares increasing offsets from it's own start with the offset of the other rotation's start:

original string: bacb
all rotations:
    index 0: bacb 
    index 1: acbb 
    index 2: cbba 
    index 3: bbac
sorted rotations:
    index 1: acbb
    index 0: bacb
    index 3: bbac
    index 4: cbba
final representation of sorted rotations (last character of each): 
    bbca

Upvotes: 0

Views: 407

Answers (1)

niemmi
niemmi

Reputation: 17263

The problem is that you're only returning from the loop in __lt__ if self.getOffset(offset) < other.getOffset(offset) but continue looping if self.getOffset(offset) > other.getOffset(offset). This can be fixed easily:

def __lt__(self, other):
    for offset in range(len(self.original)):
        if self.getOffset(offset) < other.getOffset(offset):
            return True
        elif self.getOffset(offset) > other.getOffset(offset):
            return False
    return False

Upvotes: 4

Related Questions