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

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代码)，可以为这种序列创建一个唯一的标识符?

下面是一些相关的问题，但并不是我想要达到的目的:

如何在Python

中检查两个列表是否循环相同快速比较周期数据的方法

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)