如何计算一个序列是递增序列的偶数排列还是奇数排列？

计算科学 matlab 组合学
2021-12-22 01:15:14

该问题的变体已交叉发布到Stack Overflow和数学 Stack Exchange。可以在这些其他站点上找到其他答案。

计算科学人：

我最初在https://math.stackexchange.com/questions/379809/is-there-a-name-for-this-function-parity-of-a-finite-sequence提出了这个问题。标题基本概括了所有内容。给定一个我知道是不同的实数的有限序列，我想要一种简单的方法来计算它是递增序列的偶数排列还是递增序列的奇数排列。例如，(5,1.3,8,6,10.5)是递增序列的偶排列(1.3,5,6,8,10)，所以答案是“偶数”。 (2,3,5,1)是递增序列的奇排列(1,2,3,5)，所以答案是“奇数”。我可以让 Matlab 给我一个排列向量，对于我的第一个例子来说是[2 1 4 3 5]，但我在 Matlab 中找不到一个内置函数来计算该置换向量的符号。如果我能让 Matlab 给我 permutation matrix，我可以取那个矩阵的行列式。人们已经在网上发布了很长的 Matlab 文件来实现这一点，但我希望我可以避免这种情况。我也愿意使用 Maple。

请不要吹毛求疵或不具建设性的评论，这在 Math Stack Exchange 上很常见。我在这里的经验较少，但我希望这里的人们更有礼貌。

Stefan（堆栈交换风扇）

1个回答

假设你有一个置换向量permVec。然后应该按如下方式计算置换矩阵（以一些 MATLAB 语法错误为模，因为已经有一段时间了）：

permMat = function permVecToMat(permVec)
    n = length(permVec);
    permMat = zeros(n,n);
    for i = 1:n
        permMat(i, permVec(i)) = 1
    end
end

然后你只取行列式，你就完成了。考虑代码 BSD 许可，即使 Stack Exchange 许可证是 CC-BY-SA 3.0（我讨厌它）。

计算置换符号的另一种方法是将其转换为转置的乘积。如果这种分解中的转置数是偶数，则排列是偶数；否则，排列是奇数。但是，我不知道将排列分解为转置乘积的算法。

其它你可能感兴趣的问题
上一篇在 CFD 的背景下，什么是“唤醒”？ 下一篇解决“广义”线性规划问题