置換

P(3,3)=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個對象的置換」。

置換計數

此節使用置換的傳統定義：一個置換是從$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$

其它較舊的記法包括ⁿP_r, P_n,r或_nP_r。另外在中国大陆高中教科书及某些美国课本上，用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$，故可將置換 $s$ 對 $x$ 的相繼作用表成 $(x \; s(x) \; s^2(x) \cdots s^m(x))$，其中 $s^m(x)$ 是滿足 $s^m(x) \neq 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)。

特殊置換

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

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

計算理論中的置換

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

1, 2, ..., n

賦予變數

x₁, x₂, ..., x_n.

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

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

置換圖

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

取一個無向圖G，將圖G的n個頂點標記v₁,...,v_n，對應一個置換( s(1) s(2) ... s(n) )，若且唯若s(i) < s(j) 而 i > j，則圖的v_i和v_j相連，這樣的圖稱為置換圖。

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

使用計算機

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

試算表語法

多數試算表軟件都有函式 PERMUT(Number，Number 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

參考文獻

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

外部連結

• 許多排列組合問題，附詳解。
• 置換及圖論問題