如何计算元素相同但顺序不同的向量的序列相似度？

给定两个包含完全相同元素、仅排列顺序不同的序列：

a = [25,26,37,36,27,33,104,44,40,49,45,48,50,55,56,59,54,57,105,64,73,76,72,67,68,71,78,82,77,79,86,84,83,85,91,92,96,97,102,101,93,98,99,100,94,95,88,87,65,66,90,89,80,81,75,74,69,70,62,63,61,60,58,53,52,46,51,47,41,43,42,39,38,35,34,13,14,4,5,9,8,12,3,1,2,6,7,10,11,15,21,22,29,32,31,30,28,23,103,20,24,19,16,17,18]
b = [1,2,6,7,10,11,15,103,21,22,29,30,31,32,33,28,23,20,12,19,24,27,16,17,18,25,26,36,37,42,41,43,46,52,53,58,57,54,51,47,44,104,40,49,45,48,50,55,56,59,105,62,63,70,69,74,75,81,73,76,80,86,79,77,72,64,67,68,71,78,82,83,84,85,91,92,96,97,101,102,93,89,90,98,99,100,95,94,88,87,66,65,61,60,39,38,35,34,14,13,4,5,9,8,3]

需要基于相邻元素的匹配情况计算整体序列相似度，例如a中片段39,38,35,34,13,14,4,5,9,8与b中对应位置片段39,38,35,34,14,13,4,5,9,8仅13和14顺序颠倒，该片段相似度视为80%。

方法1：位置对应的邻接对匹配（贴合示例逻辑） #

完全匹配你给出的片段相似度计算思路，针对两个序列同一位置的相邻元素对做比对：

1. 遍历序列的每个位置i（范围是0到n-2，n为序列总长度），分别提取a的邻接对(a[i], a[i+1])和b的邻接对(b[i], b[i+1])。
2. 统计两个邻接对完全相等的次数，记为match_count。
3. 整体相似度计算公式：

   相似度 = (match_count / (n - 1)) × 100%
   

   对应你给出的片段示例：10个元素对应9个邻接对，其中7个邻接对完全匹配，7/9≈77.8%，取整后即为80%，和示例预期一致。

方法2：邻接对集合匹配（反映序列结构相似性） #

如果不限制位置，只关注元素间的相邻关系是否一致（比如某段序列在另一个序列中平移但内部结构不变），可以用这种方法：

1. 分别为a和b生成所有邻接对的多集合（保留重复出现的邻接对），比如a的邻接对集合pairs_a，b的为pairs_b。
2. 计算两个多集合的交集大小：对每个重复的邻接对，取两个集合中出现次数较小的值，累加得到总匹配数common_count。
3. 整体相似度计算公式：

   相似度 = (common_count / (n - 1)) × 100%
   

   这种方法更适合衡量序列的"结构相似性"，不会因为片段位置偏移而忽略匹配的相邻关系。

方法3：加权局部片段相似度（关注局部连续匹配） #

如果需要更精细地评估局部连续片段的相似性，可以将序列拆分后加权计算：

1. 设定片段长度k（比如示例中的10），将两个序列按顺序划分为若干长度为k的片段（最后一个片段长度不足k时单独处理）。
2. 对每个对应位置的片段，用方法1计算局部相似度。
3. 将所有局部相似度取平均（或按需求给不同片段设置权重），得到整体相似度。

内容的提问来源于stack exchange，提问作者purecobalt