||
[注:下文是群邮件的内容,标题是抬头。有较大的启发性。]
对排列分组的动机是什么?
* * *
初次接触排列时立刻会意识到,少数几个字母的排列在数量上可以相当庞大。而在研究任何问题时,从各种具体情形摸索规律是很自然的 (即“形而上”)。如果要得到所有可能的排列,可以有若干办法,而最好的办法是涉及的 “操作” 最少。
.
在这之前,我想到全部的排列可能包含若干模式 (从图案角度看),从而形成 “自然的” 分组。为此我在 Matlab 里做了个实验:P= perms([1: 5]); figure; image (P)。现在倾向于放弃这个想法,而转到 “最少操作” 上来。
.
先列出 1, 2, 3 的全排列 (借助 Matlab):
P =
3 2 1
3 1 2
2 3 1
2 1 3
1 2 3
1 3 2
.
最简单的,可以按 “反射” (记作 R) 分组。比如,第1行和第5行:R(1) = 5, R(5) = R^2(1) = 1;R^2(5) = R(1) = 5。再比如,第2行和第4行:R(2) = 4,R(4) = R^2(2) = 2。这样按反射操作就分为三组:(1, 5), (2, 4), (3, 6)。这样的话,前三行可以作为 “种子”,用反射的办法得到其余排列。这个办法的“复杂度”为 [3:1],表示 3个种子 1 个操作。
.
现在把目光放到3个种子上... 先做个调整:第1行和第5行对调(组内调换行的位置不影响复杂度)。
P =
1 2 3
3 1 2
2 3 1
2 1 3
3 2 1
1 3 2
.
仍然取前三行作为种子组。可以看出,它们是循环关系(方括号内的数字指行内元素的位置):[3] ~> [1] ~> [2] ~> [3]。把这个操作记作 C。则有:C(1) = 2, C(2) = 3, C(3) = 1。由此,种子组里又可以选出一个(二级)种子,由它得到种子组。
.
综上,可以从一个(二级)种子出发,经过循环操作 C,得到三个(一级)种子,由它们得到其余排列(后三组内也是循环关系)。总的复杂度是 [1: 2],即一个种子,两个操作。
.
从分组的角度看,1~3 行形成一组,4 ~ 6 行形成一组。两个组都 “服从” 循环关系。所谓(单一)群,就是从单一的对象*出发按单一的操作得到 “全部” 的对象。星号:此处的对象是排列。而 “全部” 意味着封闭性。而且,在同一个(单一)群内,无论从哪个对象出发得到的结果都一样。
.
如果要在操作之间排个顺序,应该是 R, C。从任何一个对象开始,先做一个反射,然后各自做循环,就可以得到全部的排列。注:这是对三元排列而言。
.
总之:对排列分组的动机,很可能只是为了方便地写出全部的排列。由于写出全部的排列显得很麻烦,就希望以最小的麻烦办成事情。而麻烦通常是由于没有规律引起的,于是就可能促使人们从排列中寻找规律,进而发现它。
.
进一步,这里面的思想方法是什么?我把它归结为 “计算” 二字:以最少的符号计之,以最少的操作算之。对于 n 个符号的排列而言,可以记作 P(abc...)。但这只停留在概念的层面的。如果写作 (R, C, abc) 就到达了 “计算” 的层面。 (从abc出发 “呼啦” 一下全有了!)
.
注:昨天拿出 Edwards 的书,页码不少,不知道从何下手。从第一页开始读?好像没那个耐心。从早上到晚上,抽了2包烟,最后选择从 S39 开始读起。以上是即兴写成(不是 “memoir” !)。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-23 16:01
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社