思维之海

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

组合数学

组合数学(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$ 个空)。

模型

放球模型

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模板

本次project一定要找好方向~

Knuth的第三卷书:

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


提交内容

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

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

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

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

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

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

全排列生成算法调研

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

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

字典序法 Lexicographic permutation generation

与组合数学课上介绍的算法步骤略有不同。先反转,再交换。

算法大约分为三步:

  • 从右向左,找到第一个下降的位置 i
  • 反转 i 之后的所有元素
  • i 和 其后缀中比它大的最小元素 进行交换
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;
}

递增进位制法

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

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;
}

递减进位制法

与递增进位制数的机制相似,只是数位发生反转,也就是进位方向调整一下即可。对应到代码上只需要修改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;
}



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

其它全排列算法

循环位移法

算法效率

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

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

母函数

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

母函数的定义

母函数 / 生成函数(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)。

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

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

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

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


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

设计母函数:

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


母函数练习题

计数法则

乘法法则:$n$ 个计数对象可以划分为 $i$ 个对象和 $n-i$ 个对象

加法法则:$n$ 个计数对象所有的划分策略累加

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

拉马努金,三大笔记本。

母函数思考题

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

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

母函数的性质

二项式定理

$\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$,

Hanoi塔

Fibonacci数

Fibonacci思考题

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