排列

置換或排列。例如，從一到六的數字有720種排列，對應於由這些數字組成的所有不重複亦不闕漏的序列，例如"4, 5, 6, 1, 2, 3" 與"1, 3, 5, 2, 4, 6"。置-{}-換的廣義概念在不同語境下有不同的形式定義：置換數的計算.此節使用置換的傳統定義。從formula_1個相異元素中取出formula_2個元素，formula_2個元素的排列數量為：formula_4其中P意為Permutation，!表示階乘運算。以賽馬為例，有8匹馬參加比賽，玩家需要在彩票上填入前三勝出的馬匹的號碼，從8匹馬中取出3匹馬來排前3名，排列數量為：formula_5因為一共存在336種可能性，因此玩家在一次填入中中獎的機率應該是：formula_6不過，中國大陸的教科書則是把從n取k的情況記作formula_7或formula_8。重複置換.上面的例子是建立在取出元素不重複出現狀況。從formula_1個元素中取出formula_2個元素，formula_2個元素可以重複出現，這排列數量為：formula_12以四星彩為例，10個數字取4個數字，因可能重複所以排列數量為：formula_13這時的一次性添入中獎的機率就應該是：formula_14抽象代數.在集合論與抽象代數等領域中，「置-{}-換」一詞被保留為集合到自身的雙射的一個稱呼。例如對於從一到十的數字構成的集合，其置-{}-換將是從集合 formula_15 到自身的雙射。因此，置-{}-換是擁有相同定義域與上域的函式，且其為雙射的。一個集合上的置-{}-換在函式合成運算下構成一個群，稱為對稱群或置換群。符號.以下僅考慮有限集上的置-{}-換，由於 formula_1 個元素的有限集可以一一對應到集合 formula_17，有限集的置-{}-換可以化約到形如 {1, ..., n} 的集合之置-{}-換。此時有兩種表示法。第一，利用矩陣符號將"自然"排序寫在第一列，而將置-{}-換後的排序寫在第二列。例如：formula_18表示集合 {1,2,3,4,5} 上的置-{}-換 formula_19。第二，藉由置-{}-換的相繼作用描述，這被稱為「輪換分解」。分解方式如下：固定置-{}-換 formula_20。對任一元素 formula_21，由於集合有限而 formula_20 是雙射，必存在正整數 formula_23 使得 formula_24，故可將置-{}-換 formula_20 對 formula_21 的相繼作用表成 formula_27，其中 formula_28 是滿足 formula_29 的最小正整數。稱上述表法為 formula_21 在 formula_20 下的輪換， formula_28 稱為輪換的長度。我們在此將輪換視作環狀排列，例如formula_33 與formula_34是同一個輪換。由此可知 formula_21 在 formula_20 下的輪換隻決定於 formula_21 在 formula_20 作用下的軌道，於是，任兩個元素 formula_39 或給出同一個輪換，或給出不交的輪換。我們將輪換 formula_40 理解為一類特殊的置-{}-換：僅須定義置-{}-換 formula_20 為 formula_42，而在其它元素上定義為恆等對映。不交的輪換在函式合成的意義下可相交換。因此我們可以將集合 {1, ..., n} 對一置-{}-換分解成不交輪換的合成，此分解若不計順序則是唯一的。例如前一個例子的 formula_20 就對應到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。輪換.輪換一是種特殊的置換。如果給定formula_44是formula_45上的一個置換，formula_46為formula_45上的一個子集。若有formula_48formula_49則稱formula_50 為一個輪換。formula_51 為輪換的長度。特殊置換.在上節的置換表法中，長度等於二的環狀置換稱為換位，這種環狀置換 formula_52 不外是將元素 formula_39 交換，並保持其它元素不變。對稱群可以由換位生成。由於環狀置換長度為formula_51的置換formula_55可分解為最少formula_56個換位，若formula_2為偶數，則formula_55為偶換位，否則formula_55為奇換位。即環狀置換的長度為奇數，該置換為偶換位；環狀置換的長度為偶數，該置換為奇換位。由此可定義任一置換的奇偶性，並可證明：一個置換是偶換位的充要條件是它可以由偶數個換位生成。偶換位在置換群中構成一個正規子群，稱為交錯群。計算理論中的置換.某些舊課本將置換視為變數值的"賦值"。在電腦科學中，這就是將值1, 2, ..., "n"賦予變數"x"1, "x"2, ..., "x""n"的賦值運運算元，並要求每個值只能賦予一個變數。賦值/代入的差別表明函數語言程式設計與指令式程式設計之差異。純粹的函數語言程式設計並不提供賦值機制。現今數學的慣例是將置換看作函式，其間運算看作函式合成，函數語言程式設計也類似。就賦值語言的觀點，一個代入是將給定的值「同時」重排，這是個有名的問題。置換圖.取一個無向圖"G"，將圖"G"的"n"個頂點標記"v"1...,"v"n，對應一個置換( s(1) s(2) ... s("n") )，若且唯若s("i")  "j"，則圖的"v"i和"v"j相連，這樣的圖稱為置換圖。置換圖的補圖必是置換圖。使用計算器.多數計算器都有個計算置換數的 "nPr" 鍵。然而此鍵在一些最先進的桌上型機種中卻被隱藏了。例如：在 TI-83 中，按 MATH、三次右鍵、再按二。在卡西歐的圖形計算機中，按 OPTN，一次右鍵。試算表語法.多數試算表軟體都有函式 PERMUT("Number"，"Number chosen")，用以計算置換。"Number" 是描述物件數量的一個整數，"Number chosen" 是描述每個置換中所取物件數的整數。C++演算範例.迴圈法.using namespace std;bool arrsame(int* arr, int len, int num) {int i;for (i = 0; i = n)return 0;for (int num = 0, seat = i + 1; seat &lt; 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 &lt; k || k &lt;= 0)return 0;int* perm = new int[k];for (int i = 0; i &lt; k; i++)perm[i] = i;dofor (int i = 0; i &lt; k; cout « ((++i &lt; k) ? ',' : '\n'))cout « perm[i] + 1;while (next_perm(perm, k, n));delete[] perm;return 0;遞迴法.using namespace std;struct prem {int len;vector used, position;function action;void run(int now = -1) {if (now == len - 1) {action(position);return;int next = now + 1;for (int i = 0; i &lt; 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, [&amp;](vector&amp; p) {for (int i = 0; i &lt; len; i++) {cout « p[i] « " ";cout « endl;p.run();return 0;python演算範例.import sysdef perm(dim, num):if not 0 &lt;= num &lt;= dim:print('It must be that 0 &lt;= num &lt;= 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