本页使用了标题或全文手工转换

置換

维基百科,自由的百科全书
跳转至: 导航搜索
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的情況記作P^k_nA^k_n(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}
1 & 2 & 3 & 4 & 5 \\ 
2 & 5 & 4 & 3 & 1\end{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,故可將置換 sx 的相繼作用表成 (x \; s(x) \; s^2(x) \cdots s^{m-1} (x)),其中 m 是滿足 s^{m}(x) = x 的最小正整數。

稱上述表法為 xs 下的轮换m 稱為轮换的長度。我們在此將轮换視作環狀排列,例如

(a_1 \; a_2 \; a_3 \cdots a_m)
(a_m \; a_1 \; a_2 \cdots a_{m-1})

是同一個轮换。由此可知 xs 下的轮换只決定於 xs 作用下的軌道,於是,任兩個元素 x, y 或給出同一個轮换,或給出不交的轮换。

我們將轮换 (x_1 \; \cdots x_m) 理解為一類特殊的置換[3]:僅須定義置換 ss: 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)。

特殊置換[编辑]

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

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

計算理論中的置換[编辑]

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

1, 2, ..., n

賦予變數

x1, x2, ..., xn

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

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

置換圖[编辑]

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

取一個無向G,將圖Gn個頂點標記v1,...,vn,對應一個置換( s(1) s(2) ... s(n) ),若且唯若s(i) < s(j) 而 i > j,則圖的vivj相連,這樣的圖稱為置換圖。

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

使用計算機[编辑]

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

試算表語法[编辑]

多數試算表軟件都有函式 PERMUT(NumberNumber chosen),用以計算置換。Number 是描述物件數量的一個整數,Number chosen 是描述每個置換中所取物件數的整數。

演算範例[编辑]

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

參考資料[编辑]

  1. ^ 對於不排序的情形,請見條目組合
  2. ^ 組合數學 ─算法與分析─. 九章出版社. : 29.  OCLC:44527392
  3. ^ 可遞置換

參考文獻[编辑]

  • 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.

外部連結[编辑]