排列

排列又稱置換，是將相異物件或符號根據確定的順序重排，得到的每個順序都稱作一個排列或置換。例如，從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
```

## 外部連結

- 許多排列組合問題，附詳解。
- 置換及圖論問題