執行__lt__排序列表

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

運行此腳本我得到以下輸出：

$ 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 

我不明白爲什麼result不正確排序。我本來期待result=[acbb, bacb, bbac, cbba]？

對於上下文：這個想法是嘗試找到一種更快的方式來對所有字符串的旋轉進行「排序」，而不是找到所有排列並對它們進行單獨排序。 （這個想法可以用於長度爲數百或數千字符串但不是數十萬字符串的字符串。）爲了證明排序，__str__將拉取字符串中的最後一個字符。爲了實現排序，每個「旋轉」（它知道在原來它開始的地方）比較其他旋轉的開始的偏移量增加，從它自己開始偏移：

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 

Answer 1

的問題是，你只能是如果self.getOffset(offset) < other.getOffset(offset)爲__lt__，則從循環中返回，但如果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