假设我有一个看起来像这样的无向循环序列:
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 代码)来为这种序列创建唯一标识符?
以下是一些相关的问题,但不完全是我想要实现的目标: