dvrgv

P(3,3)=6

排列（英语：Permutation）是將相異物件或符號根據確定的順序重排。每個順序都稱作一個排列^[1]。例如，從一到六的數字有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個對象的置換」。

置換數的计算

此節使用置換的傳統定義。从 $n$ 个相異元素中取出 $k$ 个元素， $k$ 个元素的排列數量為：

P_{k}^{n}={frac {n!}{(n-k)!}}

其中P意为Permutation（排列），!表示階乘運算。

以賽馬為例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，從8匹馬中取出3匹馬來排前3名，排列數量為：

P_{3}^{8}={frac {8!}{(8-3)!}}=336

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

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

不過，中國大陸的教科書則是把從n取k的情況記作 ${displaystyle P_{n}^{k}}$ 或 ${displaystyle A_{n}^{k}}$ （A代表Arrangement，即排列）。

重複置換

上面的例子是建立在取出元素不重複出現狀況。

從 $n$ 个元素中取出 $k$ 个元素， $k$ 个元素可以重复出现，這排列數量為：

U_{k}^{n}=n^{k}

^[2]

以四星彩為例，10個數字取4個數字，因可能重複所以排列數量為：

U_{4}^{10}=10^{4}=10000

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

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

抽象代數

在集合論與抽象代數等領域中，「置換」一詞被保留為集合（通常是有限集）到自身的雙射的一個稱呼。例如對於從一到十的數字構成的集合，其置換將是從集合 ${ 1, ldots, 10 }$ 到自身的雙射。因此，置換是擁有相同定義域與上域的函數，且其為雙射的。一個集合上的置換在函數合成運算下構成一個群，稱為對稱群或置換群。

符號

以下僅考慮有限集上的置換（視為雙射），由於 $n$ 個元素的有限集可以一一對應到集合 ${ 1, ldots, n}$ ，有限集的置換可以化約到形如 {1, ..., n} 的集合之置換。此時有兩種表示法。

第一，利用矩陣符號將自然排序寫在第一列，而將置換後的排序寫在第二列。例如：

begin{pmatrix}<br/>1 & 2 & 3 & 4 & 5 \ <br/>2 & 5 & 4 & 3 & 1end{pmatrix}

表示集合 {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$ 的相繼作用表成 ${displaystyle (x;s(x);s^{2}(x)cdots s^{m-1}(x))}$ ，其中 $m$ 是滿足 ${displaystyle 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)$ 理解為一類特殊的置換^[3]：僅須定義置換 $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:Xrightarrow X$ 是 $X$ 上的一個置換， $A$ 為 $X$ 上的一個子集。

若有

${displaystyle exists Ain X,A={x_{1},x_{2},cdots ,x_{l}}}$

${displaystyle {begin{cases}f(x_{1})=x_{2},f(x_{2})=x_{3},cdots ,f(x_{l})=x_{1}\f(x)=x,xnot in Aend{cases}}}$

則稱 $f$ 為一個輪換。 $l$ 為輪換的長度。

特殊置換

在上節的轮换表法中，長度等於二的轮换稱為換位，這種轮换 $(x ; y)$ 不外是將元素 $x, y$ 交換，並保持其它元素不變。對稱群可以由換位生成。

由於輪換長度為 $l$ 的輪換 $C$ 可分解為最少 ${displaystyle k=l-1}$ 個換位，若 $k$ 為偶數，則 $C$ 為偶輪換，否則C為奇輪換。即輪換的長度為奇數，該輪換為偶輪換；輪換的長度為偶數，該輪換為奇輪換。

由此可定義任一置換的奇偶性，並可證明：一個置換是偶置換的充要條件是它可以由偶數個換位生成。偶轮换在置換群中構成一個正規子群，稱為交错群。

計算理論中的置換

某些舊課本將置換視為變數值的賦值。在計算機科學中，這就是將值

1, 2, ..., n

賦予變數

x₁, x₂, ..., x_n

的賦值運算子，並要求每個值只能賦予一個變數。

賦值/代入的差別表明函數式編程與指令式編程之差異。純粹的函數式編程並不提供賦值機制。現今數學的慣例是將置換看作函數，其間運算看作函數合成，函數式編程也類似。就賦值語言的觀點，一個代入是將給定的值「同時」重排，這是個有名的問題。

置換圖

(2,5,1,4,3,6)的置換圖

取一個無向圖G，將圖G的n個頂點標記v₁,...,v_n，對應一個置換( s(1) s(2) ... 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++演算範例

迴圈法

#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;
}

遞迴法

#include <iostream>
#include <cstdio>
using namespace std;

namespace perm {
int n, k;
int arr[12];
int count;
bool arrsame(int site) {
	for (int i = 0; i < site; i++)
		if (arr[i] == arr[site])
			return 0;
	return 1;
}
inline void arrprint() {
	for (int i = 0; i < k; i++)
		printf("%3d", arr[i]);
	puts("");
	count++;
}
void calculate(int now) {
	if (now == k) {
		arrprint();
		return;
	}
	for (int i = 0; i < n; i++) {
		arr[now] = i;
		if (arrsame(now)) {
			calculate(now + 1);
		}
	}
}
inline void run(int nn, int kk) {
	n = nn, k = kk;
	count = 0;
	if (k < 12 && n >= k && k > 0)
		calculate(0);
	if (count)
		printf("n%d permutation.nn", count);
	else
		puts("Input error!");
}
}

int main() {
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF) {
		perm::run(n, k);
		fflush(stdout);
	}
	return 0;
}

參考資料

^ 對於不排序的情形，請見條目組合。

^ 組合數學 ─算法與分析─. 九章出版社. : 29. OCLC:44527392

^ 可遞置換

參考文獻

Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 978-1-58488-434-7.

Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 978-0-201-85393-3.

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.

外部連結

許多排列組合問題，附詳解。（英文）

置換及圖論問題（英文）

[combination-1] 對於不排序的情形，請見條目組合。

[組合數學-2] 組合數學 ─算法與分析─. 九章出版社. : 29. OCLC:44527392

[3] 可遞置換

搜尋此網誌