排列
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目需要補充更多來源。 (2018年9月4日) |
「Permutation」的各地常用名稱 | |
---|---|
中國大陸 | 排列 |
臺灣 | 排列、置換 |
港澳 | 排列 |
日本 | 置換 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Permutations_RGB.svg/220px-Permutations_RGB.svg.png)
排列(英語: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個對象的置換」。
定義
[編輯]
恆等置換的定義為置換使得對所有,。
所有關於個元素的集合的置換組成的集合構成對稱群,其群運算為函數的複合。因此兩個置換,和的積的定義為
兩個置換的複合一般不滿足交換律:。
置換數的計算
[編輯]此節使用置換的傳統定義。從個相異元素中取出個元素,個元素的排列數量為:
其中P意為Permutation(排列),!表示階乘運算。
以賽馬為例,有8匹馬參加比賽,玩家需要在彩票上填入前三勝出的馬匹的號碼,從8匹馬中取出3匹馬來排前3名,排列數量為:
因為一共存在336種可能性,因此玩家在一次填入中中獎的概率應該是:
不過,中國大陸的教科書則是把從n取k的情況記作或(A代表Arrangement,即排列)。[1]
重複置換
[編輯]上面的例子是建立在取出元素不重複出現狀況。
從個元素中取出個元素,個元素可以重複出現,這排列數量為:
以四星彩為例,10個數字取4個數字,因可能重複所以排列數量為:
這時的一次性添入中獎的概率就應該是:
抽象代數
[編輯]在集合論與抽象代數等領域中,「置換」一詞被保留為集合(通常是有限集)到自身的對射的一個稱呼。例如對於從一到十的數字構成的集合,其置換將是從集合 到自身的對射。因此,置換是擁有相同定義域與對應域的函數,且其為對射的。一個集合上的置換在函數合成運算下構成一個群,稱為對稱群或置換群。
符號
[編輯]以下僅考慮有限集上的置換(視為對射),由於 個元素的有限集可以一一對應到集合 ,有限集的置換可以化約到形如 {1, ..., n} 的集合之置換。此時有兩種表示法。
第一,利用矩陣符號將自然排序寫在第一列,而將置換後的排序寫在第二列。例如:
表示集合 {1,2,3,4,5} 上的置換 。
第二,藉由置換的相繼作用描述,這被稱為「輪換分解」。分解方式如下:固定置換 。對任一元素 ,由於集合有限而 是對射,必存在正整數 使得 ,故可將置換 對 的相繼作用表成 ,其中 是滿足 的最小正整數。
稱上述表法為 在 下的輪換, 稱為輪換的長度。我們在此將輪換視作環狀排列,例如
- 與
是同一個輪換。由此可知 在 下的輪換只決定於 在 作用下的軌道,於是,任兩個元素 或給出同一個輪換,或給出不交的輪換。
我們將輪換 理解為一類特殊的置換[注 2]:僅須定義置換 為 ,而在其它元素上定義為恆等映射。不交的輪換在函數合成的意義下可相交換。
因此我們可以將集合 {1, ..., n} 對一置換分解成不交輪換的合成,此分解若不計順序則是唯一的。例如前一個例子的 就對應到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。
輪換
[編輯]輪換一是種特殊的置換。
如果給定是上的一個置換,為上的一個子集。
若有
則稱 為一個輪換。 為輪換的長度。
特殊置換
[編輯]在上節的置換表法中,長度等於二的環狀置換稱為換位,這種環狀置換 不外是將元素 交換,並保持其它元素不變。對稱群可以由換位生成。
由於環狀置換長度為的置換可分解為最少個換位,若為偶數,則為偶換位,否則為奇換位。即環狀置換的長度為奇數,該置換為偶換位;環狀置換的長度為偶數,該置換為奇換位。
由此可定義任一置換的奇偶性,並可證明:一個置換是偶換位的充要條件是它可以由偶數個換位生成。偶換位在置換群中構成一個正規子群,稱為交錯群。
計算理論中的置換
[編輯]某些舊課本將置換視為變量值的賦值。在計算機科學中,這就是將值
- 1, 2, ..., n
賦予變量
- x1, x2, ..., xn
的賦值運算子,並要求每個值只能賦予一個變量。
賦值/代入的差別表明函數式編程與指令式編程之差異。純粹的函數式編程並不提供賦值機制。現今數學的慣例是將置換看作函數,其間運算看作函數合成,函數式編程也類似。就賦值語言的觀點,一個代入是將給定的值「同時」重排,這是個有名的問題。
置換圖
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/8/80/Permutation_graph_251436.png)
取一個無向圖G,將圖G的n個頂點標記v1,...,vn,對應一個置換( s(1) s(2) ... s(n) ),當且僅當s(i) < s(j) 而 i > j,則圖的vi和vj相連,這樣的圖稱為置換圖。
置換圖的補圖必是置換圖。
使用計算器
[編輯]多數計算器都有個計算置換數的 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 <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演算範例
[編輯]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
註釋
[編輯]參考文獻
[編輯]- ^ 普通高中教科书 数学 选择性必修第三册(A版). 北京市海淀區中關村南大街17號院1號樓: 人民教育出版社. : 17 [2024-03-30]. ISBN 978-7-107-34598-2.
- ^ 組合數學 ─算法與分析─. 九章出版社. : 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.