文字列が回転に等しいとき

Question

私は多数の文字列を持っています。私の目的のために、2つの文字列は、一方が他方の回転であれば等価です（例えば、 '1234'は '3412'と等価です）。

Pythonで各文字列を正確に1回（回転まで）処理する効率的な方法は何ですか？

私が何をしたいの素朴な実装は次のようになります。

class DuplicateException(Exception): pass 
seen = set() 
for s in my_strings: 
    try: 
    s2 = s+s 
    for t in seen: 

     # Slick method I picked up here in SO 
     # for checking whether one string is 
     # a rotation of another 
     if len(s) == len(t) and t in s2: 
     raise DuplicateException() 

    seen.add(s) 
    process(s) 
    except DuplicateException: pass 

Answer 1

が回転文字列（文字列のすべての可能な回転の間で、例えば辞書式に最小回転）のクラスを表すために正規の方法を選んで、そして正規表現でのみ動作（正規化）。

例えば

：あなたはこのコードは*ロット*簡単にすることができます

def canonicalize(s): 
    return min(s[i:]+s[:i] for i in xrange(len(s))) 

canonical_strings = {canonicalize(s) for s in my_strings} 
for cs in canonical_strings: 
    process(cs) 

Answer 2

多分それはそれらの最小回転がユニークであり、可能性よりも、特定の値、例えば可能な最小の回転にごstringを回転させることが理にかなっていますセットに簡単に入れることができます。

これは実装例であり、「rotate_to_smallest」はおそらく改善される可能性があります。

my_strings = ['1234', '123', '2341', '4312', '312', '56', '65', '1236'] 

def rotate_to_smallest(x): 
    smallest = x 
    for i in xrange(1, len(x)): 
     rotation = x[i :] + x[: i] 
     if rotation < smallest: 
      smallest = rotation 
    return smallest 

def unique_rotations(my_strings): 
    uniques = set(()) 
    for s in my_strings: 
     smallest_rotation = rotate_to_smallest(s) 
     if smallest_rotation not in uniques: 
      uniques.add(smallest_rotation) 
    return uniques 

結果：

>>> unique_rotations(my_strings) 
set(['1234', '56', '1243', '123', '1236'])