逻辑信息系统排序的实现

Question

我不明白为什么我的__lt__实现似乎失败了。在

这是我的课：

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

运行此脚本时，我得到以下输出：

^{pr2}$

我不明白为什么result没有正确排序。我会料到result=[acbb, bacb, bbac, cbba]？在

上下文：这个想法是尝试找到一种更快的方法来“排序”一个字符串的所有旋转，而不是找到所有的排列和单独排序。（这个想法将适用于长度为数百或数千但不是几十万的字符串）为了证明排序__str__提取字符串中的最后一个字符。为了实现排序，每个“旋转”（它知道它在原始位置的起始位置）将从其自身开始的增加偏移量与另一个旋转的起点偏移量进行比较：

^{3}$

Answer 1

问题是您只从__lt__if self.getOffset(offset) < other.getOffset(offset)中的循环返回，而如果self.getOffset(offset) > other.getOffset(offset)，则继续循环。这很容易修复：

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