リストをソートする__lt__の実装

Question

私の__lt__の実装が失敗しているように見えるのはなぜわかりません。

$ 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が適切にソートされていない理由を私は理解していない：私は次の出力を取得し、このスクリプトを実行

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

：

この

は私のクラスです。私は 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)の場合はself.getOffset(offset) > other.getOffset(offset)の場合はループし続けます。__lt__これは簡単に修正することができます：

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