當字符串相當於旋轉

我有大量的字符串。就我的目的而言，如果一個是另一個的旋轉（例如'1234'等同於'3412'），則兩個字符串是等價的。當字符串相當於旋轉

什麼是在Python中精確處理每個字符串（一直到旋轉）的有效方法？

一個天真的實現什麼，我想可能是這樣的：

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

來源

2013-03-03 math4tots

選擇一個標準的方式來代表一類旋轉的字符串（如字符串的所有可能的旋轉中字典序最小旋轉），和工作只與規範表示（規範化）。

例如：

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)

來源

2013-03-03 05:31:08 nneonneo

這是每個字符串的O（n²），實際上可以更快地計算它，請參閱維基百科「字典順序最小字符串旋轉」 – 2013-03-03 14:37:12

@FalkHüffner，必須有一些東西！ – Akavall 2013-03-03 17:02:34

只需將鏈接添加到FalkHüffner建議的帖子中：http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation – 2013-04-01 02:36:10

也許是有道理的旋轉你的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'])

來源

2013-03-03 04:36:53 Akavall

您可以將此代碼*很多*簡單。看我的解決方案。否則，它是好的。 – nneonneo 2013-03-03 05:34:32

當字符串相當於旋轉

回答

相關問題