查看“置換”的源代码

{{refimprove|time=2018-09-04T08:27:17+00:00}}
{{NoteTA
|G1 = Math
}}
{{Forceconvert|-{zh-cn:{{Redirect2|置换|化学中的置换|置换反应}}; zh-tw:{{About|數學中的置換|化學中的置換|置換反應}};}-}}
[[File:Permutations RGB.svg|thumb|P(3,3)=6]]

'''排列'''（{{lang-en|Permutation}}）是將相異物件或符號根據確定的順序重排。每個順序都稱作一個-{zh-cn:'''排列'''; zh-tw:'''置換'''或'''排列''';}-<ref name="combination" group="注">對於不排序的情形，請見條目[[組合]]。</ref>。例如，從一到六的[[數字]]有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個對象的置換」。

== 置換數的计算 ==
此節使用置換的傳統定義。从<math>n</math>个相異元素中取出<math>k</math>个元素，<math>k</math>个元素的排列數量為：
:<math> P_k^n = \frac{n!}{(n-k)!}</math>
其中'''P'''意为Permutation（排列），'''!'''表示[[階乘]]運算。

以[[賽馬]]為例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，從8匹馬中取出3匹馬來排前3名，排列數量為：
:<math> P_3^8 =\frac{8!}{(8-3)!}=336</math>

因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：
:<math> P = \frac{1}{336}= 0.00298</math>

不過，中國大陸的教科書則是把從n取k的情況記作<math>P^k_n</math>或<math>A^k_n</math>（A代表Arrangement，即排列）。

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

從<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素可以重复出现，這排列數量為：
:<math> U_k^n = n^k</math><ref name="組合數學">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 |  pages=29}} OCLC:44527392 </ref>

以[[中華民國公益彩券|四星彩]]為例，10個數字取4個數字，因可能重複所以排列數量為：
:<math>U_4^{10}=10^4=10000</math>

这时的一次性添入中奖的概率就应该是：
:<math>P=\frac{1}{10000}=0.0001</math>

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

== 符號 ==
{{further|對稱群 (n次对称群)}}
以下僅考慮有限集上的置-{}-換（視為[[雙射]]），由於 <math>n</math> 個元素的有限集可以一一對應到集合 <math>\{ 1, \ldots, n\}</math>，有限集的置-{}-換可以化約到形如 {1, ..., n} 的集合之置-{}-換。此時有兩種表示法。

第一，利用矩陣符號將''自然''排序寫在第一列，而將置-{}-換後的排序寫在第二列。例如：
: <math>\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
2 & 5 & 4 & 3 & 1\end{pmatrix}</math>
表示集合 {1,2,3,4,5} 上的置-{}-換 <math>s: s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1</math>。

第二，藉由置-{}-換的相繼作用描述，這被稱為「[[轮换分解]]<!--Cycle decomposition-->」。分解方式如下：固定置-{}-換 <math>s</math>。對任一元素 <math>x</math>，由於集合有限而 <math>s</math> 是雙射，必存在正整數 <math>N</math> 使得 <math>s^N(x)=x</math>，故可將置-{}-換 <math>s</math> 對 <math>x</math> 的相繼作用表成 <math>(x \; s(x) \; s^2(x) \cdots s^{m-1} (x))</math>，其中 <math>m</math> 是滿足 <math>s^{m}(x) = x</math> 的最小正整數。

稱上述表法為 <math>x</math> 在 <math>s</math> 下的'''轮换'''， <math>m</math> 稱為轮换的'''長度'''。我們在此將轮换視作[[環狀排列]]，例如
: <math>(a_1 \; a_2 \; a_3 \cdots a_m)</math> 與
: <math>(a_m \; a_1 \; a_2 \cdots a_{m-1})</math>
是同一個轮换。由此可知 <math>x</math> 在 <math>s</math> 下的'''轮换'''只決定於 <math>x</math> 在 <math>s</math> 作用下的軌道，於是，任兩個元素 <math>x, y</math> 或給出同一個轮换，或給出不交的轮换。

我們將轮换 <math>(x_1 \; \cdots x_m)</math> 理解為一類特殊的置-{}-換<ref group="注">可遞置-{}-換</ref>：僅須定義置-{}-換 <math>s</math> 為 <math>s: x_1 \mapsto x_2, \ldots, x_{m-1} \mapsto x_m, x_m \mapsto x_1</math>，而在其它元素上定義為[[恆等映射]]。不交的轮换在函數合成的意義下可相交換。

因此我們可以將集合 {1, ..., n} 對一置-{}-換分解成不交轮换的合成，此分解若不計順序則是唯一的。例如前一個例子的 <math>s</math> 就對應到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。

== 輪換 ==
輪換一是種特殊的置換。

如果給定<math>f:X\rightarrow X</math>是<math>X</math>上的一個置換，<math>A</math>為<math>X</math>上的一個子集。

若有

<math>\exists A\in X,A=\{x_1,x_2,\cdots,x_l\}</math>

<math>\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}
</math>

則稱<math>f</math> 為一個輪換。<math>l</math> 為輪換的長度。

== 特殊置換 ==
在上節的轮换表法中，長度等於二的轮换稱為'''換位'''，這種轮换 <math>(x \; y)</math> 不外是將元素 <math>x, y</math> 交換，並保持其它元素不變。[[对称群 (n次对称群)|對稱群]]可以由換位生成。

由於輪換長度為<math>l</math>的輪換<math>C</math>可分解為最少<math>k=l-1</math>個換位，若<math>k</math>為偶數，則<math>C</math>為'''偶輪換'''，否則C為'''奇輪換'''。即輪換的長度為奇數，該輪換為'''偶輪換'''；輪換的長度為偶數，該輪換為'''奇輪換'''。

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

== 計算理論中的置換 ==
某些舊課本將置換視為變數值的''賦值''。在[[計算機科學]]中，這就是將值
: 1, 2, ..., ''n'' 
賦予變數
:''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub>
的賦值運算子，並要求每個值只能賦予一個變數。

賦值/代入的差別表明[[函數式編程]]與[[指令式編程]]之差異。純粹的函數式編程並不提供賦值機制。現今數學的慣例是將置換看作函數，其間運算看作函數合成，函數式編程也類似。就賦值語言的觀點，一個代入是將給定的值「同時」重排，這是個有名的問題。
== 置換圖 ==
[[File:Permutation_graph_251436.png|thumb|(2,5,1,4,3,6)的置換圖]]

取一個無向[[圖]]''G''，將圖''G''的''n''個[[顶点 (图论)|頂點]]標記''v''<sub>1</sub>,...,''v''<sub>n</sub>，對應一個置換( s(1) s(2) ... s(''n'') )，若且唯若s(''i'') < s(''j'') 而 ''i'' > ''j''，則圖的''v''<sub>i</sub>和''v''<sub>j</sub>相連，這樣的圖稱為置換圖。

置換圖的[[補圖]]必是置換圖。

== 使用計算機 ==
多數[[計算機]]都有個計算置換數的 ''nPr'' 鍵。然而此鍵在一些最先進的桌上型機種中卻被隱藏了。例如：在 TI-83 中，按 MATH、三次右鍵、再按二。在[[卡西歐]]的圖形計算機中，按 OPTN，一次右鍵（F6）、PROB（F3）、nPr（F2）。

== 試算表語法 ==
多數[[試算表]]軟件都有函式 PERMUT(''Number''，''Number chosen'')，用以計算置換。''Number'' 是描述物件數量的一個整數，''Number chosen'' 是描述每個置換中所取物件數的整數。

==C++演算範例==
===迴圈法===
<source lang="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;
}
</source>
===遞迴法===
<source lang="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;
}
</source>

== 注释 ==
<references group="注"/>

== 參考文獻 ==
<references/>
* Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 978-1-58488-434-7.
* Donald Knuth. ''The Art of Computer Programming'', Volume&nbsp;4: ''Generating All Tuples and Permutations'', Fascicle&nbsp;2, first printing. Addison-Wesley, 2005. ISBN 978-0-201-85393-3. 
* Donald Knuth. ''The Art of Computer Programming'', Volume&nbsp;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.

== 外部連結 ==
* [http://mathforum.org/library/drmath/sets/high_perms_combs.html 許多排列組合問題，附詳解。]{{en}}
* [http://www.cut-the-knot.org/do_you_know/permutation.shtml 置換及圖論問題 ]{{en}}

[[Category:抽象代数|Z]]
[[Category:集合論基本概念|Z]]
[[Category:置换|Z]]