如何评估已打乱序列的随机性及识别相似打乱模式？

针对判断序列是否为随机打乱及量化随机程度，可采用以下方法：

• 卡方频率检验：统计每个数值在序列各个位置的出现次数，与均匀分布的期望次数对比，通过scipy.stats.chi2_contingency计算卡方统计量和p值。若p值大于显著性水平（如0.05），则无法拒绝序列是随机的假设；卡方值越小，随机程度越高。
• 游程检验：统计序列中上升/下降游程的数量（游程指连续递增或递减的子序列）。随机序列的游程数服从正态分布，用scipy.stats.runs_1samp做Z检验，判断游程数是否符合随机序列的特征。游程数偏离期望越远，随机性越差。
• 逆序数检验：计算序列中逆序对的数量（即i<j但序列[i]>序列[j]的对数）。随机排列的逆序数期望为n(n-1)/4（n为序列长度），方差为n(n-1)(2n+5)/72。通过Z检验判断实际逆序数是否偏离期望，偏离越小则随机程度越高。可通过numpy结合向量化操作快速计算逆序数。
• 置换熵：量化序列的无序程度，熵值越接近log2(n!)（n为序列长度），随机性越强。可使用pyentrp库的permutation_entropy函数计算。

要找出采用相似打乱方式的序列，可从置换特征和距离度量入手：

• 置换特征提取与聚类：
  • 提取置换的核心特征：逆序数、循环分解结构（将置换分解为循环，如[3,2,1,4,5]可分解为(1→3→1)、(2)、(4)、(5)）、元素位置偏移量（每个元素与原有序列中位置的差值）。
  • 基于特征向量使用聚类算法分组，比如scikit-learn的KMeans或层次聚类，特征相似的序列会被归为同一类，代表相似的打乱方式。
• 置换距离度量：
  • 肯德尔tau距离：反映两个置换的逆序差异，通过scipy.stats.kendalltau计算相关系数，系数越接近1说明两个置换的排序趋势越相似，打乱方式可能一致。
  • 凯莱距离：将一个置换转换为另一个所需的最小相邻交换次数，距离越小说明打乱方式越接近。可通过置换的循环分解计算：凯莱距离 = n - 循环数量（n为序列长度）。
  • 汉明距离：统计两个序列对应位置元素不同的数量，适合识别简单移位、反转类的相似打乱。

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