能否在线性或亚二次时间内计算置换的符号？

我想了解是否存在在线性（或至少优于n²的亚二次）时间内计算置换符号的方法。例如，当我对含n个元素的数组进行元素交换时，置换符号会翻转。我目前有一个时间复杂度为O(n²)的计算函数，但似乎存在更高效的算法。以下是我实现的二次时间计算的最小可复现代码：

import numpy as np

vals = np.arange(1,6,1)
pvals = np.arange(1,6,1)
pvals[0], pvals[1] = pvals[1], pvals[0] # 交换元素

def quadratic(vals):
  sgn_matrix = np.sign(np.expand_dims(vals, -1) - np.expand_dims(vals, -2))
  return np.prod(np.tril(np.ones_like(sgn_matrix)) + np.triu(sgn_matrix, 1))

def sub_quadratic(vals):
    # 线性时间计算置换符号：基于循环分解
    perm = np.array(vals) - 1  # 转换为0-based的置换数组
    n = len(perm)
    visited = [False] * n
    cycle_count = 0
    
    for i in range(n):
        if not visited[i]:
            cycle_count += 1
            j = i
            while not visited[j]:
                visited[j] = True
                j = perm[j]  # 沿着置换遍历整个循环
    
    # 置换符号 = (-1) ^ (n - 循环个数)
    return (-1) ** (n - cycle_count)

# 测试二次时间函数
sgn = quadratic(vals)
print(sgn)   # 输出 +1 

psgn = quadratic(pvals)
print(psgn)  # 输出 -1 

# 测试线性时间函数
sgn_sub = sub_quadratic(vals)
print(sgn_sub)   # 输出 1

psgn_sub = sub_quadratic(pvals)
print(psgn_sub)  # 输出 -1

我查阅过相关资料，发现有人提到循环置换可实现线性时间计算，但我对此完全不了解，也未找到足够相关内容。

TL;DR 请问是否存在亚二次时间计算置换符号的方法？

解答 #

存在线性时间（O(n)）的算法计算置换符号，核心思路是通过置换的循环分解推导：

1. 核心原理：

   • 任何置换都可分解为若干不相交的循环的乘积。
   • 长度为k的循环可拆分为(k-1)个两两交换（对换），每个对换会翻转置换符号。
   • 总对换数等于所有循环的(k-1)之和，即 总对换数 = n - 循环个数（n为元素总数）。
   • 置换符号为 (-1) ^ 总对换数，也就是 (-1) ^ (n - 循环个数)。

2. 算法步骤：

   • 用布尔数组标记每个元素是否已访问。
   • 遍历每个元素：若未被访问，沿置换映射遍历整个循环，标记循环内所有元素为已访问，同时统计循环数量。
   • 根据公式计算置换符号。

3. 代码说明：

   • 将数组元素转换为0-based索引（减1），让数组直接表示从{0,1,...,n-1}到自身的置换。
   • 从每个未访问的索引出发，沿perm[j]（置换后的索引）遍历，直到回到起点，完成一个循环的统计。
   • 最终通过(-1) ** (n - cycle_count)计算符号，结果与O(n²)方法完全一致，但时间复杂度降至O(n)。

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