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

Question

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

为了获得概览，我只存储一条给定项链的等效串作为 "representative"。至于检查我是否存储了候选项链，我需要一个函数来规范化任何给定的字符串表示。作为一种伪代码，我在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]

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

由于我对 Python 比较陌生，我想知道 - 如果我开始在 Python 中实现一个应用程序 - 这个函数是否已经 "good enough" 用于生产代码？换句话说：有经验的 Python 程序员会使用这个功能，还是有明显的缺陷？

Answer 1

这样的事情怎么样：

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

示例输出：

In [1]: normalized = lambda p: ''.join(sorted(p))

In [2]: normalized('abba')
Out[2]: 'aabb'

In [3]: normalized('CBAE')
Out[3]: 'ABCE'

Answer 2

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

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

此代码仅适用于字符串，无法像您的代码那样在队列和字符串之间进行转换。快速计时测试显示此代码在 30-50% 的时间内达到运行。知道应用程序中 s 的长度会很有趣。由于必须临时存储所有排列，因此临时列表 L 需要 len(s)^2 个字节。希望这不是您的情况的限制。

编辑： 今天我偶然发现，如果将原始字符串连接到自身，它将包含所有旋转作为子字符串。所以代码将是：

def normalized4(s):
    ss = s + s      # contains all rotations of s as substrings
    n = len(s)
    return min((ss[i:i+n] for i in range(n)))

这确实会运行更快，因为只剩下一个连接加上 n 个切片。使用 10 到 10**5 的字符串长度，与使用生成器的 min() 版本相比，运行我的机器上的时间在 55% 到 66% 之间。

请注意，您以速度换取内存消耗 (2x)，这在这里无关紧要，但在不同的设置中可能会如此。

Answer 3

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

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

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

def normalized3(s):
    ssize=len(s)
    minchar= min(s)
    minindexes= [ i for i in range(ssize) if minchar == s[i] ]
    for offset in range(1,ssize):
        if len( minindexes ) == 1 :
            break
        minchar= min( s[(i+offset)%ssize] for i in minindexes )
        minindexes= [i for i in minindexes if minchar == s[(i+offset)%ssize]]
    return s[minindexes[0]:] + s[:minindexes[0]]

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

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

我们也可以向前扫描字符串，但我怀疑如果没有一些奇特的算法，它会更快。

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

Normalize strings that represent (combinatorical) necklaces

python

combinatorics

string-comparison

string-matching