为无向循环序列创建唯一标识符

Question

假设我有一个无向循环序列，如下所示：

  1 —— 2 —— 3
 /           \
1             1
|             |
3             2
 \           /
  3 —— 2 —— 3

假设我有如下3个序列，由数字列表表示：

seq1 = [1,1,3,3,2,3,2,1,3,2] # anticlockwise from top left
seq2 = [3,2,3,3,1,1,2,3,1,2] # clockwise from bottom right
seq3 = [3,1,2,3,2,3,3,1,1,2] # clockwise from top right

由于该序列是无方向的，因此所有3个序列基本相同，并表示上面的圆形序列。实际上，我有数千个这样的无向循环序列，所以不可能对每一对进行比较。因此，我想创建一个唯一的标识符，它可以表示每个唯一的无向循环序列。例如，上述3个序列的标识符应相同

我的想法是将这类序列视为圆形图。然后，我可以指定边权重作为两个连接节点之间的差值，并找到遍历所有节点的路径，同时最大化所有边权重之和。下面是我的Python实现：

def identifier(seq):
    delta_sum = float('-inf')
    res_seq = []
    for i in range(len(seq)):
        new_seq = seq[i:] + seq[:i]
        ds = sum([new_seq[j+1] - new_seq[j] for j in range(len(seq)-1)])
        if ds > delta_sum:
            delta_sum = ds
            res_seq = new_seq
        if -ds > delta_sum:
            delta_sum = -ds
            res_seq = new_seq[::-1]
    return ','.join(map(str, res_seq))

print(identifier(seq1))
print(identifier(seq2))
print(identifier(seq3))

输出：

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

显然我的算法不起作用。它为前两个序列创建相同的标识符，但为第三个序列创建不同的标识符。有人能推荐一种相对快速的算法（最好是Python代码）来为这种序列创建唯一的标识符吗

以下是一些相关的问题，但不是我想要实现的目标：

How to check whether two lists are circularly identical in Python

Fast way to compare cyclical data

Answer 1

您可以使用元组作为哈希标识符，并从序列的可能旋转中选择最小的元组：

def identifier(s):
    return min((*s[i::d],*s[:i:d]) for d in (1,-1) for i in range(len(s)))

输出：

seq1 = [1,1,3,3,2,3,2,1,3,2] # anticlockwise from top left
seq2 = [3,2,3,3,1,1,2,3,1,2] # clockwise from bottom right
seq3 = [3,1,2,3,2,3,3,1,1,2] # clockwise from top right

print(identifier(seq1))
print(identifier(seq2))
print(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)

假设最小元组将以最小值开始，您可以通过首先查找最小值并仅比较从最小值索引开始形成的元组来对此进行优化：

def identifier(seq):
    start  = min(seq)
    starts = [i for i,v in enumerate(seq) if v == start]
    return min((*seq[i::d],*seq[:i:d]) for d in (1,-1) for i in starts)