当字符串相当于旋转

我有大量的字符串。就我的目的而言，如果一个是另一个的旋转（例如'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

当字符串相当于旋转

回答

相关问题