5

我有大量的字符串。出于我的目的，如果一个字符串是另一个字符串的旋转，则两个字符串是等效的（例如，'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
4

2 回答 2

6

选择一种规范的方式来表示一类旋转的字符串（例如，在字符串的所有可能旋转中按字典顺序最小的旋转），并且只使用规范表示（规范化）。

例如：

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-03T05:31:08.243 回答
3

也许将您旋转到特定值是有意义的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-03T04:36:53.857 回答