规范化表示（组合）项链的字符串

Question

我试图通过查找符号的线性表示来匹配Python中的"necklaces"，为此我使用普通字符串。例如，字符串"AABC"、"ABCA"、"BCAA"、"CAAB"都代表同一条项链（如图）。在

为了得到一个概述，我只存储一个给定项链的等价字符串的一个作为“代表”。为了检查我是否存储了候选的项链，我需要一个函数来规范化任何给定的字符串表示。作为一种伪代码，我用Python编写了一个函数：

import collections

def normalized(s):
    q = collections.deque(s)
    l = list()
    l.append(''.join(q))
    for i in range(len(s)-1):
        q.rotate(1)
        l.append(''.join(q))
    l.sort()
    return l[0]

对于上面示例项链中的所有字符串表示，此函数返回"AABC"，它按字母顺序排在第一位。在

我想知道，如果我已经在Python中实现了一个新的Python应用程序，我会想“如果我已经在Python中实现了一个新的函数，我会不会已经足够好了？换句话说：一个有经验的Python程序员会使用这个函数吗，还是有明显的缺陷？在

Answer 1

这样的怎么样：

patterns = ['abc', 'bca', 'cab']
normalized = lambda p: ''.join(sorted(p))
normalized_patterns = set(normalized(p) for p in patterns)

输出示例：

^{pr2}$

Answer 2

您可以使用min而不是排序：

def normalized2(s):
    return min(( s[i:] + s[:i] for i in range(len(s)) ))

但它仍然需要复制字符串len(s)次。更快的方法是过滤最小字符的起始索引，直到只得到一个。有效搜索最小循环：

^{pr2}$

对于长字符串，这要快得多：

In [143]: loop = [ random.choice("abcd") for i in range(100) ]
In [144]: timeit normalized(loop)
1000 loops, best of 3: 237 µs per loop
In [145]: timeit normalized2(loop)
10000 loops, best of 3: 91.3 µs per loop
In [146]: timeit normalized3(loop)
100000 loops, best of 3: 16.9 µs per loop

但如果我们有很多重复的话，这种方法是不够的：

In [147]: loop = "abcd" * 25
In [148]: timeit normalized(loop)
1000 loops, best of 3: 245 µs per loop
In [149]: timeit normalized2(loop)
100000 loops, best of 3: 18.8 µs per loop
In [150]: timeit normalized3(loop)
1000 loops, best of 3: 612 µs per loop

我们也可以向前扫描字符串，但我怀疑它是否会更快，没有一些花哨的算法。在

Answer 3

如果我理解正确，你首先需要构造输入序列的所有循环置换，然后确定（按字典顺序）最小的元素。这是符号循环的根。 试试这个：

def normalized(s):
    L = [s[i:] + s[:i] for i in range(len(s))]
    return sorted(L)[0]

这段代码只处理字符串，而不像代码中那样在队列和字符串之间进行转换。快速计时测试显示此代码在30-50%的时间内运行。 知道应用程序中s的长度是很有趣的。由于所有排列都必须临时存储len（s），临时列表L需要^2个字节。希望这不是你的限制。在

编辑： 今天我无意中发现，如果你把原来的字符串连在一起，它将包含所有的旋转作为子串。所以代码是：

^{pr2}$

这确实会运行得更快，因为只有一个合并加上n个滑动。在我的机器上，使用10到10**5的stringlength，运行时间在55%到66%之间，而带有生成器的min（）版本则是这样。在

请注意，您在内存消耗（2倍）上牺牲了速度，这在这里并不重要，但在不同的设置下可能会这样做。在