假設我有一個如下所示的無向回圈序列：
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 中檢查兩個串列是否回圈相同
比較周期性資料的快速方法
uj5u.com熱心網友回復：
您可以使用元組作為可散列的識別符號，并從序列的可能旋轉中選擇最小的一個：
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/329069.html
下一篇：計算精彩子串的數量