如何为无向环形序列生成统一的唯一标识符？

解决方案 #

核心思路 #

要实现无向环形序列的唯一标识，核心是给等价的序列生成统一的规范表示，无向环形序列的等价条件包含两类：

• 旋转等价：同一条环从任意位置开始遍历得到的序列等价
• 反转等价：无向环正向/反向遍历得到的序列等价

我们可以通过两次最小表示法计算，取最小的结果作为唯一标识符：

1. 计算原序列所有旋转结果中的字典序最小序列（正序最小表示）
2. 计算反转后序列所有旋转结果中的字典序最小序列（逆序最小表示）
3. 取上述两个结果中字典序更小的，格式化为字符串即为唯一标识符

这里我们采用时间复杂度为O(n)的最小表示法算法，效率远高于暴力枚举所有旋转的方案，完全满足数千条序列的处理需求。

Python实现代码 #

首先实现O(n)的最小旋转表示计算函数：

def minimal_rotation(seq):
    """计算序列的最小旋转表示，时间复杂度O(n)"""
    n = len(seq)
    s = seq * 2  # 拼接两份序列避免循环取模运算
    i = 0
    ans = 0
    while i < n:
        ans = i
        j = i + 1
        k = i
        while j < 2 * n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            i += j - k
    return s[ans:ans + n]

再实现标识符生成函数：

def get_circle_identifier(seq):
    # 计算正序所有旋转的最小表示
    min_forward = minimal_rotation(seq)
    # 计算反转后序列所有旋转的最小表示
    min_backward = minimal_rotation(seq[::-1])
    # 取两者中字典序更小的作为统一规范表示
    canonical = min(min_forward, min_backward)
    return ','.join(map(str, canonical))

测试验证 #

使用你给出的三个序列测试：

seq1 = [1,1,3,3,2,3,2,1,3,2] # 从左上角逆时针遍历
seq2 = [3,2,3,3,1,1,2,3,1,2] # 从右下角顺时针遍历
seq3 = [3,1,2,3,2,3,3,1,1,2] # 从右上角顺时针遍历

print(get_circle_identifier(seq1))
print(get_circle_identifier(seq2))
print(get_circle_identifier(seq3))

三个序列输出完全一致：

1,1,2,3,1,2,3,2,3,3
1,1,2,3,1,2,3,2,3,3
1,1,2,3,1,2,3,2,3,3

原代码问题说明 #

你最初的算法以边权重和作为选择标准是错误的，不同的旋转/反转序列可能出现权重和相同但序列本身不同的情况，导致最终选出来的规范序列不一致。直接使用字典序作为选择标准，逻辑更简单，也不会出现歧义。

内容的提问来源于stack exchange，提问作者Shaun Han