排列

排列又称置换，是将相异物件或符号根据确定的顺序重排，得到的每个顺序都称作一个排列。例如，从1到6的数字有720种排列，对应于由这些数字组成的所有不重复亦不阙漏的序列，例如“4, 5, 6, 1, 2, 3”与“1, 3, 5, 2, 4, 6”。

排列的广义概念在不同语境下有不同的形式定义：

- 在集合论中，一个集合的排列是从该集合映至自身的双射；在有限集的情况，便与上述定义一致。
- 在组合数学中，排列一词的传统意义是一个有序序列，其中元素不重复，但可能有阙漏。例如“1, 2, 4, 3”可以称为“1, 2, 3, 4, 5, 6”的一个排列，但是其中不含“5, 6”。此时通常会标明为“从n个对象取r个对象的排列”。无序序列的情形则为组合。

## 定义

一个集合的置换为从该集合映至自身的双射函数：

$$\sigma : S\ \stackrel{\sim}{\longrightarrow}\ S.$$

恒等置换的定义为置换$\sigma$使得对所有$x \in X$，$\sigma(x) = x$。

所有关于$n$个元素的集合$S$的置换组成的集合构成对称群$S_n$，其群运算为函数的复合。因此两个置换，$\sigma$和$\tau$的积$\pi = \sigma\tau$的定义为$\pi(i) = \sigma(\rho(i))$。

两个置换的复合一般不满足交换律：$\tau\sigma \neq \sigma\tau$。

## 置换数的计算

此节使用置换的传统定义。从$n$个相异元素中取出$k$个元素，$k$个元素的排列数量为：

$$P_k^n = \frac{n!}{(n-k)!}$$

以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为：

$$P_3^8 =\frac{8!}{(8-3)!}=336$$

因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：

$$P = \frac{1}{336}= 0.00298$$

不过，中国大陆的教科书则是把从n取k的情况记作$P^k_n$或$A^k_n$（A代表Arrangement，即排列）。

## 重复置换

上面的例子是建立在取出元素不重复出现状况。

从$n$个元素中取出$k$个元素，$k$个元素可以重复出现，这排列数量为：

$U_k^n = n^k$

以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为：

$$U_4^{10}=10^4=10000$$

这时的一次性添入中奖的概率就应该是：

$$P=\frac{1}{10000}=0.0001$$

## 抽象代数

在集合论与抽象代数等领域中，“置换”一词被保留为集合（通常是有限集）到自身的双射的一个称呼。例如对于从一到十的数字构成的集合，其置换将是从集合 $\{ 1, \ldots, 10 \}$ 到自身的双射。因此，置换是拥有相同定义域与上域的函数，且其为双射的。一个集合上的置换在函数合成运算下构成一个群，称为对称群或置换群。

## 符号

以下仅考虑有限集上的置换（视为双射），由于 $n$ 个元素的有限集可以一一对应到集合 $\{ 1, \ldots, n\}$，有限集的置换可以化约到形如 $\{ 1, \ldots, n\}$ 的集合之置换。此时有两种表示法。

第一，利用矩阵符号将自然排序写在第一列，而将置换后的排序写在第二列。例如：

$$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{bmatrix}$$

表示集合 {1,2,3,4,5} 上的置换 $s: s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1$。

第二，借由置换的相继作用描述，这被称为“轮换分解”。分解方式如下：固定置换 $s$。对任一元素 $x$，由于集合有限而 $s$ 是双射，必存在正整数 $N$ 使得 $s^N(x)=x$，故可将置换 $s$ 对 $x$ 的相继作用表成 $(x \; s(x) \; s^2(x) \cdots s^{m-1} (x))$，其中 $m$ 是满足 $s^{m}(x) = x$ 的最小正整数。

称上述表法为 $x$ 在 $s$ 下的轮换， $m$ 称为轮换的长度。此处将轮换视作环状排列，例如

$(a_1 \; a_2 \; a_3 \cdots a_m)$ 与

$$(a_m \; a_1 \; a_2 \cdots a_{m-1})$$

是同一个轮换。由此可知 $x$ 在 $s$ 下的轮换只决定于 $x$ 在 $s$ 作用下的轨道，于是，任两个元素 $x, y$ 或给出同一个轮换，或给出不交的轮换。

将轮换 $(x_1 \; \cdots x_m)$ 理解为一类特殊的置换，即可递置换：仅须定义置换 $s$ 为 $s: x_1 \mapsto x_2, \ldots, x_{m-1} \mapsto x_m, x_m \mapsto x_1$，而在其它元素上定义为恒等映射。不交的轮换在函数合成的意义下可相交换。

因此，可以将集合 {1, ..., n} 对一置换分解成不交轮换的合成，此分解若不计顺序则是唯一的。例如前一个例子的 $s$ 就对应到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。

## 轮换

轮换一是种特殊的置换。

如果给定$f:X\rightarrow X$是$X$上的一个置换，$A$为$X$上的一个子集。

若有

$$\exists A\subset X,A=\{x_1,x_2,\cdots,x_l\}$$

$$\begin{cases} f(x_1)=x_2,f(x_2)=x_3,\cdots,f(x_l)=x_1 \\ f(x)=x,x\not\in A \end{cases}$$

则称$f$ 为一个轮换。$l$ 为轮换的长度。

## 特殊置换

在上节的置换表法中，长度等于二的环状置换称为换位，这种环状置换 $(x \; y)$ 不外是将元素 $x, y$ 交换，并保持其它元素不变。对称群可以由换位生成。

由于环状置换长度为$l$的置换$C$可分解为最少$k=l-1$个换位，若$k$为偶数，则$C$为偶换位，否则$C$为奇换位。即环状置换的长度为奇数，该置换为偶换位；环状置换的长度为偶数，该置换为奇换位。

由此可定义任一置换的奇偶性，并可证明：一个置换是偶换位的充要条件是它可以由偶数个换位生成。偶换位在置换群中构成一个正规子群，称为交错群。

## 计算理论中的置换

某些旧课本将置换视为变数值的赋值。在计算机科学中，这就是将值1, 2, ..., $n$赋予变数$x_1$, $x_2$, ..., $x_n$的赋值运算子，并要求每个值只能赋予一个变数。

赋值/代入的差别表明函数式编程与指令式编程之差异。纯粹的函数式编程并不提供赋值机制。现今数学的惯例是将置换看作函数，其间运算看作函数合成，函数式编程也类似。就赋值语言的观点，一个代入是将给定的值“同时”重排，这是个有名的问题。

## 置换图

<image>

取一个无向图$G$，将图$G$的$n$个顶点标记为$v_1$, ..., $v_n$，对应一个置换（$s(1) \; s(2) \; \cdots \; s(n)$），当且仅当$s(i) < s(j)$而$i > j$，则图的$v_i$和$v_j$相连，这样的图称为置换图。

置换图的补图必是置换图。

## 使用计算器

多数计算器都有个计算置换数的 nPr 键。然而此键在一些最先进的桌上型机种中却被隐藏了。例如：在 TI-83 中，按 MATH、三次右键、再按二。在卡西欧的图形计算机中，按 OPTN，一次右键（F6）、PROB（F3）、nPr（F2）。

## 试算表语法

多数试算表软件都有函式 PERMUT(Number，Number chosen)，用以计算置换。Number 是描述物件数量的一个整数，Number chosen 是描述每个置换中所取物件数的整数。

## C++演算范例

### 循环法

```cpp
#include <iostream>
using namespace std;
bool arrsame(int* arr, int len, int num) {
	int i;
	for (i = 0; i < len; i++)
		if (arr[i] == num)
			break;
	return i != len;
}
bool next_perm(int* perm, const int k, const int n) {
	int i = k - 1;
	do
		perm[i]++;
	while (arrsame(perm, i, perm[i]) || (perm[i] >= n && i--));
	if (perm[0] >= n)
		return 0;
	for (int num = 0, seat = i + 1; seat < k; num++)
		if (!arrsame(perm, i + 1, num))
			perm[seat++] = num;
	return 1;
}
int main() {
	int n, k;
	cout << "perm(n,k):" << endl;
	cin >> n >> k;
	if (n < k || k <= 0)
		return 0;
	int* perm = new int[k];
	for (int i = 0; i < k; i++)
		perm[i] = i;
	do
		for (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))
			cout << perm[i] + 1;
	while (next_perm(perm, k, n));
	delete[] perm;
	return 0;
}
```

### 递回法

```cpp
#include <bits/stdc++.h>
using namespace std;

struct prem {
	int len;
	vector<int> used, position;
	function<void(vector<int>&)> action;
	prem(int l = 0, function<void(vector<int>&)> a = [](vector<int>& position) {}) : len(l), used(l, -1), position(l), action(a) {}
	void run(int now = -1) {
		if (now == len - 1) {
			action(position);
			return;
		}
		int next = now + 1;
		for (int i = 0; i < len; i++) {
			if (used[i] == -1) {
				used[i] = next;
				position[next] = i;
				run(next);
				used[i] = -1;
			}
		}
	}
};
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int len = 4;
	prem p(len, [&](vector<int>& p) {
		for (int i = 0; i < len; i++) {
			cout << p[i] << " ";
		}
		cout << endl;
	});
	p.run();
	return 0;
}
```

## python演算范例

```python
import sys

def perm(dim, num):
    if not 0 <= num <= dim:
        print('It must be that 0 <= num <= dim!', flush=True, file=sys.stderr)
        return []

    result = []
    xstack = []

    arr = []
    xset = set(range(dim, 0, -1))

    xstack.append((arr, xset))

    while len(xstack):
        theArr, theSet = xstack.pop()
        for theInt in theSet:
            newSet = theSet.copy()
            newSet.remove(theInt)
            newArr = theArr.copy()
            newArr.append(theInt)
            if num == len(newArr):
                result.append(newArr)
            else:
                xstack.append((newArr, newSet))
    return result
```

## 外部链接

- 许多排列组合问题，附详解。
- 置换及图论问题