置換

维基百科,自由的百科全书
跳转至: 导航搜索
P(3,3)=6

排列是將相異物件或符號根據確定的順序重排。每個順序都稱作一個排列[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個相異元素中取出r個元素並加以排序的可能方式。所有可能的置換數為:

 P^n_r = \frac{n!}{(n-r)!}

其中:

  • P意为Permutation(排列),
  • r是每個置換的長度,
  • n是所置換的元素數量,
  • ! 表示階乘運算。

例一:假設我們有10個元素,即整數{1,2,...,10},並考慮從中取出3個元素的所有可能性(含順序),此時須取n=10, r=3,並計算

P_{3}^{10} = 10\times 9\times 8 = 720

注意,在含实际数字的计算中,不要使用排列数公式,因为分子分母会约掉一部分。

例二:從{1, ..., 6}取出6個元素(含順序),也就是將數字1到6重新排序的方式共有

P^6_6 = 6! = 720

其它較舊的記法包括nPr, Pn,rnPr。另外在中国大陆高中教科书及某些美国课本上,用A(Arrangement)替代P,即 A_r^n

抽象觀點[编辑]

如上所述,在集合論抽象代數等領域中,「置換」一詞保留作集合(通常是有限集)到自身的雙射。例如對於從一到十的數字構成的集合,其置換將是從集合 \{ 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(x)),其中 s^m(x) 是滿足 s^m(x) \neq 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) 理解為一類特殊的置換[2]:僅須定義置換 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 是描述每個置換中所取物件數的整數。

生成排列[编辑]

性质[编辑]

A=\left \{a_{1},a_{2}\cdots ,a_{n} \right \},B=\left \{b_{1},b_{2}\cdots ,b_{n} \right \},B是大于A的,在字典序下的,最小的全排列。

在A和B中,从左往右数,第一个不相等的元素下标为k(1≤k≤n);则

  1. a_{1}=b_{1}, a_{2}=b_{2}, \cdots,  a_{k-1}=b_{k-1}, a_{k}<b_{k}
  2. B中,b_{k}后面的元素按升序排列。(因为B是大于A的最小的全排列)
  3. b_{k}=min\left \{a_{j}|a_{j}>a_{k};j=k+1,k+2,\cdots ,n \right \}。意思是,A与B第一个不相同的数b_{k}是A的a_{k}之后大于a_{k}的最小的数。
  4. 对于任意比A大的全排列R,从左往右数,第一个不相等的元素下标为m,必然m≤k。(因为B是大于A的最小的全排列)

算法[编辑]

以下是一种排列生成算法的Java语言实现

/**
 * @author: contribute to wikipedia according GNU
 * @description 生成n阶排列
 */
public class permutations {
    public static int[] perm;  //为排列定义一个数组  
	public static int[] drct; //为排列的方向箭头定义一个数组 
	public static int n; 	
	public static int largest_mobile_val;
 
	//寻找最大的可移动的数
	public static boolean find_largest_mobile() 
	{ int idx_temp1 = -1;
 
	 for(int n_temp1 = n; n_temp1 >=1; n_temp1 --)
	 { 
		 for(int s_temp = 0; s_temp < n; s_temp ++)
		 { if(perm[s_temp] == n_temp1)
			 idx_temp1 = s_temp;
		 }
 
		 if (drct[idx_temp1] == 0)
	 { if(idx_temp1 == 0)
	 continue;
	 else
	 {
	 	 if(perm[idx_temp1 - 1] < perm[idx_temp1])
	 	 {
	 		 largest_mobile_val = perm[idx_temp1];
	 		 swith_m_and_adjacent(idx_temp1,idx_temp1 - 1);
	 		 return true;
	 	 }
	 }
	 }
	 else
	 { 
	 	 if(idx_temp1 == n-1)
                   continue;
               else
               {
        	       if(perm[idx_temp1 + 1] < perm[idx_temp1])
        	       {
        	    	   largest_mobile_val = perm[idx_temp1];
        	    	   swith_m_and_adjacent(idx_temp1,idx_temp1 + 1);
        	    	   return true;
        	       }
               }
 
	 }
	 }
	 return false;
	}
	public static void swith_m_and_adjacent(int idx_m, int idx_adjacent) 
	//idx_m,idx_adjacen是m的位置(下标)和它的邻居 
	{ //交换perm里的数据 
	 int sub_temp;
	 sub_temp = perm[idx_m];
	 perm[idx_m] = perm[idx_adjacent];
	 perm[idx_adjacent] = sub_temp;
 
	 //交换方向值 
	 int drc_temp;
	 drc_temp = drct[idx_m];
	 drct[idx_m] = drct[idx_adjacent];
	 drct[idx_adjacent] = drc_temp; 
	}
 
	public static void switch_direction_of_arrows_bigthan_m(int m)
	{ int idx_temp2;
		for(idx_temp2 = 0; idx_temp2 < n;idx_temp2 ++)
		{
			if (perm[idx_temp2] > m)
			{
				drct[idx_temp2] = 1 - drct[idx_temp2];
			}
		}
	}
 
	public static void print()
	{ 
	 System.out.print("\n");
		for(int j = 0;j< n;j ++)
		{
			if(drct[j] == 0) 
				System.out.print("<");
			else
				System.out.print(">");
			System.out.print(" ");
		}
		System.out.println();
 
 
		for(int j = 0;j< n;j ++)
		{
			System.out.print(perm[j]);
			System.out.print(" ");
		}
		System.out.println();
 
	}
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		n = 4;
		perm = new int[5]; 
        perm [0] = 1; perm [1] = 2; perm [2] = 3; perm [3] = 4;
        drct = new int[5];  
       drct [0] = 0; drct [1] = 0; drct [2] = 0; drct [3] = 0; 
        //0表示左箭头 1表示右箭头
 
       print() ;
 
       while(find_largest_mobile())
       {
       	switch_direction_of_arrows_bigthan_m(largest_mobile_val);
       	print() ;
       }        
	}
 
}
输入:
默认值为main函数中的n=4
输出:

< < < < 
1 2 3 4 

< < < < 
1 2 4 3 

< < < < 
1 4 2 3 

< < < < 
4 1 2 3 

> < < < 
4 1 3 2 

< > < < 
1 4 3 2 

< < > < 
1 3 4 2 

< < < > 
1 3 2 4 

< < < < 
3 1 2 4 

< < < < 
3 1 4 2 

< < < < 
3 4 1 2 

< < < < 
4 3 1 2 

> > < < 
4 3 2 1 

> > < < 
3 4 2 1 

> < > < 
3 2 4 1 

> < < > 
3 2 1 4 

< > < < 
2 3 1 4 

< > < < 
2 3 4 1 

< < > < 
2 4 3 1 

< < > < 
4 2 3 1  

> < < > 
4 2 1 3 

< > < > 
2 4 1 3 

< < > > 
2 1 4 3 

< < > > 
2 1 3 4

參考資料[编辑]

  1. ^ 對於不排序的情形,請見條目組合
  2. ^ 可遞置換

參考文獻[编辑]

  • Miklos Bona. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 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 0-201-85393-0.
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.

外部連結[编辑]