置换和排列的区别？

一、置换

一个有限集合S到自身的双射（即一一对应）称为S的一个置换。集合上的置换可以表示为

意为将映射为，其中是1,2，…，n的一个排列。显然S上所有置换的数量为n!。

乘法

对于两个置换和 ，f 和 g 的乘积记为，其值为

简单来说就是先后经过 f 的映射，再经过 g 的映射。

二、排列

设是前 n 个正整数构成的集合，是I的一个置换。记：

于是仍然为1,2，…，n这 n 个数，只是顺序有所不同。

由1,2，…，n组成的一个有序组，称为1,2，…，n的一个排列。例如把前文叫做1,2，…，n的一个排列。

前 n 个正整数1,2，…，n的不同排列共有 n! 个。

（1）逆序和逆序数

在一个排列中，如果某一个较大的数排在某一个较小的数前面，就说这两个数构成一个反序或逆序。

在一个排列里出现的反序的总个数，叫做这个排列的反序数或逆序数。

一个排列的反序数可能是偶数也可能是奇数。有偶数个反序的排列叫做一个偶排列，有奇数个反序的排列叫做一个奇排列。

（2）对换

如果把1,2，…，n的排列中，任意两个数 i 和 j 交换，其余数保持不动，就得到一个新排列。对于排列施加这样一个变换叫做一个对换，用 (i,j) 表示。

定理：设和是 n 个数码的任意两个排列，那么总可以通过一系列对换，由 得出。

定理：每一个对换都改变排列的奇偶性。

定理：当 n 至少为 2 时，n 个数码的奇排列与偶排列个数相等，各为个。

（3）逆序数的计算方法

逆序数的编程计算方法，可以使用归并排序，时间复杂度为。