{{Forceconvert|-{zh-cn:;zh-tw:;}-}}
排列又称置換，是將相異物件或符號根據確定的順序重排，得到的每個順序都稱作一個-{zh-cn:排列; zh-hk:排列; zh-tw:排列或置換;}-。例如，從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的賦值運算子，並要求每個值只能賦予一個變數。
賦值/代入的差別表明函數式編程與指令式編程之差異。純粹的函數式編程並不提供賦值機制。現今數學的慣例是將置換看作函數，其間運算看作函數合成，函數式編程也類似。就賦值語言的觀點，一個代入是將給定的值「同時」重排，這是個有名的問題。
置換圖
取一個無向圖G，將圖G的n個頂點標記為v_1, ..., v_n，對應一個置換（s(1) \; s(2) \; \cdots \; s(n)），若且唯若s(i) 而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
using namespace std;
bool arrsame(int* arr, int len, int num) {
int i;
for (i = 0; i = n && i--));
if (perm[0] >= n)
return 0;
for (int num = 0, seat = i + 1; seat > n >> k;
if (n
遞迴法
#include
using namespace std;
struct prem {
int len;
vector used, position;
function&)> action;
prem(int l = 0, function&)> a = [](vector& 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 & p) {
for (int i = 0; i
python演算範例
import sys
def perm(dim, num):
if not 0
注释
參考文獻
- 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.
外部連結
评论 (0)