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

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

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)

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

Create unique identifier for undirected circular sequences

python

algorithm

sorting

sequence

circular-list