排列（英语：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个对象的置换”。

[micxp_threadbk] [micxp_title] 置换的数算 重复置换 抽象代数 符号 特殊置换 计算理论中的置换 置换图 使用计算机 试算表语法 演算范例 参考资料 参考文献 外部链接 [/micxp_title] [#] 此节使用置换的传统定义。从${\displaystyle n}$个相异元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素的排列数量为：

${\displaystyle P_k^n=\frac{n!}{(n-k)!}}$

其中P意为Permutation（排列），!表示阶乘运算。 以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为：

${\displaystyle P_3^8=\frac{8!}{(8-3)!}=336}$

因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：

${\displaystyle P=\frac{1}{336}=0.00298}$

不过，中国大陆的教科书则是把从n取k的情况记作${\displaystyle P_n^k}$或${\displaystyle A_n^k}$（A代表Arrangement，即排列）。 [##] 上面的例子是建立在取出元素不重复出现状况。 从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素可以重复出现，这排列数量为：

${\displaystyle U_k^n=n^k}$[2]

以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为：

${\displaystyle U_4^{10}={10}^4=10000}$

这时的一次性添入中奖的概率就应该是：

${\displaystyle P=\frac{1}{10000}=0.0001}$

[###] 在集合论与抽象代数等领域中，“置换”一词被保留为集合（通常是有限集）到自身的双射的一个称呼。例如对于从一到十的数字构成的集合，其置换将是从集合 ${\displaystyle \{1,\dots ,10\}}$ 到自身的双射。一个集合上的置换在函数合成运算下构成一个群，称为对称群或置换群。 [####] 更多资料：对称群 以下仅考虑有限集上的置换（视为双射），由于 ${\displaystyle n}$ 个元素的有限集可以一一对应到集合 ${\displaystyle \{1,\dots ,n\}}$，有限集的置换可以化约到形如 {1, ..., n} 的集合之置换。此时有两种表示法。 第一，利用矩阵符号将自然排序写在第一列，而将置换后的排序写在第二列。例如：

表示集合 {1,2,3,4,5} 上的置换 ${\displaystyle s:s(1)=2,s(2)=5,s(3)=4,s(4)=3,s(5)=1}$。 第二，借由置换的相继作用描述，这被称为“轮换分解”。分解方式如下：固定置换 ${\displaystyle s}$。对任一元素 ${\displaystyle x}$，由于集合有限而 ${\displaystyle s}$ 是双射，必存在正整数 ${\displaystyle N}$ 使得 ${\displaystyle s^N(x)=x}$，故可将置换 ${\displaystyle s}$ 对 ${\displaystyle x}$ 的相继作用表成 ${\displaystyle (xs(x)s^2(x)\cdots s^{m-1}(x))}$，其中 ${\displaystyle m}$ 是满足 ${\displaystyle s^m(x)=x}$ 的最小正整数。 称上述表法为 ${\displaystyle x}$ 在 ${\displaystyle s}$ 下的轮换， ${\displaystyle m}$ 称为轮换的长度。我们在此将轮换视作环状排列，例如

${\displaystyle (a_1{a}_2{a}_3\cdots a_m)}$ 与

${\displaystyle (a_m{a}_1{a}_2\cdots a_{m-1})}$

是同一个轮换。由此可知 ${\displaystyle x}$ 在 ${\displaystyle s}$ 下的轮换只决定于 ${\displaystyle x}$ 在 ${\displaystyle s}$ 作用下的轨道，于是，任两个元素 ${\displaystyle x,y}$ 或给出同一个轮换，或给出不交的轮换。 我们将轮换 ${\displaystyle (x_1\cdots x_m)}$ 理解为一类特殊的置换[3]：仅须定义置换 ${\displaystyle s}$ 为 ${\displaystyle s:x_1\mapsto x_2,\dots ,x_{m-1}\mapsto x_m,x_m\mapsto x_1}$，而在其它元素上定义为恒等映射。不交的轮换在函数合成的意义下可相交换。 因此我们可以将集合 {1, ..., n} 对一置换分解成不交轮换的合成，此分解若不计顺序则是唯一的。例如前一个例子的 ${\displaystyle s}$ 就对应到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。 [#####] 在上节的轮换表法中，长度等于二的轮换称为换位，这种轮换 ${\displaystyle (xy)}$ 不外是将元素 ${\displaystyle x,y}$ 交换，并保持其它元素不变。对称群可以由换位生成。 轮换长度为偶数之轮换称为偶轮换，反之则为奇轮换；由此可定义任一置换的奇偶性，并可证明：一个置换是偶置换的充要条件是它可以由偶数个换位生成。偶轮换在置换群中构成一个正规子群，称为交错群。 [######] 某些旧课本将置换视为变数值的赋值。在计算机科学中，这就是将值

1, 2, ..., n

赋予变数

x1, x2, ..., xn

的赋值运算子，并要求每个值只能赋予一个变数。 赋值/代入的差别表明函数式编程与指令式编程之差异。纯粹的函数式编程并不提供赋值机制。现今数学的惯例是将置换看作函数，其间运算看作函数合成，函数式编程也类似。就赋值语言的观点，一个代入是将给定的值“同时”重排，这是个有名的问题。 [#######] (2,5,1,4,3,6)的置换图 取一个无向图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 是描述每个置换中所取物件数的整数。 [##########]

#include 
using namespace std;
bool arrsame(int* arr, int len, int num) {
	int i;
	for (i = 0; i < len; i++)
		if (arr == num)
			break;
	return i != len;
}
bool next_perm(int* perm, const int k, const int n) {
	int i = k - 1;
	do
		perm++;
	while (arrsame(perm, i, perm) || (perm >= 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;
	do
		for (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))
			cout << perm + 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.

[#############]

• 许多排列组合问题，附详解。（英文）
• 置换及图论问题 （英文）

分类：

• 抽象代数
• 集合论基本概念
• 置换

[/micxp_threadbk]

排列（英语：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个对象的置换”。

[micxp_threadbk] [micxp_title] 置换的数算 重复置换 抽象代数 符号 特殊置换 计算理论中的置换 置换图 使用计算机 试算表语法 演算范例 参考资料 参考文献 外部链接 [/micxp_title] [#] 此节使用置换的传统定义。从${\displaystyle n}$个相异元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素的排列数量为：

${\displaystyle P_k^n=\frac{n!}{(n-k)!}}$

其中P意为Permutation（排列），!表示阶乘运算。 以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为：

${\displaystyle P_3^8=\frac{8!}{(8-3)!}=336}$

因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：

${\displaystyle P=\frac{1}{336}=0.00298}$

不过，中国大陆的教科书则是把从n取k的情况记作${\displaystyle P_n^k}$或${\displaystyle A_n^k}$（A代表Arrangement，即排列）。 [##] 上面的例子是建立在取出元素不重复出现状况。 从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素可以重复出现，这排列数量为：

${\displaystyle U_k^n=n^k}$[2]

以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为：

${\displaystyle U_4^{10}={10}^4=10000}$

这时的一次性添入中奖的概率就应该是：

${\displaystyle P=\frac{1}{10000}=0.0001}$

[###] 在集合论与抽象代数等领域中，“置换”一词被保留为集合（通常是有限集）到自身的双射的一个称呼。例如对于从一到十的数字构成的集合，其置换将是从集合 ${\displaystyle \{1,\dots ,10\}}$ 到自身的双射。一个集合上的置换在函数合成运算下构成一个群，称为对称群或置换群。 [####] 更多资料：对称群 以下仅考虑有限集上的置换（视为双射），由于 ${\displaystyle n}$ 个元素的有限集可以一一对应到集合 ${\displaystyle \{1,\dots ,n\}}$，有限集的置换可以化约到形如 {1, ..., n} 的集合之置换。此时有两种表示法。 第一，利用矩阵符号将自然排序写在第一列，而将置换后的排序写在第二列。例如：

表示集合 {1,2,3,4,5} 上的置换 ${\displaystyle s:s(1)=2,s(2)=5,s(3)=4,s(4)=3,s(5)=1}$。 第二，借由置换的相继作用描述，这被称为“轮换分解”。分解方式如下：固定置换 ${\displaystyle s}$。对任一元素 ${\displaystyle x}$，由于集合有限而 ${\displaystyle s}$ 是双射，必存在正整数 ${\displaystyle N}$ 使得 ${\displaystyle s^N(x)=x}$，故可将置换 ${\displaystyle s}$ 对 ${\displaystyle x}$ 的相继作用表成 ${\displaystyle (xs(x)s^2(x)\cdots s^{m-1}(x))}$，其中 ${\displaystyle m}$ 是满足 ${\displaystyle s^m(x)=x}$ 的最小正整数。 称上述表法为 ${\displaystyle x}$ 在 ${\displaystyle s}$ 下的轮换， ${\displaystyle m}$ 称为轮换的长度。我们在此将轮换视作环状排列，例如

${\displaystyle (a_1{a}_2{a}_3\cdots a_m)}$ 与

${\displaystyle (a_m{a}_1{a}_2\cdots a_{m-1})}$

是同一个轮换。由此可知 ${\displaystyle x}$ 在 ${\displaystyle s}$ 下的轮换只决定于 ${\displaystyle x}$ 在 ${\displaystyle s}$ 作用下的轨道，于是，任两个元素 ${\displaystyle x,y}$ 或给出同一个轮换，或给出不交的轮换。 我们将轮换 ${\displaystyle (x_1\cdots x_m)}$ 理解为一类特殊的置换[3]：仅须定义置换 ${\displaystyle s}$ 为 ${\displaystyle s:x_1\mapsto x_2,\dots ,x_{m-1}\mapsto x_m,x_m\mapsto x_1}$，而在其它元素上定义为恒等映射。不交的轮换在函数合成的意义下可相交换。 因此我们可以将集合 {1, ..., n} 对一置换分解成不交轮换的合成，此分解若不计顺序则是唯一的。例如前一个例子的 ${\displaystyle s}$ 就对应到 (1 2 5) (3 4) 或 (3 4) (1 2 5)。 [#####] 在上节的轮换表法中，长度等于二的轮换称为换位，这种轮换 ${\displaystyle (xy)}$ 不外是将元素 ${\displaystyle x,y}$ 交换，并保持其它元素不变。对称群可以由换位生成。 轮换长度为偶数之轮换称为偶轮换，反之则为奇轮换；由此可定义任一置换的奇偶性，并可证明：一个置换是偶置换的充要条件是它可以由偶数个换位生成。偶轮换在置换群中构成一个正规子群，称为交错群。 [######] 某些旧课本将置换视为变数值的赋值。在计算机科学中，这就是将值

1, 2, ..., n

赋予变数

x1, x2, ..., xn

的赋值运算子，并要求每个值只能赋予一个变数。 赋值/代入的差别表明函数式编程与指令式编程之差异。纯粹的函数式编程并不提供赋值机制。现今数学的惯例是将置换看作函数，其间运算看作函数合成，函数式编程也类似。就赋值语言的观点，一个代入是将给定的值“同时”重排，这是个有名的问题。 [#######] (2,5,1,4,3,6)的置换图 取一个无向图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 是描述每个置换中所取物件数的整数。 [##########]

#include 
using namespace std;
bool arrsame(int* arr, int len, int num) {
	int i;
	for (i = 0; i < len; i++)
		if (arr == num)
			break;
	return i != len;
}
bool next_perm(int* perm, const int k, const int n) {
	int i = k - 1;
	do
		perm++;
	while (arrsame(perm, i, perm) || (perm >= 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;
	do
		for (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))
			cout << perm + 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.

[#############]

• 许多排列组合问题，附详解。（英文）
• 置换及图论问题 （英文）

分类：

• 抽象代数
• 集合论基本概念
• 置换

[/micxp_threadbk]