思维之海

——在云端,寻找我的星匙。

组合数学

组合数学(Combinatorics)是什么?“数数”。根据组合数学 - 维基百科,组合数学,亦称组合论、组合学,数学的一个分支,亦和离散数学的排列组合研究,所研究的是计数的技巧。总之,组合数学是一门研究离散对象的数学科学。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。幻方是最早被探索的组合数学问题,除此之外,还有十四巧板、杨辉三角……,在四色问题的证明上,引发了一个新领域:机器证明。从最小支撑树到最小斯坦纳树,到斯坦纳比猜想……从无尺度网络、六度分离到小世界网络原理、埃尔德什数。组合数学的影子潜入了各个角落……

莱布尼兹《论组合的艺术》:一切推理和发现,不管是否用语言描述,都能归结为如数,字,声,色这些元素经过某种组合的有序集合。(书中首次使用了组合论 / Combinatorics 这一词)

References

课程:《组合数学》,马昱春

今年的OJ环节没了,但可以自己联系

额外限选题目(1-3人):人工智能、计算理论、金融。【以Paper/代码评价】

组合数学(第5版),Introductory Combinatorics

组合数学(第4/5版),卢开澄,推荐第5版

Applied Combinatorics by Roberts, F.S.

组合数学PPT

教学日历:

简介

组合数学的三大问题

  • 存在(existence problem)
    • 是否存在合理的解?
  • 计数(counting problem)
    • 有多少种解的可能?
  • 优化(optimization problem)
    • 依照某种标准,所有解中那个是最优的?

组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。

相比较而言,离散数学(Discrete mathematics)是数学的几个分支的总称,以研究离散量的结构和相互间的关系为主要目标,其研究对象一般是有限个或可数无穷个元素;因此它充分描述了计算机科学离散性的特点。离散数学通常研究的领域包括:数理逻辑、集合论、关系论、函数论、组合学、代数系统与图论。

组合数学经常使用的方法并不高深复杂。

  • 计数时的合理分类
  • 组合模型的转换

四色猜想

猜想:一张地图,用一种颜色对一个地区着色,那么一共只需要四种颜色就能保证每两个相邻的地区颜色不同。

1852年,刚从伦敦大学毕业的Francis Guthrie提出了四色猜想。
1878年著名的英国数学家Cayley向数学界征求解答。
此后数学家 Heawood 花费了毕生的精力致力于四色研究,于1890年证明了五色定理(每个平面图都是5顶点可着色的)。
直到1976年6月,美国数学家 K. Appel与 W. Haken,在3台不同的电子计算机上,用了1200小时,才终于完成了“四色猜想”的证明,从而使“四色猜想”成为了四色定理

四色猜想的证明,引入了机器证明这门学科。四色定理是第一个主要由电脑证明的著名数学定理。

并且,如何证明一个机器证明的正确性, 也被拿来研究。

机器证明在某种意义上让人类迈向了一个更复杂、怪异的广阔世界……

最小斯坦纳树

斯坦纳( Steiner )最小树是可以在给定的点之外再增加若干个点(称为 斯坦纳点),然后将所有这些点连起来,使得边权之和最小。

如果不允许增加任何额外的点作为网络的顶点,这种最短网络称为最小生成树。

Pollak-Gilbert猜想

斯坦纳比猜想:平面上任意n点集,斯坦纳最小树长与最小生成树之长的比值的最小值是 $\cfrac{\sqrt3}{2}$。

这个猜想目前还未得到完整的证明。

无尺度网络 / 小世界网络

“6度分离” —对每个人来说,平均大约只需要通过6个人就能将信寄到目的地。

在1999年,Barab´asi et al.发现在因特网上,任意两个网页间的链接即网页之间的“距离”平均为18.59 。从任意一个网页出发, 原则上可以通过不超过19次链接到达互联网中的任何网页。 (Nature 401, 1999)

埃尔德什数

保罗·埃尔德什就是随机图理论的开创者之一。与他一起发表过论文的学者的“埃尔德什数”是1,与这些学者合作发表过论文的学者的“埃尔德什数”是2,以此类推。美国数学会的数据库中记录的超过40万名数学家们的“埃尔德什数”平均是4.65,最大的是13。

马昱春老师的埃尔德什数是3~~~

幻方

一个连续整数集在棋盘上放置,并满足约束:横竖、对角之和相同。棋盘的长宽称为幻方的阶数。

二阶幻方不存在。(约束太强)

大约30年前德国数学家L. Bieberbach证明了:「对于任意大于等于3的数n,都存在一个n阶的幻方。

当然,除了和相同以外,还有诸如幻积、幻差、幻商、平方幻和等方式来约束一个幻方……

个性的幻方也是表达心意不错的选择QAQ

幻方的构造

根据构造方法的不同,幻方可以分三类:奇数阶幻方、 4M阶幻方和4M+2阶幻方。


对于奇数阶幻方:从1开始(幻方的中间最上角)斜循环遍历。

偶数阶幻方需要分类讨论为4m+2和4m+4。可以自行搜索。

幻方的计数

3阶幻方只有一个(旋转等价)。

试问:n阶普通幻方的个数?

实际上到目前为止连6阶幻方的计数都还没有完全解决。。

  • 弗兰尼克尔(Bernard Frenicle de Bessy)在1693 年得出结论,认为4 阶幻方总共有 880 个基本形式,通过旋转与镜面反射,总共有 7040 个幻方。
  • 对于 5 阶幻方总数的估计, 理查德• 许洛泼尔(Richard Schroeppel)利用计算机编程运算得出结论,认为 5 阶幻方的基本形式有275305224 个,即 2 亿 7 千 5 百多万个。
  • 对 6 阶幻方,皮恩(K.Pinn) 和维茨考夫斯基(C. Wieczerkowski)利用蒙特卡洛模拟和统计学方法,
    得出一个大概的数值估计,其数量在 $1.774310\times 10^{19}$ 至 $1.776610\times 10^{19}$ 之间。

由此可见,其他阶幻方的数量级,将达到难以置信的程度。

事实上这其中的原因可以由幻方的定义来解释,因为幻方的约束只有横、纵和对角线。对于这三种约束来说,随着幻方的阶数的增加,横、纵约束对每个元素的平摊约束强度为$O(\cfrac{1}{n})$,而对角线约束对每个元素的平摊约束强度为$O(\cfrac{1}{n^2})$。显然随着阶数的增加,幻方定义所保证的约束变得越来越弱,因此自由也越来越大。

幻方的应用

幻方可以与密码学结合。。。

用幻方表达心意

如何在幻方中绘制某种特定的图案?

比如,某个人的名字?或者和为520?

绘制图案可以从1、2、3……依次连线来得到。但是想要特定的图案确实会存在一定的困难。

和为520其实有一个较为简单的解决方案,只要加上一定的偏置。当然,还需要实际测试。。

这是一个比较困难的问题。可以暂时留待思考。

安卓九宫格

计算安卓手机九宫格密码的所有可能的密码种数。

模拟法

求解思路就是模拟,从每个点出发,然后对下一个步骤点进行决策,如果这个决策是合法的,就递归模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
a = [[False for i in range(3)] for i in range(3)]
ret = 0

def dfs(p, depth, required_depth):
a[ p[0] ][ p[1] ] = True
depth += 1
global ret

if depth == required_depth: # 达到密码长度
a[ p[0] ][ p[1] ] = False
ret += 1 # 统计结果
return
else:
for i in range(-2, 3):
for j in range(-2, 3):
if i == 0 and j == 0:
pass
else:
# 若合法的话
if p[0] + i <= 2 and p[0] + i >= 0 and p[1] + j <= 2 and p[1] + j >= 0:
# 开始
if (abs(i) == 2 or abs(j) == 2) and (abs(i) + abs(j) != 3):
m = int(i / 2) if abs(i) == 2 else i
n = int(j / 2) if abs(j) == 2 else j
if a[ p[0] + m ][ p[1] + n ] == True:
if a[ p[0] + i ][ p[1] + j ] == False:
dfs([p[0] + i, p[1] + j], depth, required_depth)
else:
if a[ p[0] + i ][ p[1] + j ] == False:
dfs([p[0] + i, p[1] + j], depth, required_depth)


a[ p[0] ][ p[1] ] = False


if __name__ == '__main__':
for k in range(4, 10):
tmp = ret
for i in range(3):
for j in range(3):
dfs([i,j], 0, k)
print(k, "位:", ret - tmp)
print(ret)

输出结果:

1
2
3
4
5
6
7
8
4 位: 1624
5 位: 7152
6 位: 26016
7 位: 72912
8 位: 140704
9 位: 140704
389112
[Finished in 5.0s]

运行:

补集法

求解思路就是枚举出所有的数字排列(有序,代表连接手势的顺序),然后去掉那些不符合要求的排列。

这些排列可以通过正则匹配的方式识别并排除。

比如这些模式在有效序列中是非法的:13314664799717712882399319913773。需要一一排除。

注意到,如果中点提前被经过了,那么某些序列可能会变合法。比如,13如果是..4..13的形式,则变成一种合法的模式。如下图所示:

这样,我们需要的正则表达式如下:

  • ([^2]*)(13|31)
  • ([^4]*)(17|71)
  • ([^6]*)(39|93)
  • ([^8]*)(79|97)
  • ([^5]*)(46|64|28|82|19|91|37|73)

这些正则表达式将匹配出所有非法的序列。现在我们只需要生成所有可能的序列就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 补集法
# 求解思路就是枚举出所有的数字排列(有序,代表连接手势的顺序),然后去掉那些不符合要求的排列。
# 这些排列可以通过正则匹配的方式识别并排除。
import re
ret = 0
illegal_pattern = '(([^2]*)(13|31))|(([^4]*)(17|71))|(([^6]*)(39|93))|(([^8]*)(79|97))|(([^5]*)(46|64|28|82|19|91|37|73))'

def solve(string, depth, k):
global ret
global illegal_pattern
if depth == k:
illegal_match = re.match(illegal_pattern, string)
ret += (illegal_match == None) # 序列合法则统计
return
for i in range(1, 10):
if str(i) not in string:
solve(string + str(i), depth + 1, k)

if __name__ == '__main__':
for k in range(4, 10):
tmp = ret
solve("", 0, k)
print(k, "位:", ret - tmp)
print(ret)

输出结果:

1
2
3
4
5
6
7
8
4 位: 1624
5 位: 7152
6 位: 26016
7 位: 72912
8 位: 140704
9 位: 140704
389112
[Finished in 4.3s]

运行:

数学法

似乎按照2017年是通过内部结构来分类计算的,想想就很麻烦。。还是先算了吧。。

排列组合

无重复、无遗漏。

一 一对应。

加法法则 & 乘法法则

分类计数和分步计数。

加法法则

加法法则(The Sum Rule):设事件 A 有 m 种产生方式,事件 B 有 n 种产生方式,则事件 A 或 B 之一有 m+n 种产生方式。

乘法法则

乘法法则(The Product Rule):设事件 A 有 m 种产生方式,事件 B 有 n 种产生方式,则事件 A 与 B 有 m · n 种产生方式。

排列

排列(Permutation):从 n 个不同的元素中,取 r 个不重复的元素,按次序排列,称为从 n 个中取 r 个的无重排列。排列的个数用 $P(n,r)$ 表示,或者 $P_n^r$ 。当 r=n 时称为全排列。一般不说可重即无重。

圆排列

圆排列:从 n 个中取 r 个的圆排列的排列数为 $P(n,r)/r $,$2≤r≤n$。

项链排列

项链排列:在圆排列的基础上,正面向上和反面向上两种方式放置各个数是同一个排列。

引入了镜像对称。

多重集

多重集:元素可以多次出现的集合。$q_i =0,1, …,∞$ 表示元素 $a_i$ 可以出现的次数,含有 $n$ 个不同元素的多重集可以记为 $\{q_1 ·a_1 , q_2 ·a_2 …,q_t ·a_t \}$。

多重全排列

多重全排列:($r_1+r_2+…+r_t=\sum r_{i}=n$)

  • $r_1$ 个元素 1,$r2$ 个元素 2,……,$r_t$ 个元素 t,共计 n 个元素进行排列,记为 $P(n;r_1,r_2,…,r_t)$。

多重排列

多重排列:即从多重集中选取若干个元素进行排列。

多重集S = {3·a, 2·b, 4·c},取8个元素的排列有多少?
– {2·a, 2·b, 4·c}: 8!/(2!2!4!)=420
– {3·a, 1·b, 4·c}:8!/(3!1!4!)=280
– {3·a, 2·b, 3·c}:8!/(3!2!3!)=560
• Total: 420+280+560 = 1260

可重排列

可重排列:即从无限多重集(多重集中每个元素的个数无限)中选取若干个元素进行排列。

例:26 个英文字母能组成多少 4 位数的字符串,其中每位字母都不相同且 b 和 d 不相邻 ?

$P(26, 4) – C(24, 2)3!2$

组合

组合(Combination):从 n 个不同元素中取 r 个不重复的元素组成一个子集,而不考虑其元素的顺序,称为从 n 个中取 r 个的无重组合。组合的个数用 $C(n,r)$ 表示或者 $C_n^r$。

https://vel.life/算法手册/#组合数学

二项式组合

二项式组合

二项式推广

可重组合

可重组合模型:取r个无标志的球,n个有区别的盒子,每个盒子允许放多于一个球。

可重组合:$n$ 个类型元素的多重集,每个类的元素个数无限,从中取 $r$ 个元素。

无重组合

无重组合的模型:n个球是有区别的,r个盒子是无区别的,取r个球放入盒子,每个盒子一个球

无重组合就是普通的组合模型。

index法计算可重组合

从可重组合构造无重组合。

先排序,再令所有可重元素的标号加上对应的indexa[i] += i ),即构造了要给无重组合。

编号 + 位置号,构造无重序列

隔板法计算可重组合

同理,可以得到 $\bar C(n,r) = C(n+r-1,r)$。

例1:线性方程 $x_1 +x_2 …+x_n =b$ 的非负整数解的个数是 $C(n+b-1,b)$。

例2: $(x+y+z)^ 4$ 有多少项? $A={x,y,z}$ 三个元素中取r=4个做可重组合。

不相邻组合

不相邻的组合是指从 $A=\{1,2,…n\}$ 中取 $r$ 个不相邻的数进行组合(不可重),即不存在相邻的两个数 $j, j+1$ 的组合。

这个证明同样可以利用index法完成( a[i] -= i )。将不相邻组合转化为无重组合。

也可以将未选取的数列成一排,选取的不相邻组合其实就是往中间插空(一共 $n-r+1$ 个空)。

广义不相邻组合 Kaplansky定理

从 $A=\{1,2,…n\}$ 中取 $r$ 个不相邻的数进行组合(不可重),且任意两个数之间至少间隔 $m$ 个数。

模型

放球模型初步

n 个不同的球中,取出 r 个,放入 r 个不同的盒子里,每盒1个

n 个不同的球中,取出 r 个,放入 r 个相同的盒子里,每盒1个

常用方法:

  • 下标法
  • 隔板法
  • 模拟法
  • index法

格路模型

简单路径计数

从 $(0,0)$ 点出发沿 x 轴或 y 轴的正方向每步走一个单位,最终走到 $(m,n)$ 点,有多少条路径?

设 $c≥a,d≥b$,则由 $(a,b)$ 到 $(c,d)$ 的简单格路数为 $C((c-a)+(d-b),c-a)$。

若某些点不可经过/含有额外约束,则可以采用动态规划求解之。

镜像格路法

在格路要求的基础上若设 $m<n$,求 $(0,1)$ 点到 $(m,n)$ 点不接触对角线 $x=y$ 的格路的数目(“接触”包括“穿过”)

凯莱定理

Cayley定理:$n$ 个有标号的顶点,可以组成不同的树的数目等于 $n^{n-2}$ 。

用 $n-1$ 条边将 $1,2,3…n$ 点连接起来的连通图的数目为 $n^{n-2}$ 。

模型转换

观察发现凯莱定理中的组合数是可重排列的形式。想到将树形结构转化为序列结构。

不妨构造一个从序列到树的一一对应(双射)。

树 $\longrightarrow$ 序列

树 $\longrightarrow$ 序列:

  • 删叶子:逐个摘去标号最小的叶子
  • 每次记录该叶子的相连节点编号放入序列
序列 $\longrightarrow$ 树

序列 $\longrightarrow$ 树:

  • 一个典型结论
  • 每次寻找不在序列中且序号最小的节点,作为序列开头元素的连接点
双射证明
  • 由一棵n个顶点的树可得到一个长度为n - 2的序列,且不同的树对应的序列不同,因此 $| T |≤n^{n-2}$。

  • 反之,由一个长度为n - 2的序列(每个元素为1~ n 的一个整数),可得到一棵树,且不同的序列对应的树是不同的,因此 $n^{n-2} ≤| T |$。

综上,$| T | =n^{n-2}$。

组合恒等式

基本组合恒等式

r个元素被取走构成一个组合,剩下的n-r个也构成了一个组合,由此建立C(n, r)与C(n, n-r)的一个一一对应。

组合递推式

其中组合数的递推公式,可以用格路模型证明。

终极递推式

选取独立性

① 选班委,再选核心班委
② 选核心班委,再选非核心班委

两种选法都无遗漏,无重复地给出可能的方案,应该相等。

二项式定理

$[1,m]$ 的每个元素面对一个组合,要么取,要么不取,所有方案数为 $2^m$ 个方案。

二项式定理2

在$(x+y)^ n =C(n,0)x^n + C(n,1)x^{n-1} y+ …+ C(n,n)y^n$ 中,令 $x=1,y=-1$,得上式。

Chu-Vandermonde恒等式

从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类。

或者利用格路法证明:

黑板上的排列组合

用六种不同颜色涂一正方体,每一面一色,且每面颜色不同,会有多少种涂法?

注意到六种颜色必须同时用到。

注意这里仍然存在对称性和群论的影子。

注意上面选择第二面涂色的方式,左边一种会导致4种旋转后等价的结果,右侧则会导致第三面涂色时出现4种旋转等价。

故,总计 = 1 * (1 * 4! + 1 * 1 * 3!) = 24 + 6 = 30 种。

如果可以不同面同色的话,答案怎么计算呢?(还是用六种不同颜色)

可以考虑分类讨论。首先我们可以确定可能的使用颜色种数的范围在 [3, 6] 之间。

  • 6种颜色
    • 由上个问题,我们已经知道
    • 30种
  • 5种颜色
    • 无非是将6色模型中某个面的对面换成同一种颜色,根据对称性可知种数相当
    • C(6, 5) * 30 = 180种
  • 4种颜色
    • 无非是将5色模型中某个颜色只出现了一次的面的对面换成同一种颜色,但是此时会出现重复
    • 因此可以采用涂色的方法,先选涂2种颜色形成一个环带,然后其实就已经陷入对称了
    • C(6, 4) * C(4, 2) * 1 * 1 = 15 * 12 = 180种
  • 3种颜色
    • 高度对称
    • C(6, 3) = 20种

故,总计为 30 + 180 + 180 + 20 = 410 种

全排列

Stirling数

右侧的近似幂公式可以用快速幂的方式计算。

递归法

递归的思路是通过 $n-1$ 的排列来生成 $n$ 的排列。

例:求 {1 2 3} 的全排列。

先得到 {1 2} 的全排列为:1 2,2 1。

生成 {1 2 3} 的全排列:3 1 3 2 33 2 3 1 3。依次插入 3,共计6个全排列。

字典序法

字典序法要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。

  • 从右向左扫描都是增的,就不存在下一个;
  • 要找第一次出现下降的位置 a Ab
    • $j=max\{i\;|\;p_i<p_{i+1}\}$
  • a 与后面比 a 大的最小元素 b 交换;(【二分】)
    • $ k=max\{i\;|\;p_i > p_j \}$
  • b 后缀重排成升序
    • 因为之前操作的性质,这里其实只需要【倒转】后缀即可

序号

(字典)序号:给定排列在字典序中的排名。(从 0 开始计序)

例:计算给定排列 839647521 的序号。

7×8! +2×7! +6×6! +4×5! +2×4! +3×3! +2×2! +1×1! = 297191(【康托展开】)

839647521 的序号是 297191,表明 839647521 前面有 297191 个排列。

字典序中介数

康托展开

(字典序)中介数:记录当前数位数字右边比当前数字小的数字的个数。(从字典序推导而来)

中介数、序号和排列之间是一一对应的关系。

构造中介数

例:计算给定排列 839647521 的中介数。

7×8! +2×7! +6×6! +4×5! +2×4! +3×3! +2×2! +1×1! = 297191

抽取出递增进位制的系数,得到中介数:72642321

中介数的位数比排列少一位。

由中介数推出排列

搬运了一下后文练习题中的求解内容~~

8位排列,中介数为:7000201,反推排列。(由中介数推出排列的算法,见PPT的C1-4)

  • 7+1=8,P1=8
  • 0+1=1,P2=1
  • 0+1=1
    • 1已出现,1+1=2,P3=2【数字“已出现”代表着不能采用,所以顺延】
  • 0+1=1
    • 1已出现,1+1=2
    • 2已出现,2+1=3,P4=3
  • 2+1=3
    • 123已出现,3+3=6,P5=6
  • 0+1=1
    • 1已出现,1+1=2
    • 2已出现,2+1=3
    • 3已出现,3+1=4,P6=4
  • 1+1=2
    • 12已出现,2+2=4
    • 34已出现,4+2=6
    • 6已出现,6+1=7,P7=7
  • P8=5

综上,得到排列为 81236475

序号转化为中介数

不断按位除余即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def p(n):
return p(n-1)*n if n >= 2 else 1

def idx2inter(idx):
base = 9
perm = ""
while int(idx / p(base)) == 0:
base -= 1
while base > 0:
perm += str(int(idx / p(base)))
idx = idx % p(base)
base -= 1
print("转换为中介数", perm)
print("----------------")
return int(perm)

递增进位制法

“原排列”→“原中介数”→“新中介数”→“新排列”

递增进位制数

递增进位制:指数字的进制随着数字位置的不同递增。

递增进位制数 ($a_9$ $a_8$ $a_7$ $a_6$ $a_5$ $a_4$ $a_3$ $a_2$ )$↑$ 为:

  • a_9 * 8! + a_8 * 7! + ….+ a_3 * 2! + a_2 * 1! = 序号
  • = a_9 * 8) + a_8) * 7 + ….+ a_3) * 2 + a_2) * 1!

87654321对应的十进制序号为462879(即 9! - 1)。

(改进的)递增进位制数:记录数字右边比当前数字小的数字的个数

  • $a_i$:i 的右边比 i 小的数字的个数

利用改进的递增进位制数生成排列的方法,被称为递增进位制法


例:839647521,求字典序中介数和递增进位制数。

字典序中介数72642321

  • 含义:第9位的右边有7个更小的数,第8位的右边有2个更小的数,第7位的右边有6个更小的数……
    • 839647521

递增进位制数67342221

  • 含义:数字9的右边有6个更小的数,数字8的右边有7个更小的数,数字7的右边有3个更小的数……
    • 839647521

递减进位制法

递减进位制:指数字的进制随着数字位置的不同递减。

递减进位制数

递减进位制数:把递增进位制数翻转,就得到递减进位制数。

递减进位制数 ($a_2$ $a_3$ $a_4$ $a_5$ $a_6$ $a_7$ $a_8$ $a_9$ )$\downarrow$。

最低位不一定是9。比如,如果是A-Z的排列,那么最低位将是逢26进1。

特点:进位不频繁;中介数不进位的情况下,只要把最大数和左边相邻数对换一下。

递减进位制数也可以转化为十进制,从而得到一个对应的序号,但这个序号的意义和字典序序号、递增进位制数序号是不同的。每种方法所得到的十进制序号,可以用来规定相应的排列的秩。


例:839647521,求递减进位制数。

递增进位制数67342221

故反转得,递减进位制数12224376

邻位对换法

可移动数

可移动数(mobile int.):每个数字具有方向,若该方向当前指向一个相邻更小数,那么称其为可移动的数。

k is called mobile if its arrow points to a smaller integer.

序列两端有默认的无穷大固定哨兵。

SJT算法

SJT算法(Steinhaus–Johnson–Trotter algorithm)的邻域性特别好,相邻排列之间的变动总是保证只有一次相邻交换。

SJT将递归算法的生成过程描述为每个数字的带有方向的 穿梭 行为。

SJT算法:Begin with $\overleftarrow{1} \overleftarrow{2} \overleftarrow{3} \overleftarrow{4}$,While there exists a mobile integer, do

  1. find the largest mobile integer $m$ . (例:$\overleftarrow{1} \overleftarrow{2} \overleftarrow{3} {\color{red}{\overleftarrow{4 } } }$)
  2. switch $m$ and the adjacent integer its arrow points to.(例:$\overleftarrow{1} \overleftarrow{2} {\color{blue}{\overleftarrow{3} } } {\color{red}{\overleftarrow{4 } } }\;\longrightarrow\; \overleftarrow{1} \overleftarrow{2} {\color{red}{\overleftarrow{4 } } } {\color{blue}{\overleftarrow{3} } } $)
  3. switch the direction of all integers $p$ with $p>m$ .(例:$\overleftarrow{1} \overleftarrow{2} {\color{red}{\overleftarrow{4 } } } \overleftarrow{3}$)

邻位中介数

邻位中介数:在递减进位制数的基础上,记录数字方向背后比当前数字小的数字的个数

利用中介数每一位的奇偶性来记录方向。


计算邻位中介数

例:839647521,求邻位中介数。

1的方向默认向左,

  • $83964752{\color{red}{\overleftarrow{1} } }$

2的方向一定向左

  • $8396475{\color{red}{\overleftarrow{2} } } {\color{blue}{\overleftarrow{1} } }$
    • 背向2的方向中比2小的数字有1个,b2=1

3的方向由b2为奇可以断定向右,【奇向右、偶向左

  • $8{\color{red}{\overrightarrow{3} } }96475\overleftarrow{2} \overleftarrow{1}$【i 为奇数,其方向性决定于 $b_{i-1}$ 的奇偶性
    • 背向3的方向中比3小的数字有0个,b3=0

4的方向由b2+b3为奇可以断定向右,

  • $8{\color{blue}{\overrightarrow{3} } }96{\color{red}{\overrightarrow{4} } }75\overleftarrow{2} \overleftarrow{1}$【i 为偶数,其方向性决定于 $b_{i-1} + b_{i-2}$ 的奇偶性
    • 背向4的方向中比4小的数字有1个,b4=1

5的方向由b4为奇可以断定为右,

  • $8{\color{blue}{\overrightarrow{3} } }96{\color{blue}{\overrightarrow{4} } }7{\color{red}{\overrightarrow{5} } }\overleftarrow{2} \overleftarrow{1}$
    • 背向5的方向中比5小的数字有2个,b5=2

6的方向由b4+b5为奇可以断定向右,

  • $8{\color{blue}{\overrightarrow{3} } }9{\color{red}{\overrightarrow{6} } }\overrightarrow{4}7\overrightarrow{5}\overleftarrow{2} \overleftarrow{1}$
    • 背向6的方向中比6小的数字有1个,b6=1

7的方向由b6为奇可以断定向右,

  • $8{\color{blue}{\overrightarrow{3} } }9{\color{blue}{\overrightarrow{6} } }{\color{blue}{\overrightarrow{4} } } {\color{red}{\overrightarrow{7} } }\overrightarrow{5}\overleftarrow{2} \overleftarrow{1}$
    • 背向7的方向中比7小的数字有3个,b7=3

8的方向由b6+b7为偶可以断定向左,

  • ${\color{red}{\overleftarrow{8} } }{\color{blue}{\overrightarrow{3} } }9{\color{blue}{\overrightarrow{6}\overrightarrow{4}\overrightarrow{7}\overrightarrow{5}\overleftarrow{2} \overleftarrow{1} } }$
    • 背向8的方向中比8小的数字有7个,b8=7

9的方向由b8为奇可以断定向右,

  • ${\color{blue}{\overleftarrow{8}\overrightarrow{3} } } {\color{red}{\overrightarrow{9} } }\overrightarrow{6}\overrightarrow{4}\overrightarrow{7}\overrightarrow{5}\overleftarrow{2} \overleftarrow{1}$
    • 背向9的方向中比9小的数字有2个,b9=2

综上,得到邻位中介数为:10121372($\downarrow$)

利用邻位中介数求排列

例:已知邻位中介数10121372($\downarrow$) ,求排列。

9:

  • b8=7奇 → 9向右
  • b9=2,向右第3个空
  • $\bigsqcup\;\bigsqcup\;{\color{red}{9} }\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup$

8:

  • b6+b7=1+3=4偶 → 8向左
  • b8=7,向左第8个空
  • ${\color{red}{8} }\;\bigsqcup\;9\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup$

7:

  • b6=1奇 → 7向右,
  • b7=3,向右第4个空
  • $8\;\bigsqcup\;9\;\bigsqcup\;\bigsqcup\;{\color{red}{7} }\;\bigsqcup\;\bigsqcup\;\bigsqcup$

6:

  • b4+b5=1+2=3奇 → 6向右
  • b6=1,向右第2个空
  • $8\;\bigsqcup\;9\;{\color{red}{6} }\;\bigsqcup\;7\;\bigsqcup\;\bigsqcup\;\bigsqcup$

5:

  • b4=1奇 → 5向右
  • b5=2,向右第3个空
  • $8\;\bigsqcup\;9\;6\;\bigsqcup\;7\;{\color{red}{5} }\;\bigsqcup\;\bigsqcup$

4:

  • b2+b3=1+0=1 奇 → 4向右
  • b4=1,向右第2个空
  • $8\;\bigsqcup\;9\;6\;{\color{red}{4} }\;7\;5\;\bigsqcup\;\bigsqcup$

3:

  • b2=1奇 → 3向右
  • b3=0,向右第1个空
  • $8\;{\color{red}{3} }\;9\;6\;4\;7\;5\;\bigsqcup\;\bigsqcup$

2:(2一定向左)

  • b2=1,向左第2个空
  • $8\;3\;9\;6\;4\;7\;5\;{\color{red}{2} }\;\bigsqcup$

综上,得到排列为:839647521

全排列练习题

按照课堂上介绍的四种全排列算法,分别求出 83674521 之前第2020个排列。

注:在进行手工步骤计算的同时,也借助了程序辅助验证

注:这里只有8个数字。

字典序法

首先计算出 83674521 的序号。

7×7! + 2×6! + 4×5! + 4×4! + 2×3! +2×2! + 1×1! = 37313

求之前第2020个排列的序号。(字典序按照序号排列)

37313 - 2020 = 35293

也可以直接用字典序中介数的形式相减:7244221($\uparrow$) - 244020($\uparrow$) = 7000201($\uparrow$)

反推字典序中介数。

  • 35293 / 7! = 735293 % 7! = 13
  • 13 / 6! = 0,13 % 6! = 13
  • 13 / 5! = 0,13 % 5! = 13
  • 13 / 4! = 0,13 % 4! = 13
  • 13 / 3! = 2,13 % 3! = 1
  • 1 / 2! = 0,1 % 2! = 1
  • 1 / 1! = 1

得到字典序中介数为: 7000201($\uparrow$)

反推排列。(由字典序中介数推出排列的算法,见PPT的C1-4)

  • 7+1=8,P1=8
  • 0+1=1,P2=1
  • 0+1=1
    • 1已出现,1+1=2,P3=2【数字“已出现”代表着不能采用,所以顺延】
  • 0+1=1
    • 1已出现,1+1=2
    • 2已出现,2+1=3,P4=3
  • 2+1=3
    • 123已出现,3+3=6,P5=6
  • 0+1=1
    • 1已出现,1+1=2
    • 2已出现,2+1=3
    • 3已出现,3+1=4,P6=4
  • 1+1=2
    • 12已出现,2+2=4
    • 34已出现,4+2=6
    • 6已出现,6+1=7,P7=7
  • P8=5

综上,得到排列为 81236475

递增进位制法

首先计算出83674521的递增进位制数。

根据定义,计算每个数字右侧更小元素的个数,得到递增进位制数:7442221($\uparrow$)。

计算之前第2020个排列的递增进位制数。

7442221($\uparrow$) - 2020(十)

  • = 7442221($\uparrow$) - 244020($\uparrow$)
  • = 7153201($\uparrow$)

反推排列。

由定义,易得所求排列为 86254173

递减进位制法

首先计算出83674521的递减进位制数。

由之前的结果,得递增进位制数:7442221($\uparrow$)。

反转,得到递减进位制数:1222447($\downarrow$)。

计算之前第2020个排列的递减进位制数。

1222447($\downarrow$) - 2020(十)

  • = 1224427($\downarrow$) -11004($\downarrow$)
  • = 1211443($\downarrow$)

反推排列。

反转,得到递增进位制数:3441121($\uparrow$)。

由定义,易得所求排列为 36728451

邻位对换法

首先计算出83674521的邻位中介数。

1的方向默认向左,

  • $8367452{\color{red}{\overleftarrow{1} } }$

2的方向一定向左

  • $836745{\color{red}{\overleftarrow{2} } } {\color{blue}{\overleftarrow{1} } }$
    • 背向2的方向中比2小的数字有1个,b2=1

3的方向由b2为奇可以断定向右,【奇向右、偶向左

  • $8{\color{red}{\overrightarrow{3} } }6745\overleftarrow{2} \overleftarrow{1}$【i 为奇数,其方向性决定于 $b_{i-1}$ 的奇偶性
    • 背向3的方向中比3小的数字有0个,b3=0

4的方向由b2+b3为奇可以断定向右,

  • $8{\color{blue}{\overrightarrow{3} } }67{\color{red}{\overrightarrow{4} } }5\overleftarrow{2} \overleftarrow{1}$【i 为偶数,其方向性决定于 $b_{i-1} + b_{i-2}$ 的奇偶性
    • 背向4的方向中比4小的数字有1个,b4=1

5的方向由b4为奇可以断定为右,

  • $8{\color{blue}{\overrightarrow{3} } }67{\color{blue}{\overrightarrow{4} } }{\color{red}{\overrightarrow{5} } }\overleftarrow{2} \overleftarrow{1}$
    • 背向5的方向中比5小的数字有2个,b5=2

6的方向由b4+b5为奇可以断定向右,

  • $8{\color{blue}{\overrightarrow{3} } }{\color{red}{\overrightarrow{6} } }7\overrightarrow{4}\overrightarrow{5}\overleftarrow{2} \overleftarrow{1}$
    • 背向6的方向中比6小的数字有1个,b6=1

7的方向由b6为奇可以断定向右,

  • $8{\color{blue}{\overrightarrow{3} } }{\color{blue}{\overrightarrow{6} }{\color{red}{\overrightarrow{7} } } }\overrightarrow{4} \overrightarrow{5}\overleftarrow{2} \overleftarrow{1}$
    • 背向7的方向中比7小的数字有2个,b7=2

8的方向由b6+b7为奇可以断定向右,

  • ${\color{red}{\overrightarrow{8} } }\overrightarrow{3}\overrightarrow{6}\overrightarrow{7}\overrightarrow{4}\overrightarrow{5}\overleftarrow{2} \overleftarrow{1}$
    • 背向8的方向中比8小的数字有0个,b8=0

综上,得到邻位中介数为:1012120($\downarrow$)

计算之前第2020个排列的邻位中介数。

1012120($\downarrow$) - 2020(十)

  • = 1012120($\downarrow$) -11004($\downarrow$)
  • = 1001114($\downarrow$)

反推排列。

8:

  • b6+b7=1+1=2 偶 → 8向左
  • b8=4,向左第5个空
  • $\bigsqcup\;\bigsqcup\;\bigsqcup\;{\color{red}{\overleftarrow{8} } }\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup$

7:

  • b6=1 奇 → 7向右,
  • b7=1,向右第2个空
  • $\bigsqcup\;{\color{red}{\overrightarrow{7} } }\;\bigsqcup\;\overleftarrow{8}\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup$

6:

  • b4+b5=0+1=1 奇 → 6向右
  • b6=1,向右第2个空
  • $\bigsqcup\;\overrightarrow{7}\;{\color{red}{\overrightarrow{6} } }\;\overleftarrow{8}\;\bigsqcup\;\bigsqcup\;\bigsqcup\;\bigsqcup$

5:

  • b4=0 偶 → 5向左
  • b5=1,向左第2个空
  • $\bigsqcup\;\overrightarrow{7}\;\overrightarrow{6}\;\overleftarrow{8}\;\bigsqcup\;\bigsqcup\;{\color{red}{\overleftarrow{5} } }\;\bigsqcup$

4:

  • b2+b3=1+0=1 奇 → 4向右
  • b4=0,向右第1个空
  • ${\color{red}{ \overrightarrow{4} } }\;\overrightarrow{7}\;\overrightarrow{6}\;\overleftarrow{8}\;\bigsqcup\;\bigsqcup\;\overleftarrow{5}\;\bigsqcup$

3:

  • b2=1 奇 → 3向右
  • b3=0,向右第1个空
  • $\overrightarrow{4} \;\overrightarrow{7}\;\overrightarrow{6}\;\overleftarrow{8}\;{\color{red}{\overrightarrow{3} } }\;\bigsqcup\;\overleftarrow{5}\;\bigsqcup$

2:(2一定向左)

  • b2=1,向左第2个空
  • $\overrightarrow{4} \;\overrightarrow{7}\;\overrightarrow{6}\;\overleftarrow{8}\;\overrightarrow{3}\;{\color{red}{\overleftarrow{2} } }\;\overleftarrow{5}\;\bigsqcup$

综上,得到排列为:47683251

验算结果:

辅助测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
def main():
index(83674521)
index(839647521)
index(839651247)
idx2upinter(37313)
idx2upinter(35293)
index(81236475)
idx2upinter(2020)
idx2downinter(2020)
# downinter2idx(4004)
# downinter2idx(1224427)

# print(7*p(8) + 2*p(7) + 6*p(6) + 4*p(5) + 2*p(4) + 3*p(3) + 2*p(2) + 1*p(1))
# print(7*p(7) + 2*p(6) + 4*p(5) + 4*p(4) + 2*p(3) + 2*p(2) + 1*p(1))
# print(7*p(7) + 2*p(6) + 4*p(5) + 4*p(4) + 2*p(3) + 2*p(2) + 1*p(1) -2020)

def p(n):
return p(n-1)*n if n >= 2 else 1

def index(n):
print("输入:", n)
n = str(n)
im = ""
for i in range(0, len(n) - 1):
t = 0
for j in range(i+1, len(n)):
if int(n[i]) > int(n[j]):
t += 1
im += str(t)
print("中介数:", im)
im_rev = im[::-1]
index = 0
for i in range(len(im_rev)):
index += int(im_rev[i]) * p(i + 1)
# print(int(im_rev[i]), p(i + 1))
print("序数:", index)
print("----------------")
return index

def idx2upinter(idx):
base = 9
perm = ""
while int(idx / p(base)) == 0:
base -= 1
while base > 0:
perm += str(int(idx / p(base)))
idx = idx % p(base)
# print("-->", idx)
base -= 1
print("转换为递增中介数", perm)
print("----------------")
return int(perm)

def idx2downinter(idx):
base = p(8)
BASE = 1
perm = ""
while int(idx / base) == 0:
print(base / BASE)
base = int(base / BASE)
BASE += 1
while base > 1:
print("-->", idx, "/", base)
perm += str(int(idx / base))
idx = idx % base
base = int(base / BASE)
BASE += 1
perm += str(idx)
print("转换为递减中介数", perm)
print("----------------")
return int(perm)

def downinter2idx(downinter):
downinter = str(downinter)[::-1]
ret = 0
base = 1
BASE = 9
for i in range(0, len(downinter)):
ret += int(downinter[i]) * base
base *= BASE
BASE -= 1
print("递减中介数转换为序号", ret)
return ret

if __name__ == '__main__':
main()

测试输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
输入: 83674521
中介数: 7244221
序数: 37313
----------------
输入: 839647521
中介数: 72642321
序数: 297191
----------------
输入: 839651247
中介数: 72643000
序数: 297192
----------------
转换为递增中介数 7244221
----------------
转换为递增中介数 7000201
----------------
输入: 81236475
中介数: 7000201
序数: 35293
----------------
转换为递增中介数 244020
----------------
40320.0
20160.0
6720.0
1680.0
--> 2020 / 1680
--> 340 / 336
--> 4 / 56
--> 4 / 8
转换为递减中介数 11004
----------------
递减中介数转换为序号 2020
递减中介数转换为序号 99097
297191
37313
35293
[Finished in 0.1s]

全排列思考题

Matlab用了什么方法来算全排列?

简单来说就是旧版的MATLAB(R2015b)有一定的BUG(程序员想当然,导致全排列的生成顺序不定),新版的MATLAB(R2016a至R2020a)全排列的生成算法已经修复了该问题。网络学堂上有更为详细的讨论,这里便不再展开。

全排列(Project 1)

https://www.sharelatex.com 学术论文Latex模板

https://www.overleaf.com/latex/templates/latex-template-for-submissions-to-the-international-organization-journal/wgzvjqgswybk

本次project一定要找好方向~

Knuth的第三卷书:

Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005.

On constructing permutations of finite fields 一篇数学系的paper

New recursive circular algorithm for listing all permutations

Permutations Generated by Stacks and Deques 用数据结构生成排列

A Two-level Algorithm for Generating Multiset Permutations 多重集

From Permutations to Iterative Permutations

Efficient Chaotic Permutations for Image Encryption Algorithms 图形学

From Subjective to Objective Metrics for Evolutionary Story Narration Using Event Permutations NLP

rdtscp系统调用测cycle级程序用时。


提交内容

请将程序代码,可执行文件,运行截图以及readme文件和paper整理打包成一个压缩文件提交到本次作业中。

程序要求:C/C++ or Java编程实现,提交代码,可执行文件,运行截图和readme文件

提交paper一篇,论文模板可参考任何学术会议或期刊,中英文均可。

以下三个内容任选其一或者多个。

  • 在实现和研究4种全排列生成算法基础上进行创新
  • 算法效率和复杂度分析或理论证明
  • 新的算法, 有关排列生成的任何相关内容的创新点

评分以论文为主,提交代码为参考,满分5分。

全排列生成算法调研

  • 递归
    • 不安全,邻域性好
  • 字典序法
    • 直观,邻域性差
  • 递增进位制
    • 中介数转换更易操作
    • 进位频繁,邻域性差
  • 递减进位制
    • 进位不频繁,但是每次进位都会失去邻域性
  • SJT算法
    • 安全,但是不好计数
      • 引入邻位中介数 $\longrightarrow$ 得到SJT算法意义下的序号,解决计数问题

4种基础全排列生成算法实现(C++)

字典序法 Lexicographic permutation generation

与组合数学课上介绍的算法步骤略有不同。先反转,再交换。它们的顺序无关紧要。

算法大约分为三步:

  • 从右向左,找到第一个下降的位置 i,$O(n)$
  • 反转 i 之后的所有元素,$O(n)$
  • i 和 其后缀中比它大的最小元素 进行交换,$O(n)$ 或 $O(\log n)$,在于是否二分

对于第一步:找到第一个下降的位置,虽然其最大复杂度可达 $O(n)$ 量级,但是在分摊意义下则为 $O(1)$。

这是因为对于随机的排列来说,任意数字的下一个数字更大或更小是同时可能的,并且概率相等。这意味着连续增、连续降的子序列的期望长度为 $O(1)$。

这样,对于第二步来说,其平摊效率也将变为 $O(1)$。

同理,第三步也将平摊为 $O(1)$。

二分可能可以提高一定的常数效率,但需要权衡。

故总算法效率为 $O(n!)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;

// #define __DEBUG__
#define _for(i,a,b) for(int i =(a); i < (b); ++i)
#define _rep(i,a,b) for(int i =(a); i <= (b); ++i)
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for(auto it = v.begin(); it != v.end(); it++)
os<<*it<<" ";
return os;
}

// the charset of the permutaions
string BASE = "123456789";
// BASE = "0123456789abcdefghijklmnopqrstuvwxyz"
// BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZ"

void lexicographic_permutation_generation(int n){
cout << "Lexicographic permutation generation"<<"(n = "<<n<<")"<<":" <<endl;
vector<char> perms;
#ifndef __DEBUG__
_for(i, 0, n) perms.push_back(BASE[i]);
#endif
#ifdef __DEBUG__
perms.push_back('1');
perms.push_back('2');
perms.push_back('5');
perms.push_back('4');
perms.push_back('3');
#endif
cout << perms <<endl;
while(true){
// fisrt the first rank that going downwards
int first_downward_site = -1;
_for(i, 1, n){
// cout << perms[n - 1 - i] << " " << perms[n -i] << endl;
if(perms[n - 1 - i] < perms[n - i]){
// cout <<" --> "<< perms[n - 1 - i] << " " << perms[n -i] << endl;
first_downward_site = n - i -1;
break;
}
}
if(first_downward_site == -1) break;
#ifdef __DEBUG__
cout << "first_downward_site: " <<perms[first_downward_site]<<" ["<< first_downward_site << "]" <<endl;
#endif

// reverse the subvector behind the first_downward_site
_for(i, first_downward_site + 1, n){
if(i >= n - 1 - (i - first_downward_site - 1)) break;
swap(perms[i], perms[n - 1 - (i - first_downward_site - 1)]);
}

#ifdef __DEBUG__
cout << perms <<endl;
#endif

// find the minimal number that greater than the first_downward_site number
_for(i, first_downward_site + 1, n){
if(i == n - 1)
swap(perms[first_downward_site], perms[i]);
else if(perms[first_downward_site] < perms[i]){
swap(perms[first_downward_site], perms[i]);
break;
}
}
cout << perms <<endl;

#ifdef __DEBUG__
cout << "-------------" <<endl;
#endif

}
}

int main(){
freopen("OJ.in", "r", stdin);
// freopen("OJ.out", "w", stdout);
int n; cin >> n;

lexicographic_permutation_generation(n);

return 0;
}
利用中介数生成字典序

在递增进位制数的基础,只需要改写一下to_permutation方法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;

// #define __DEBUG__
#define _for(i,a,b) for(int i =(a); i < (b); ++i)
#define _rep(i,a,b) for(int i =(a); i <= (b); ++i)
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for(auto it = v.begin(); it != v.end(); it++)
os<<*it<<" ";
return os;
}

// the charset of the permutaions
string BASE = "123456789";
// BASE = "0123456789abcdefghijklmnopqrstuvwxyz"
// BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZ"

struct number{
vector<int> digits, T;
number(int n) {
digits.resize(n, 0);
T.resize(n);
_for(i, 0, n) T[i] = i + 2;
}
number(string s){
unsigned n = s.size();
digits.resize(n, 0);
T.resize(n);
_for(i, 0, n) T[i] = i + 2;
_for(i, 0, n) digits[i] = s[n - 1 - i] - '0';
overflow();
}
overflow(){
_for(i, 0, digits.size()){
if(digits[i] >= T[i]){
if(i + 1 == digits.size()){
digits.push_back(digits[i] / T[i]);
digits[i] = digits[i] % T[i];
break;
} else{
digits[i + 1] += digits[i] / T[i];
digits[i] = digits[i] % T[i];
}
}
// cout <<digits<<endl;
}
}
string to_permutation(int perm_range = -1){ // perm_range is how many items in perms
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');

vector<int> rank; rank.resize(perm_range + 1, 0);
_for(i, 0, perm_range + 1) rank[i] = i;
// cout << " --> "<<rank<<endl;

for(int i = perm_range; i >= 1; i--){
int count = digits[i - 1];
// cout << "count: "<<count<<endl;

int target = -1;

_for(i, 0, perm_range + 1){
if(rank[i] == count){
target = i;
rank[i] = -1;
_for(j, i+1, perm_range + 1) if(rank[j] != -1) rank[j] -= 1;
break;
}
}

permutaion[perm_range - i] = BASE[target];
// cout << permutaion <<endl;
// cout << " --> "<<rank<<endl;
}

_for(i, 0, perm_range + 1)
if(rank[i] != -1){
_for(j, 0, perm_range + 1){
if(permutaion[j] == '*')
permutaion[j] = BASE[i];
}
break;
}
// cout << permutaion <<endl;

return permutaion;
}

number operator +(int b){
digits[0] += b;
overflow();
return *this;
}
number operator ++(int){
digits[0] += 1;
overflow();
return *this;
}
};
ostream& operator<<(ostream& os, const number& N){
vector<int> v = N.digits;
for(auto it = v.rbegin(); it != v.rend(); it++)
os<<*it<<"";
return os;
}


int main(){
freopen("OJ.in", "r", stdin);
// freopen("OJ.out", "w", stdout);
int n; cin >> n;

// lexicographic_permutation_generation(n);

number X("00000000");
cout<< X << "::" << X.to_permutation()<<endl;

_for(i, 0, 10){
X++;
cout<< X << "::" << X.to_permutation()<<endl;
}

return 0;
}

递增进位制法 Increase

递增进位制法,需要首先构造递增进位制数。构造了递增进位制数及其运算系统之后,再实现将递增进位制数转换为对应排列的方法即可。

在基于中介数的各种算法中。算法的效率都可以被拆分成两个部分,一个是中介数的加减法效率,另一个是中介数和排列相互转化的效率。递增进位制数对字典序中介数的改进在于,更易实现从中介数到排列的转化。

对于第一部分:中介数的加减法。在某一位上的加减法,只需要 $O(1)$ 的基本运算即可。然后,往高位或往低位扫描每一位,看是否会发生进位/借位,这里每次发生运算后需要 $O(n)$ 的时间,这一部分对应代码中 overflow() 或者 underflow()

对于第二部分:则完全采用课堂上讲述的从中介数到对应去全排列的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;

// #define __DEBUG__
#define _for(i,a,b) for(int i =(a); i < (b); ++i)
#define _rep(i,a,b) for(int i =(a); i <= (b); ++i)
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for(auto it = v.begin(); it != v.end(); it++)
os<<*it<<" ";
return os;
}

// the charset of the permutaions
string BASE = "123456789";
// BASE = "0123456789abcdefghijklmnopqrstuvwxyz"
// BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZ"

struct number{
vector<int> digits, T;
number(int n) {
digits.resize(n, 0);
T.resize(n);
_for(i, 0, n) T[i] = i + 2;
}
number(string s){
unsigned n = s.size();
digits.resize(n, 0);
T.resize(n);
_for(i, 0, n) T[i] = i + 2;
_for(i, 0, n) digits[i] = s[n - 1 - i] - '0';
overflow();
}
overflow(){
_for(i, 0, digits.size()){
if(digits[i] >= T[i]){
if(i + 1 == digits.size()){
digits.push_back(digits[i] / T[i]);
digits[i] = digits[i] % T[i];
break;
} else{
digits[i + 1] += digits[i] / T[i];
digits[i] = digits[i] % T[i];
}
}
// cout <<digits<<endl;
}
}
string to_permutation(int perm_range = -1){ // perm_range is how many items in perms
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');
for(int num = perm_range; num >= 1; num--){

int count = 0, site = perm_range;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site--;
} site++;
permutaion[site] = BASE[num];
// cout << permutaion <<endl;
}

_for(site, 0, perm_range + 1)
if(permutaion[site] == '*'){
permutaion[site] = BASE[0];
break;
}
// cout << permutaion <<endl;

return permutaion;
}

number operator +(int b){
digits[0] += b;
overflow();
return *this;
}
number operator ++(int){
digits[0] += 1;
overflow();
return *this;
}
};
ostream& operator<<(ostream& os, const number& N){
vector<int> v = N.digits;
for(auto it = v.rbegin(); it != v.rend(); it++)
os<<*it<<"";
return os;
}


int main(){
freopen("OJ.in", "r", stdin);
// freopen("OJ.out", "w", stdout);
int n; cin >> n;

// lexicographic_permutation_generation(n);

number X("00000000");
cout<< X << "::" << X.to_permutation()<<endl;

_for(i, 0, 10){
X++;
cout<< X << "::" << X.to_permutation()<<endl;
}

return 0;
}

递减进位制法 Decrease

与递增进位制数的机制相似,只是数位发生反转,也就是进位方向调整一下即可。对应到代码上只需要修改T[i]的初始化即可。

1
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;

同时,在to_permutation中只需前后加上reverse(digits.begin(), digits.end());就可以复用递增进位制的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;

// #define __DEBUG__
#define _for(i,a,b) for(int i =(a); i < (b); ++i)
#define _rep(i,a,b) for(int i =(a); i <= (b); ++i)
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for(auto it = v.begin(); it != v.end(); it++)
os<<*it<<" ";
return os;
}

// the charset of the permutaions
string BASE = "123456789";
// BASE = "0123456789abcdefghijklmnopqrstuvwxyz"
// BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZ"

struct number{
vector<int> digits, T;
number(int n) {
digits.resize(n, 0);
T.resize(n);
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;
}
number(string s){
unsigned n = s.size();
digits.resize(n, 0);
T.resize(n);
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;
_for(i, 0, n) digits[i] = s[n - 1 - i] - '0';
overflow();
}
overflow(){
_for(i, 0, digits.size()){
if(digits[i] >= T[i]){
if(i + 1 == digits.size()){
digits.push_back(digits[i] / T[i]);
digits[i] = digits[i] % T[i];
break;
} else{
digits[i + 1] += digits[i] / T[i];
digits[i] = digits[i] % T[i];
}
}
// cout <<digits<<endl;
}
}
string to_permutation(int perm_range = -1){ // perm_range is how many items in perms
reverse(digits.begin(), digits.end());
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');
for(int num = perm_range; num >= 1; num--){

int count = 0, site = perm_range;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site--;
} site++;
permutaion[site] = BASE[num];
// cout << permutaion <<endl;
}

_for(site, 0, perm_range + 1)
if(permutaion[site] == '*'){
permutaion[site] = BASE[0];
break;
}
// cout << permutaion <<endl;

reverse(digits.begin(), digits.end());
return permutaion;
}

number operator +(int b){
digits[0] += b;
overflow();
return *this;
}
number operator ++(int){
digits[0] += 1;
overflow();
return *this;
}
};
ostream& operator<<(ostream& os, const number& N){
vector<int> v = N.digits;
for(auto it = v.rbegin(); it != v.rend(); it++)
os<<*it<<"";
return os;
}


int main(){
freopen("OJ.in", "r", stdin);
// freopen("OJ.out", "w", stdout);
int n; cin >> n;

// lexicographic_permutation_generation(n);

number X("00000000");

// cout << X << endl;
// _for(i, 0, 100){
// X++;
// cout<< X <<endl;
// }

cout<< X << "::" << X.to_permutation()<<endl;

_for(i, 0, 100){
X++;
cout<< X << "::" << X.to_permutation()<<endl;
}

return 0;
}

邻位对换法 Adjacent interchanges

Plain changes 平易的改动

Knuth P178:邻位对换在每次访问中恰做一次这一事实意味着它所生成的排列交替地为偶的和奇的。因此我们通过简单地绕过奇数的那些就能生成全部为偶数的排列。

邻位对换的代码实现还是比较简单的,重写to_permutation方法即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;

// #define __DEBUG__
#define _for(i,a,b) for(int i =(a); i < (b); ++i)
#define _rep(i,a,b) for(int i =(a); i <= (b); ++i)
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for(auto it = v.begin(); it != v.end(); it++)
os<<*it<<" ";
return os;
}

// the charset of the permutaions
string BASE = "123456789";
// BASE = "0123456789abcdefghijklmnopqrstuvwxyz"
// BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZ"

struct number{
vector<int> digits, T;
number(int n) {
digits.resize(n, 0);
T.resize(n);
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;
}
number(string s){
unsigned n = s.size();
digits.resize(n, 0);
T.resize(n);
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;
_for(i, 0, n) digits[i] = s[n - 1 - i] - '0';
overflow();
}
overflow(){
_for(i, 0, digits.size()){
if(digits[i] >= T[i]){
if(i + 1 == digits.size()){
digits.push_back(digits[i] / T[i]);
digits[i] = digits[i] % T[i];
break;
} else{
digits[i + 1] += digits[i] / T[i];
digits[i] = digits[i] % T[i];
}
}
// cout <<digits<<endl;
}
}
string to_permutation(int perm_range = -1){ // perm_range is how many items in perms
reverse(digits.begin(), digits.end());
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');

vector<bool> used_nums; used_nums.resize(perm_range + 1, false);
for(int num = perm_range; num >= 1; num--){
// cout << "-> BASE["<< num << "] = "<< BASE[num] <<endl;
bool to_right;
if(num == 1){
to_right = false;
}
else if(num % 2){ // index(num) is odd, number is even
// cout << "b["<<num<<"] = "<<digits[num - 1]<< "; b["<<num - 1<<"] = " << digits[num - 2]<<endl;
to_right = (digits[num - 2] + digits[num - 3]) % 2;
} else{
// cout << "b["<<num<<"] = "<<digits[num - 1]<<endl;
to_right = digits[num - 2] % 2;
}
// cout <<"to_right: "<< to_right <<endl;


if(to_right){
int count = 0, site = 0;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site++;
} site--;
permutaion[site] = BASE[num]; used_nums[num] = true;
// cout << permutaion <<endl;
} else{
int count = 0, site = perm_range;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site--;
} site++;
permutaion[site] = BASE[num]; used_nums[num] = true;
// cout << permutaion <<endl;
}
}

_rep(i, 0, perm_range)
if(!used_nums[i])
_rep(j, 0, perm_range)
if(permutaion[j] == '*')
permutaion[j] = BASE[i];

// cout << permutaion <<endl;
reverse(digits.begin(), digits.end());
return permutaion;
}

number operator +(int b){
digits[0] += b;
overflow();
return *this;
}
number operator ++(int){
digits[0] += 1;
overflow();
return *this;
}
};
ostream& operator<<(ostream& os, const number& N){
vector<int> v = N.digits;
for(auto it = v.rbegin(); it != v.rend(); it++)
os<<*it<<"";
return os;
}


int main(){
freopen("OJ.in", "r", stdin);
// freopen("OJ.out", "w", stdout);
int n; cin >> n;

// lexicographic_permutation_generation(n);

number X("00000000");

// cout << X << endl;
// _for(i, 0, 100){
// X++;
// cout<< X <<endl;
// }

cout<< X << "::" << X.to_permutation()<<endl;

_for(i, 0, 100){
X++;
cout<< X << "::" << X.to_permutation()<<endl;
}

return 0;
}



从上面的实现过程可以明显感受到,在引入了中介数的概念以后,全排列的生成逻辑就被明显地分成了两个部分,一部分用于维护中介数的表示、存储和计算,另一部分则负责中介数到排列的转换。

其它全排列算法

循环位移法

算法效率

算法效率应该分为几个主题来衡量:

  • 依次生成所有排列的效率
  • 生成某个指定序号的排列的效率
  • 推导前驱/后继排列的效率

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
#include<bits/stdc++.h>
#include<ctime>
using namespace std;

// #define __DEBUG__
#define _for(i,a,b) for(int i =(a); i < (b); ++i)
#define _rep(i,a,b) for(int i =(a); i <= (b); ++i)
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){
for(auto it = v.begin(); it != v.end(); it++)
os<<*it<<" ";
return os;
}

// the charset of the permutaions
// string BASE = "123456789";
// string BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZ";
string BASE = "0123456789ABCDEFGHIJKLMNPOQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";


struct number{
vector<int> digits, T;
number(int n, string Type = "increase") {
digits.resize(n, 0);
T.resize(n);
if (Type == "increase"){
_for(i, 0, n) T[i] = i + 2;
} else{
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;
}
}
number(string s, string Type = "increase"){
unsigned n = s.size();
digits.resize(n, 0);
T.resize(n);
if (Type == "increase"){
_for(i, 0, n) T[i] = i + 2;
} else{
for(int i = n - 1; i >= 0; i--) T[i] = n - i + 1;
}
_for(i, 0, n) digits[i] = s[n - 1 - i] - '0';
overflow();
}
overflow(){
_for(i, 0, digits.size()){
if(digits[i] >= T[i]){
if(i + 1 == digits.size()){
digits.push_back(digits[i] / T[i]);
digits[i] = digits[i] % T[i];
break;
} else{
digits[i + 1] += digits[i] / T[i];
digits[i] = digits[i] % T[i];
}
}
// cout <<digits<<endl;
}
}

string to_permutation_dictionary(int perm_range = -1){ // perm_range is how many items in perms
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');

vector<int> rank; rank.resize(perm_range + 1, 0);
_for(i, 0, perm_range + 1) rank[i] = i;
// cout << " --> "<<rank<<endl;

for(int i = perm_range; i >= 1; i--){
int count = digits[i - 1];
// cout << "count: "<<count<<endl;

int target = -1;

_for(i, 0, perm_range + 1){
if(rank[i] == count){
target = i;
rank[i] = -1;
_for(j, i+1, perm_range + 1) if(rank[j] != -1) rank[j] -= 1;
break;
}
}

permutaion[perm_range - i] = BASE[target];
// cout << permutaion <<endl;
// cout << " --> "<<rank<<endl;
}

_for(i, 0, perm_range + 1)
if(rank[i] != -1){
_for(j, 0, perm_range + 1){
if(permutaion[j] == '*')
permutaion[j] = BASE[i];
}
break;
}
// cout << permutaion <<endl;

return permutaion;
}

string to_permutation_increase(int perm_range = -1){ // perm_range is how many items in perms
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');
for(int num = perm_range; num >= 1; num--){

int count = 0, site = perm_range;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site--;
} site++;
permutaion[site] = BASE[num];
// cout << permutaion <<endl;
}

_for(site, 0, perm_range + 1)
if(permutaion[site] == '*'){
permutaion[site] = BASE[0];
break;
}
// cout << permutaion <<endl;

return permutaion;
}

string to_permutation_decrease(int perm_range = -1){ // perm_range is how many items in perms
reverse(digits.begin(), digits.end());
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');
for(int num = perm_range; num >= 1; num--){

int count = 0, site = perm_range;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site--;
} site++;
permutaion[site] = BASE[num];
// cout << permutaion <<endl;
}

_for(site, 0, perm_range + 1)
if(permutaion[site] == '*'){
permutaion[site] = BASE[0];
break;
}
// cout << permutaion <<endl;

reverse(digits.begin(), digits.end());
return permutaion;
}

string to_permutation_adjacent_interchanges(int perm_range = -1){ // perm_range is how many items in perms
reverse(digits.begin(), digits.end());
if(perm_range = -1) perm_range = digits.size();
digits.resize(perm_range, 0);

string permutaion; permutaion.resize(perm_range + 1, '*');

vector<bool> used_nums; used_nums.resize(perm_range + 1, false);
for(int num = perm_range; num >= 1; num--){
// cout << "-> BASE["<< num << "] = "<< BASE[num] <<endl;
bool to_right;
if(num == 1){
to_right = false;
}
else if(num % 2){ // index(num) is odd, number is even
// cout << "b["<<num<<"] = "<<digits[num - 1]<< "; b["<<num - 1<<"] = " << digits[num - 2]<<endl;
to_right = (digits[num - 2] + digits[num - 3]) % 2;
} else{
// cout << "b["<<num<<"] = "<<digits[num - 1]<<endl;
to_right = digits[num - 2] % 2;
}
// cout <<"to_right: "<< to_right <<endl;


if(to_right){
int count = 0, site = 0;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site++;
} site--;
permutaion[site] = BASE[num]; used_nums[num] = true;
// cout << permutaion <<endl;
} else{
int count = 0, site = perm_range;
while(count <= digits[num - 1]) {
if(permutaion[site] == '*') count++;
site--;
} site++;
permutaion[site] = BASE[num]; used_nums[num] = true;
// cout << permutaion <<endl;
}
}

_rep(i, 0, perm_range)
if(!used_nums[i])
_rep(j, 0, perm_range)
if(permutaion[j] == '*')
permutaion[j] = BASE[i];

// cout << permutaion <<endl;
reverse(digits.begin(), digits.end());
return permutaion;
}

number operator +(int b){
digits[0] += b;
overflow();
return *this;
}
number operator ++(int){
digits[0] += 1;
overflow();
return *this;
}
};
ostream& operator<<(ostream& os, const number& N){
vector<int> v = N.digits;
for(auto it = v.rbegin(); it != v.rend(); it++)
os<<*it<<"";
return os;
}

void lexicographic_permutation_generation(int n, int generation_steps){
// cout << "Lexicographic permutation generation"<<"(n = "<<n<<")"<<":" <<endl;
vector<char> perms;
#ifndef __DEBUG__
_for(i, 0, n) perms.push_back(BASE[i]);
#endif
#ifdef __DEBUG__
perms.push_back('1');
perms.push_back('2');
perms.push_back('5');
perms.push_back('4');
perms.push_back('3');
#endif
// cout << perms <<endl;
int count_steps = 0;
while(true){
count_steps ++;
if (count_steps > generation_steps) break;
// fisrt the first rank that going downwards
int first_downward_site = -1;
_for(i, 1, n){
// cout << perms[n - 1 - i] << " " << perms[n -i] << endl;
if(perms[n - 1 - i] < perms[n - i]){
// cout <<" --> "<< perms[n - 1 - i] << " " << perms[n -i] << endl;
first_downward_site = n - i -1;
break;
}
}
if(first_downward_site == -1) break;
#ifdef __DEBUG__
cout << "first_downward_site: " <<perms[first_downward_site]<<" ["<< first_downward_site << "]" <<endl;
#endif

// reverse the subvector behind the first_downward_site
_for(i, first_downward_site + 1, n){
if(i >= n - 1 - (i - first_downward_site - 1)) break;
swap(perms[i], perms[n - 1 - (i - first_downward_site - 1)]);
}

#ifdef __DEBUG__
cout << perms <<endl;
#endif

// find the minimal number that greater than the first_downward_site number
_for(i, first_downward_site + 1, n){
if(i == n - 1)
swap(perms[first_downward_site], perms[i]);
else if(perms[first_downward_site] < perms[i]){
swap(perms[first_downward_site], perms[i]);
break;
}
}
// cout << perms <<endl;

#ifdef __DEBUG__
cout << "-------------" <<endl;
#endif

}

// cout << count_steps <<endl;
}



int main(){
// freopen("OJ.in", "r", stdin);
// freopen("OJ.out", "w", stdout);
int n = 11, generation_steps = 300000;
// cin >> n;
clock_t beg, end;
int test_times = 2;
double average_sec, sum;
_for(i, 0, test_times){
beg = clock();
lexicographic_permutation_generation(n, generation_steps);
end = clock();
sum += (double)(end - beg) / CLOCKS_PER_SEC;
}
average_sec = sum / test_times;
cout << "lexicographic simulation:" << average_sec << " s" <<endl;


_for(i, 0, test_times){
beg = clock();

number X(n, "increase");
_for(i, 0, generation_steps){
X++;
X.to_permutation_dictionary();
}

end = clock();
sum += (double)(end - beg) / CLOCKS_PER_SEC;
}
average_sec = sum / test_times;
cout << "to_permutation_dictionary:" << average_sec << " s" <<endl;

_for(i, 0, test_times){
beg = clock();

number X(n, "increase");
_for(i, 0, generation_steps){
X++;
X.to_permutation_increase();
}

end = clock();
sum += (double)(end - beg) / CLOCKS_PER_SEC;
}
average_sec = sum / test_times;
cout << "to_permutation_increase:" << average_sec << " s" <<endl;

_for(i, 0, test_times){
beg = clock();

number X(n, "decrease");
_for(i, 0, generation_steps){
X++;
X.to_permutation_decrease();
}

end = clock();
sum += (double)(end - beg) / CLOCKS_PER_SEC;
}
average_sec = sum / test_times;
cout << "to_permutation_decrease:" << average_sec << " s" <<endl;

_for(i, 0, test_times){
beg = clock();

number X(n, "decrease");
_for(i, 0, generation_steps){
X++;
X.to_permutation_adjacent_interchanges();
}

end = clock();
sum += (double)(end - beg) / CLOCKS_PER_SEC;
}
average_sec = sum / test_times;
cout << "to_permutation_adjacent_interchanges:" << average_sec << " s" <<endl;






// number X(n, "decrease");

// cout << X << endl;
// _for(i, 0, 100){
// X++;
// cout<< X <<endl;
// }

// cout<< X << "::" << X.to_permutation_adjacent_interchanges()<<endl;

// _for(i, 0, 100){
// X++;
// cout<< X << "::" << X.to_permutation_adjacent_interchanges()<<endl;
// }

return 0;
}

逆序数分析

LHR提出可以研究研究不同全排列生成算法中逆序数的变化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import pandas as pd
import os
import matplotlib.pyplot as plt
import seaborn as sns
import numpy as np

path = "./stats/"
# files = os.listdir(path)
files = ['decr_perm.csv', 'dict_perm.csv', 'ehrlich_perm.csv', 'heap_perm.csv', 'incr_perm.csv', 'inv_perm.csv', 'shift_perm.csv', 'sjt_perm.csv']
print(files)


rows = 4
cols = 2
f, ax = plt.subplots(ncols=cols, nrows=rows, figsize=(16, 14))

for i in range(0, rows):
for j in range(0, cols):
filename = path + files[i * cols + j]
df = pd.read_csv(filename)
n = df.shape[0]
index = pd.timedelta_range(0, periods=n, freq='s')
df.index = index
df = df.resample('1000S').mean()
print(df.shape)
print(df)
# plt.xlabel('Smarts')
# plt.ylabel('v')
ax[i, j].plot(df["index"], df["inversion"])
ax[i, j].set_title(files[i * cols + j])


plt.show()

效果图

母函数

一定要提前复习和预习,否则课上答题是跟不上的。

母函数的定义

拉普拉斯 :1812年,法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论。

母函数 / 生成函数(Generating Function):对于计数序列 $c_0,c_1,c_2,…$ ,构造一函数 $G(x)=c_0+c_1x+c_2x^2+…$,称 $G(x)$ 为序列 $c_0,c_1,c_2,…$的母函数。

母函数只是一种计数工具。它可以提高计数运算的效率。我们不考虑它的收敛性、实际上的数值。母函数是一种形式幂级数(Formal power series)。

“似函数,非函数”。母函数是母亲,计数序列是孩子。

母函数就是一列用来展示一串数字序列的挂衣架。

母函数是一种映射手段(归约),将计数问题转化为更好计算的映像。

映射,是两类数学对象或集合之间的某种“对应关系”。 ———《数学方法论选讲》


投色子

雅各布 · 伯努利 / Jakob I. Bernoulli,瑞士数学家1654-1705

例:两个筛子投出 $n$ 点,有多少种可能?

设计母函数:

求两个色子掷出 $n$ 点的可能方法,即为求 $G(x) = (x+x^2+x^3+x^4+x^5+x^6)^2$ 中 $x^n$ 的系数。

$x^6$ 的系数为 5,表示两个色子掷出6点的可能方法有5种。

投色子进阶

问题: 投掷 $m$ 粒色子时,加起来点数总和等于 $n$。

所求即为 $G(x)$ 展开式中 $x^n$ 项的系数。

$(1-a x)^{-1}=1+a x+a^{2} x^{2}+\ldots$

母函数练习题

计数法则

母函数是母亲,计数序列是孩子。

“数学发展中比比皆是通过映射手段求解的现象。” “镜子”

加法法则:$n$ 个计数对象所有的划分策略累加(对应母函数中的基础多项式)

乘法法则:$n$ 个计数对象可以划分为 $i$ 个对象和 $n-i$ 个对象(对应母函数中多项式之间的乘法)

多项式乘法运算使母函数具备了计数的能力。

砝码称重

简单砝码

例:若有1克、2克、3克、4克的砝码各一枚,问能称出哪几种重量?有几种可能方案?

设计母函数。其中,1 = $x^0$ 表示不选

$\begin{array}{l}
G(x)&=(1+x)\left(1+x^{2}\right)\left(1+x^{3}\right)\left(1+x^{4}\right) \\
&=1+x+x^{2}+2 x^{3}+2 x^{4}+2 x^{5}+2 x^{6}+2 x^{7}+x^{8}+x^{9}+x^{10}
\end{array}$

从母函数的展开式知可称出从1克到10克,对应系数便是方案数。

二进制砝码

例:若有1、2、4、81632克的砝码各一枚,问能称出哪几种重量?有几种可能方案?

类似地。引入因式分解化简:

从母函数可以得知,用这些砝码可以称出从1克到63克的重量,而且办法都是唯一的。

可以推广到证明任一十进制数 $n$,可唯一表示为 $n=\sum_{k \geq 0} a_{k} 2^{k}, \quad 0 \leq a_{k} \leq 1, k \geq 0$。

多重砝码

例:若有1克砝码3枚、2克砝码4枚、4克砝码2枚,问能称出那几种重量?各有几种方案?

有几枚砝码,多项式就增加相应的几项。 “卷”

能称出19种重量,相应的系数就是对应的重量的方案数。

可重砝码

例:求用1分、2分、3分的邮票贴出不同数值的方案数。

邮票允许无限重复(完全背包)。

以 $x^4$ 为例,其系数为 4,即将 4 拆分为 1、2、3 之和的拆分数为 4。 “长除法”

  • 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 3 = 2 + 2

*长除法解多项式除法。(写代码)

整数拆分

整数拆分:所谓自然数(正整数)分拆,就是将一个正整数表达成若干个正整数之和。

  • 各部分之间考虑顺序的叫有序拆分(Composition)
    • n的有序r-拆分的个数是 $C(n-1,r-1)$
      • n个球,要分成r份,用r-1个隔板插入到球之间的n-1个空隙,方案数 $C(n-1,r-1)$
    • 放球模型:n的一个r-分拆相当于把n个无区别的球放到r个有标志的盒子,盒子不允许空着
  • 若考虑有序拆分的非负整数解$C(n+r-1,n)$
    • 放球模型:相当于把n个无区别的球放到r个有标志的盒子,盒子允许空着
  • 否则叫无序拆分(Partition) / 即整数拆分
    • 放球模型:相当于把n个无区别的球放到n个无标志的盒子,盒子允许空着,也允许放多于一个球。

整数拆分示例

例:整数n拆分成1,2,3,…,m的和,并允许重复,求其母函数。如若其中m至少出现一次,其母函数如何?

若拆分中m至少出现一次,其母函数为

或等价地

第二个等价写法的组合意义:即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数,即为至少出现一个m的拆分数。

分堆思考题

n个相同的球,分成若干堆,有几种分法?

partition of a positive integer $n$:无法写出确切的答案

整数拆分数

欧拉,1740年回复诺地的信

正整数的无序拆分:将一个正整数 $n$ 拆分成若干正整数的和(比如 8 = 1+2+2+3),数字之间顺序无关并允许重复,其不同的拆分数即 $p(n)$。(OEIS: A000041序列)


例:$x+3 y+6 z=n$ 的非负整数解的个数根据正整数 $n$ 对 应构成的序列 $S_{n},$ 请写出 $S_{n}$ 对应的母函数。

等效于把n拆分成若干个1|3|6的方案数。(在母函数的指数上进行累计,母函数的系数表示的是方案数)

$G(x)=(1+x+x^2+\cdots)(1+x^3+x^6+\cdots)(1+x^6+x^{12}+\cdots)=\cfrac{1}{1-x}\cfrac{1}{1-x^3}\cfrac{1}{1-x^6}$

整数拆分数思考题

你能精确计算出最大的整数拆分数是多少?

wait for time..

相关猜想:BSD 猜想

– Birch and Swinnerton-Dyer猜想
– 数学界七大问题之一
– 100万美元奖金

拆分数估计式

拆分数估计式:设 $p_n$ 为整数 $n$ 的拆分数,则 $p_n<e^{\sqrt{\frac{20}{3}n}}$。

证明:令母函数为 $G(x)=p_{0}+p_{1} x+p_{2} x^{2}+\cdots$。

由整数拆分定义得母函数的具体形式为

取对数:

根据Taylor展开 $\ln (1+x)=\sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} x^{n}$,有

又因为 $\frac{x^{n}}{1-x^{n}}<\frac{1}{n} \cdot \frac{x}{1-x}$,放缩得到

又因为 $\frac{1}{n^{2}}<\frac{1}{n^{2}-\frac{1}{4}}=\frac{1}{n-\frac{1}{2}}-\frac{1}{n+\frac{1}{2}}$,再次放缩得到

同时,$G(x)=p_{0}+p_{1} x+p_{2} x^{2}+\cdots+p_{n} x^{n}+\cdots>p_{n} x^{n}$,得到

然后对右侧函数求极小值即得证。

Ferrers图像

Ferrers图像:一个从上而下的 $n$ 层格子,$m_i$ 为第 $i$ 层的格子数,当 $m_i\ge m_{i+1},(i=1,2,\dots,n-1)$,即上层的格子数不少于下层的格子数时( weakly decreasing),称之为Ferrers图像(Ferrers diagram)。

Ferrers图像具有如下性质:

  • 每一层至少有一个格子。
  • 第一行与第一列互换,第二行于第二列互换,…,即上图绕虚线轴对称所得的图仍然是Ferrers图像。两个Ferrers图像称为一对共轭的Ferrers图像。

利用Ferrers图像可得关于整数拆分的十分有趣的结果。

  • 整数n拆分成最大数为k的拆分数,和数n拆分成k个数的和的拆分数相等。
    • 因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。
  • 整数n拆分成最多不超过m个数的和的拆分数,和n拆分成最大不超过m的拆分数相等。(类似地,共轭)

拆分成最多不超过m个数的和的拆分数的母函数是(根据推论):$\cfrac{1}{(1-x)\left(1-x^{2}\right) \cdots\left(1-x^{m}\right)}$

拆分成最多不超过m-1个数的和的拆分数的母函数是(根据推论):$\cfrac{1}{(1-x)\left(1-x^{2}\right) \cdots\left(1-x^{m-1}\right)}$

所以正好拆分成m个数的和的拆分数的母函数为:(共轭地等于m至少出现1次的拆分数)

  • 整数n拆分成互不相同的若干奇数的和的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等。

设 $n=\left(2 n_{1}+1\right)+\left(2 n_{2}+1\right)+\cdots+\left(2 n_{k}+1\right)$,其中 $n_{1}>n_{2}>\cdots>n_{k}$。

构造一个Ferrers图像,其第一行,第一列都是 $n_1+1$ 格,对应于 $2n_1+1$,第二行,第二列各 $n_2+1$ 格,对应于 $2n_2+1$。以此类推。由此得到的Ferrers图像是共轭的。反过来也一样。

递推关系

递推关系(Recurrence Relation):即差分方程(Difference equation),是一种递推地定义一个序列的方程式。序列的每一项目定义为前若干项的函数。

除了递推算法以外,初始值也很重要。

Hanoi塔

例:已知初始条件 $a_{0}=1, a_{1}=3$,递推公式为$a_{n+1}=a_{n}+a_{n-1}(n>0)$

1)求这个数列对应的母函数$H(x)$;

2)如果将母函数进行分式分解,即$H(x)=\cfrac{A}{1-ax}+\cfrac{B}{1-bx}$。

错位相消即可。

Fibonacci数

初始值:$F(0)=0,F(1)=1$。

Fibonacci 兔子

Fibonacci的性质

艾略特波浪(Elliott wave)理论

股票市场遵循Fibonacci数的分布。

0.382,0.618。

Fibonacci思考题

你能找到Fibnacci什么好玩的现象、规律、应用?

二项式定理

$\begin{equation}
{\color{blue}{(1+x)^{-1} } }=1-x+x^{2}+\cdots+(-1)^{k} x^{k}+\cdots
\end{equation}$

$\begin{equation}
{\color{blue}{(1-x)^{-1} } }=1+x+x^{2}+\ldots \ldots
\end{equation}$

$\begin{equation}
{\color{blue}{(1+x)^{n} } }=1+n x+\cfrac{n(n-1)}{2} x^{2}+\cdots+\cfrac{n(n-1) \cdots(n-k+1)}{k !} x^{k}+\cdots
\end{equation}$

$\begin{equation}
\begin{aligned}
{\color{blue}{(1+x)^{\alpha} } } &=1+\alpha x+\frac{\alpha(\alpha-1)}{2} x^{2}+\cdots+\frac{\alpha(\alpha-1) \cdots(\alpha-k+1)}{k !} x^{k}+\cdots \\
&=\sum_{k=0}^{\infty} \frac{\alpha(\alpha-1) \cdots(\alpha-k+1)}{k !} x^{k} \quad {\color{red}{\alpha \in R} }
\end{aligned}
\end{equation}$

$\begin{equation}
{\color{blue}{(a)^{n} } }=a^{n}
\end{equation}$

$\begin{equation}
{\color{blue}{(a+b)^{n} } }=\sum_{k=0}^{n} \cfrac{n !}{k !(n-k) !} a^{n-k} b^{k}
\end{equation}$

$\begin{equation}
{\color{blue}{(a+b+c)^{n} } }=\sum_{k=0}^{n} \sum_{l=0}^{k} \cfrac{n !}{l !(k-l) !(n-k) !} a^{n-k} b^{k-l} c^{l}
\end{equation}$

$\begin{equation}
{\color{blue}{(a+b+c+d)^{n} } }=\sum^{n} \sum^{k} \sum^{l} \cfrac{n !}{m !(l-m) !(k-l) !(n-k) !} a^{n-k} b^{k-l} c^{l-m} d^{m}
\end{equation}$

母函数因式分解练习题

已知初始条件 $a_0=1,\;a_1=3$,

线性常系数齐次递推关系

特征多项式

找递推关系

找递推关系其实是最大的难点。特征多项式反而可以按部就班。

标准求解过程

  • 找递推关系,初始值
  • 写出特征多项式
    • 无重根

指数型母函数

母函数,求解组合问题;指数型母函数,求解排列问题。

容斥原理

Inclusion and Exclusion Principle (IEP)

鸽巢原理

群论

抽象代数基础

线性规划

考试复习

每年题会有一道难的,其他基本都是套路。

排列组合

看前面的。

母函数与递推

递推方程标准求解过程

找递推关系

找递推关系,算初始值

例:已知$G(X)$分式表示,用长除法计算初始值。

可知:$a_{0}=1, a_{1}=1, a_{2}=2, a_{3}=3, a_{4}=4, a_{5}=5,a_{6}=7, a_{7}=8, a_{8}=10, \cdots$

特征多项式

写出特征多项式:$C(x)=x^{k}+C_{1} x^{k-1}+\cdots+C_{k-1} x+C_{k}$

按根分类处理

无重根

无重根:$C(x)=\left(x-a_{1}\right)\left(x-a_{2}\right) \cdots\left(x-a_{k}\right)$

最后得到解的形式为:

$\color{red}a_{n}=l_{1} a_{1}^{n}+l_{2} a_{2}^{n}+\cdots+l_{k} a_{k}^{n}$

实数$k$重根

对于任意一个实数$k$重根,一个有$k$个待定系数。解的形式为:

$\color{red}a_n=\left(A_{0}+A_{1} n+\cdots+A_{k-1} n^{k-1}\right) \alpha_{1}^{n}$

例:$S_{n}-3 S_{n-1}+3 S_{n-2}-S_{n-3}=0$,初始值$S_{0}=0, S_{1}=1, S_{2}=3$。

特征方程为$m^{3}-3 m^{2}+3 m-1=(m-1)^{3}=0$。

解的形式为:$S_{n}=\left(A+B n+C n^{2}\right)(1)^{n}=A+B n+C n^{2}$

代入$S_0,S_1,S_2$即可。

或:$\color{red}a_n=\left[A_{0}+A_{1}\left(\begin{array}{c}n \\ 1\end{array}\right)+A_{2}\left(\begin{array}{c}n \\ 2\end{array}\right)+A_{3}\left(\begin{array}{c}n \\ 3\end{array}\right)+\ldots+A_{k-1}\left(\begin{array}{c}n \\ k-1\end{array}\right)\right] \alpha_{1}^{n}$、

注:$\left(\begin{array}{c}n \\ 3\end{array}\right)=n(n-1)(n-2)/6$,当$n=0,1,2$时,该项为0。可以简化计算。

例:设$S_{n}=A+B n+\cfrac{1}{2 !} C n(n-1)+\cfrac{1}{3 !} D n(n-1)(n-2)$。

$n=0$ 时,$\quad S_{0}=A=0$
$n=1$ 时,$ \quad S_{1}=A+B=1, \quad \therefore B=1$
$n=2$ 时,$ \quad S_{2}=2 B+C=5, \quad \therefore C=3$
$n=3$ 时,$\quad S_{3}=3 B+3 C+D=14, \quad \therefore D=2$

共轭复根

对于任意一个共轭复根,解的形式为:

$\color{red}a_n=A \rho^{n} \cos n \theta+B \rho^{n} \sin n \theta$

例:给定$\boldsymbol{a}_{n}=\boldsymbol{a}_{n-1}-\boldsymbol{a}_{n-2} $,$\boldsymbol{a}_{1}=1, \boldsymbol{a}_{2}=0$。

特征方程$x^{2}-x+1=0$。

可得共轭解为,$x=\cfrac{1 \pm \sqrt{-3}}{2}=\cos \left(\cfrac{\pi}{3}\right)+i \sin \cfrac{\pi}{3}=e^{\pm \cfrac{\pi}{3} i}$

故,$\rho=1,\theta=\cfrac{\pi}{3}$。

所以:$a_{n}=A \cos \cfrac{n \pi}{3}+B \sin \cfrac{n \pi}{3}$,代入$a_1,a_2$求解$A,B$即可。

非齐次递推关系

例:$a_{n}-a_{n-1}-6 a_{n-2}=5 \cdot 4^{n}, \quad a_{0}=5, a_{1}=3$

非齐次特解 $\alpha=c \cdot 4^{n} .$ 齐次通解 $\beta_{n}-\beta_{n-1}-6 \beta_{n-2}=0$

若非齐次解和齐次解形成重根,则非齐次解对应更高的重度,即起始更高次多项式

例:方砖1*1,长砖1*2,给1*n的路铺路面,求所有方案的总砖数

递推关系:$\boldsymbol{b}_{n}=\boldsymbol{b}_{n-1}+\boldsymbol{a}_{n-1}+\boldsymbol{b}_{n-2}+\boldsymbol{a}_{n-2}=\boldsymbol{b}_{n-1}+\boldsymbol{b}_{n-2}+\boldsymbol{a}_{n}$。
即:$b_{n}-b_{n-1}-b_{n-2}=a_{n}$

$b_n$的形式(特解+通解):$(A n) \alpha^{n}+(C n) \beta^{n}+B \alpha^{n}+D \beta^{n}$
即:$(A n+B) \alpha^{n}+(C n+D) \beta^{n}$

直接代入求解较为复杂。利用递推关系 + 系数恒等来求解系数

$\boldsymbol{b}_{n} = (A n+B) \alpha^{n}+(C n+D) \beta^{n}$
$=\boldsymbol{b}_{n-1}+\boldsymbol{b}_{n-2}+\boldsymbol{a}_{n}$
$=(A(n-1)+B) \alpha^{n-1}+(C(n-1)+D) \beta^{n-1}$
$+(A(n-2)+B) \alpha^{n-2}+(C(n-2)+D) \beta^{n-2}$
$+\frac{1}{\sqrt{5}}\left(\alpha^{n+1}-\beta^{n+1}\right)$

利用恒等式求解系数$A$:$A n \alpha^{n}=A(n-1) \alpha^{n-1}+A(n-2) \alpha^{n-2}+\frac{1}{\sqrt{5}} \alpha^{n+1}$

得:$A \alpha+2 A=\frac{1}{\sqrt{5}} \alpha^{3} \quad A=\frac{1}{5} \alpha^{2}$

卡特兰数

例:在图书馆一共6个人在排队,3个还《面试宝典》一书, 3个在借 《面试宝典》一书,图书馆此时没有了面试宝典了, 求他们能顺利完成借书的排队方案数。

180。$C_3\times 3!\times 3!$。不要忘了3人借/还的排列数。

指数型母函数@

求解带约束的可重排列

例1: 求由2个a, 1个b,2个c组成的不同排列总数。

不同的排列总数为 $n=\frac{5 !}{2 ! 2 ! !}=30$

例2:由1,2,3,4四个数字组成的五位数中,要求数1出现次数不超过2次,但不 能不出现; 2出现次数不超过1次; 3出现 次数可达3次,也可以不出现; 4出现次数为偶数。求满足上述条件的数的个数。

设满足上述条件的r位数为 $a_{r},$ 序列 $a_{1}, a_{2}, \cdots a_{10}$ 的指数型母函数为
$\begin{aligned} G_{e}(x)=&\left(\frac{x}{1 !}+\frac{x^{2}}{2 !}\right)(1+x)\left(1+\frac{x}{1 !}+\frac{x^{2}}{2 !}+\frac{x^{3}}{3 !}\right)\left(1+\frac{x^{2}}{2 !}+\frac{x^{4}}{4 !}\right) \\=&\left(x+\frac{3}{2} x^{2}+\frac{1}{2} x^{3}\right)\left(1+x+x^{2}+\frac{2}{3} x^{3}+\frac{7}{24} x^{4}+\frac{1}{8} x^{5}+\frac{x^{6}}{48}+\frac{x^{7}}{144}\right) \\=& x+\frac{5}{2} x^{2}+3 x^{3}+\frac{8}{3} x^{4}+\frac{43}{24} x^{5}+\frac{43}{48} x^{6}+\frac{17}{48} x^{7}+\frac{1}{288} x^{8}+\frac{1}{48} x^{9}+\frac{1}{288} x^{10} \\=&\frac{x}{1 !}+5 \frac{x^{2}}{2 !}+18 \frac{x^{3}}{3 !}+64 \frac{x^{4}}{4 !}+215 \frac{x^{5}}{5 !}+645 \frac{x^{6}}{6 !}+1785 \frac{x^{7}}{7 !} \\&+140 \frac{x^{8}}{8 !}+7650 \frac{x^{9}}{9 !}+12600 \frac{x^{10}}{10 !} \end{aligned}$
由此可见满足条件的5位数共215个。

N位序列@

容斥原理

容斥原理

或:

欧拉函数

容斥法求不定方程

例 求不定方程 $x_{1}+x_{2}+x_{3}=15,$ 附加约束为0 $\leq x_{1} \leq 5,0 \leq x_{2} \leq 6 ; \quad 0 \leq x_{3} \leq 7$, 求整数解的数目。

解: 用容斥原理去掉$x_{1} \geq 6$ $x_{2} \geq 7$ $x_{3} \geq 8$ 的一系列解。

对于 $x_{1}+x_{2}+\ldots+x_{n}=r$ 的非负整数解的个数为 $\mathrm{C}(n+r-1, r)$
没有约束情况下的不定方程 $x_{1}+x_{2}+x_{3}=15$ 的非负整数解的个数为

设A1为 $x_{1} \geq 6$ 的解, $\quad y_{1}+6+x_{2}+x_{3}=15$
$|\mathrm{A} 1|=\mathrm{C}(9+3-1,9)=\mathrm{C}(11,2)$
设A2为 $x_{2} \geq 7$ 的解 $, \quad x_{1}+y_{2}+7+x_{3}=15$
$|\mathrm{A} 2|=\mathrm{C}(8+3-1,8)=\mathrm{C}(10,2)$
设A3为 $x_{3} \geq 8$ 的解, $x_{1}+x_{2}+y_{3}+8=15$
$|\mathrm{A} 3|=\mathrm{C}(7+3-1,7)=\mathrm{C}(9,2)$
A1nA2: $y_{1}+6+y_{2}+7+x_{3}=15 \mid$ A $1 \cap A 2 \mid=C(2+3-1,2)=C(4,2)$
A1\capA3: $y_{1}+6+x_{2}+y_{3}+8=15 \mid$ A $1 \cap A 3 \mid=C(1+3-1,1)=C(3,1)$
A2\capA3: $x_{1}+y_{2}+7+y_{3}+8=15 \mid$ A2 $\cap$ A3 $\mid=1$
$\mathrm{A} 1 \cap \mathrm{A} 2 \cap \mathrm{A} 3: y_{1}+6+y_{2}+7+y_{3}+8=15 ; \mid \mathrm{A} 1 \cap \mathrm{A} 2 \cap \mathrm{A} 3=0$
$\mid \overline{\mathrm{A} 1} \cap \overline{\mathrm{A} 2} \cap \mathrm{A} \overline{3}=\mathrm{C}(17,2)-\mathrm{C}(11,2)-\mathrm{C}(10,2)-\mathrm{C}(9,2)$

错排

母函数:

错排公式:

容斥法理解错排:($A_i$表示元素$i$在原位置,每个元素都不在原来位置的排列数) $$ \begin{array}{r} \color{red}\left|\overline{A_{1}} \cap \overline{A_{2}} \cap \ldots \cap \overline{A_{n}}\right|=n !-C(n, 1)(n-1) ! +C(n, 2)(n-2) !-\cdots-\pm C(n, n) 1 ! \end{array}\\=n !\left(1-\frac{1}{1 !}+\frac{1}{2 !}-\cdots \pm \frac{1}{n !}\right) $$ > 例9 在8个字母A,B,C,D,E,F,G,H的全排列中,求使 A,C,E,G四个字母不在原来位置上的排列数目。 > > > 解: 8个字母的全排列中, $\hat{>} \mathrm{A}_{\mathrm{A}}, \mathrm{A}_{\mathrm{C}}, \mathrm{A}_{\mathrm{E}}, \mathrm{A}_{\mathrm{G}}$ 分别表示$\mathrm{A}, \mathrm{C}, \mathrm{E}, \mathrm{G}$ 在原来位置上的排列,则错排数为: > > $$ > \begin{aligned} > \left|\overline{A_{1}} \cap \overline{A_{2}} \cap \overline{A_{3}} \cap \overline{A_{4}}\right|=& 8 !-C(4,1) 7 !+C(4,2) 6 ! \\ > &-C(4,3) 5 !+C(4,4) 4 ! \\ > =& 24024 > \end{aligned} > $$ ### 广义容斥原理

考到的概率较小。公式理解性记忆。

例 某校有 12 个教师,已知教数学的有 8 位,教物理的 有 6 位,教化学的 5 位; 数、理 5 位,数、化 4 位,理、 化 3 位 $;$ 数理化 3 位。问教其他课的有几位? 只教一门的有几位? 正好教两门的有几位?

解 :令教数学的教师属于 $A_{1},$ 教物理的属于 $A_{2},$ 教化学的 属于$A_3$ 则 $\mathrm{P}_0=12$,

故 教其他课的老师数为:

恰好教一门的教师数:

恰好教两门的老师数为:

棋盘多项式

今$r _{\mathrm{k}}$ (C) 表示k个棋子布到棋盘C上的方案数

定义:设C为一棋盘,称 $\mathrm{R}(\mathrm{C})=\sum_{\mathrm{k}=0}^{\mathrm{n}} \mathrm{r}_{\mathrm{k}}(\mathrm{C}) \mathrm{x}^{\mathrm{k}}$ 为C的棋盘多项式。

规定 $R(空)=\mathrm{r}_{0}(\mathrm{C})=1,$ 包括C=Ø时。

性质1:设$Ci$是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘;$Ce$是仅去掉 该格子后的棋盘,则

对于棋盘多项式:

性质2:如果 $C$ 由相互分离的 $C_{1}, C_{2}$ 组成 即 $C_{1}$ 的任一格子所在的行和列中都没有 $C_{2}$ 的格子。则有:

有禁区的棋盘

定理:设 $r_{i}$ 为 $i$ 个棋子布入禁区的方案数, $i$ $=1,2,3, \cdots, n$。有禁区的布子方案数(即禁区内不布子的方案数 ) 为

先求R(禁区),从而获得 $r_{i}$,然后套公式容斥即可。

鸽巢原理

鸽巢题出的较少。因为一大片人不会做。

核心是找到有多少个鸽子巢(等价类的数目)。

套娃反证法


例:共有25只队伍参加足球联赛,进行单循环比赛(即所有参加比赛的队均能相遇一次, 一场比赛结束另一场比赛才可以开始), 如果在比赛过程中的某一天每支队伍已经比赛完的场次都大手19 $)$ 请证明存在其中的5只队伍,他 门之间的比赛已经全部结束。

设与team1比赛过的球队集合为$A_1$,则

在$A_1$中取任意1只球队记为team2。
设与team2比赛过的球队集合为$A_2$,则(结合容斥原理)

在$A_1\cap A_2$中取任意1只球队记为team3。
设与team3比赛过的球队集合为$A_3$,则

同理,在$A_1\cap A_2\cap A_3$中取任意1只球队记为team4。
设与team4比赛过的球队集合为$A_4$,则

在$A_1\cap A_2\cap A_3\cap A_4$可取到1只球队记为team5。故原命题得证。

群论

Burnside引理

共轭类:置换群Sn中,属 $(1)^{\mathrm{C}_1}(2)^{\mathrm{C}_2} \cdots(\mathrm{n})^{\mathrm{C_n}}$ 共轭类的元素的个数为

$(k)^{C_k}$表示$k$阶循环有$C_k$个。

k不动置换类(Stabilizer):$Z_k$。置换群中使得点$k$不动的置换所组成的子群。

等价类/轨道(Orbit):$E_k$。若存在置换$p_i$使k变为l,则称k和l元素属于同一个等价类,数k所属的等价类记为$E_k$。

Burnside引理/轨道定理:设 $G = \{ a 1 , a 2 , . . . a g \}$ 是目标集 $[ 1 , n ] $ 上的置换群。每个置换都写成不相交循环的乘积。G将$[1,n]$划分成$l$个等价类.$c_1(a_k)$是在 置换$a_k$的作用下不动点的个数。

$|E_k|$是轨道长度,$|Z_k|$是$k$不动的置换数,$|G|$是所有置换个数。

$c_{1}\left(a_{j}\right)$是置换$a_j$中1阶循环/不动点的个数。$l$是$G$中元素的等价类的个数(即本质不同的元素的个数)。

Polya定理

考试第4道题一定是Polya定理。

正多面体的转动群。

Pólya定理:设 $G=\left\{\mathrm{P}_{1},\mathrm{P}_{2}, \ldots, \mathrm{P}_{\mathrm{g} }\right\}$ 是n个对象的一个置换群,$C(P_k)$是置换$P_k$的循环的个数,用$m$种颜色对$n$个对象着色,着色方案数为

Burnside基于目标集(即所有的涂色方案数);Polya基于对象(即点集/涂色问题中的面集)。

循环的个数就是数括号有几个(所有阶的循环都算)。


例题:正四面体群。

考试时的写法


例题:正六面体群。

正多面体群

正四面体:顶点4个,面4个,棱6条,均为等边三角形

转动群 顶点 个数
不动 (1)4 (1)4 (1)6 1
顶点-面心 ±120度 (1)(3) (1)(3) (3)2 8
棱心-棱心 180度 (2)2 (2)2 (1)2(2)2 3

正六面体:顶点8个,面6个,棱12条,均为正方形

转动群 顶点 个数
不动 (1)8 (1)6 (1)12 1
面心-面心, ±90度 (4)2 (1)2(4) (4)3 6
面心-面心,180度 (2)4 (1)2(2)2 (2)6 3
棱心-棱心,180度 (2)4 (2)3 (1)2(2)5 6
空间对角线±120度 (3)2(1)2 (3)2 (3)4 8

正八面体:顶点6个,面8个,棱12条,均为等边三角形

转动群 顶点 个数
不动 (1)6 (1)8 (1)12 1
顶点-顶点 ±90度 (1)2(4) (4)2 (4)3 6
顶点-顶点 180度 (1)2(2)2 (2)4 (2)6 3
棱心-棱心 180度 (2)3 (2)4 (1)2(2)5 6
面心-面心 ±120度 (3)2 (3)2(1)2 (3)4 8

正十二面体:顶点20个,面12个,棱30条,均为正五边形

转动群 顶点 个数
不动 (1)20 (1)12 (1)30 1
面心-面心±72,±144度 (5)4 (1)2(5)2 (5)6 24
棱心-棱心180度 (2)10 (2)6 (1)2(2)14 15
顶点-顶点±120度 (1)2(3)6 (3)4 (3)10 20

正二十面体:顶点12个,面20个,棱30条,均为等边三角形

转动群 顶点 个数
不动 (1)12 (1)20 (1)30 1
顶点-顶点±72,±144度 (1)2(5)2 (5)4 (5)6 24
棱心-棱心180度 (2)6 (2)10 (1)2(2)14 15
面心-面心±120度 (3)4 (1)2(3)6 (3)10 20

足球:顶点60个,面32个,棱数90条,20个正六边形,12个正五边形

转动群 顶点 个数
不动 (1)60 (1)32 (1)90 1
五边形面心-五边形面心±72,±144度 (5)12 (1)2(5)6 (5)18 24
六边形面心—六边形面心±120度 (3)20 (1)2(3)10 (3)30 20
正六边形棱中-棱180度(这种棱有30条) (2)30 (2)16 (1)2(2)44 15

欠角和方法

欧拉定理:顶点数$v$,面数$f$,边数$e$满足以下关系

定义:凸多面体与一个顶点相关的面角之和与360度的差称为该顶点的欠角。

定理:凸多面体各顶点欠角的和为720度

平面多边形内角和等于$(V-2)\times 180$度。

母函数型Pólya定理

考试一定会考到这种程度。

$\mathrm{Sk}=\left(\mathrm{b}_{1}^{\mathrm{k}+\mathrm{b}_{2}} \mathrm{k}+\cdots+\mathrm{b}_{\mathrm{m}}^{\mathrm{k}}\right), \mathrm{k}=1,2 \cdots \mathrm{n}$

例:

注:这个例题中的P(G)已经提前除以8了。

用组合数求系数。


多元素涂色


火柴例题:(考题难度比这个稍微复杂一点)

单纯形法

建议用铅笔答题。

线性规划若有解,则必在某个顶点上取得最优值。
而一个可行解X对应于一个顶点的充要条件是其非0分量对应的m个A的列向量线性无关

也就是非基变量就等于0(零元)。基变量才是非零元。

化为标准型

写出标准型就能拿分。

标准形式特征:
⑴.目标函数统一为求极大值,也可以用求极小值;
⑵.所有约束条件(非负条件除外)都是等式,右端常数项为非负;
⑶.所有变量为非负。

  • 目标函数统一为求极大值
  • 右端常数项$b_i\geq 0$
  • 所有变量$x_j\geq 0$
    • 若存在无约束变量,令$x_j=x_a-x_b$用两个新变量$x_a,x_b\geq 0$代替
  • 所有约束条件(非负条件除外)都是等式
    • 加入新变量解约束
      • $\geq$还需要加入人工变量凑成基

引入大M

单纯形表

$C_j$是优化的目标函数的系数表。

判断是否最优

检验数:$\lambda_j=c_j-C_BP_j$。

迭代到所有检验数都不大于零时获得最优。

Bland’s Rule:找到一个$\lambda_j>0$就可以提前终止计算,确定对应变量为入基变量,换下一张表。

考试时找到一个,剩下的$\lambda$就不用求了。

验算

最后的结果代回到原约束中,看是否成立。

二阶段法

编程专用。

如果加入了人工变量。则需要先优化人工变量到全部等于0。

若人工变量始终不能转换为非基变量(值为0),则原问题无可行解。

检验数全负,但是基里面仍含有人工变量。

但是这样相当于解了两道题。

大M法

大M法: 即假定人工变量在目标函数中的系数为M (任意大正数),如果是求极大值,需加-M; 如果是求极小值,需加M。如基变量中还存在M,就不能实现极值。