排列

排列(英语:Permutation)是将相异对象或符号根据确定的顺序重排。每个顺序都称作一个排列[注 1]。例如,从一到六的数字有720种排列,对应于由这些数字组成的所有不重复亦不阙漏的序列,例如"4, 5, 6, 1, 2, 3" 与1, 3, 5, 2, 4, 6

P(3,3)=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

的赋值运算子,并要求每个值只能赋予一个变量。

赋值/代入的差别表明函数式编程指令式编程之差异。纯粹的函数式编程并不提供赋值机制。现今数学的惯例是将排列看作函数,其间运算看作函数合成,函数式编程也类似。就赋值语言的观点,一个代入是将给定的值“同时”重排,这是个有名的问题。

排列图

 
(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 是描述每个排列中所取对象数的整数。

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

注释

  1. ^ 对于不排序的情形,请见条目组合
  2. ^ 可递置换

参考文献

  1. ^ 組合數學 ─算法與分析─. 九章出版社. : 29.  OCLC:44527392