回到最简单的情形。 * * * 考虑两个符号 a 和 b。两物并立曰 “方”。为了往前走，就得有个 “法”。在 “顺序” 的上下文里，只能交换两者的位置：a b ~ b a。此处置换扮演 “法则” 的角色（尽管这里看不出“去除不直”，但够得上简单直接）。注：“法” 似乎总是联系着某种 “运动” 或 “变化”。 . 从“几何”角度看，二元置换相当于做一个(镜面) 反射 ，记作 R。从另一个角度看，从 a b 到 b a 构成一个(二元) 循环 ，记作 C。换句话说，在二元置换中 R = C。这两个操作都有 “ 整体性 ”，即所有元素都离开了原本的位置。 . 关于二元置换只能 “挖掘” 这么多？应该还看到，这里面没有多余的东西，但已经涵盖了 “方” 和 “法”！这是否预示着二元置换 “涵盖”* 了多元置换？回答是否定的！（注：星号是指用 R 和 C 得到多元置换的全部排列）。 . 考虑三个符号 a, b, c。之前已经分析了三元置换：从任何一个三元排列出发，先做一个反射，然后各自做循环，这样就可以得到三元置换的全部排列（6个）。从表面上看，的确只用 R 和 C 就得到了全部的排列。但是在三元置换中，R 的整体性存在“缺陷”：位于中间的符号没有离开原本的位置！换句话说，这里似乎有个奇偶性的问题。又或者，三元置换的反射，隐含了一个“固定” 的操作，记作 F。 . 现在考虑如何得到四元置换的全部排列（24个）。先做一个反射，再各自做循环，这样只得到 8 个排列。从这里去除互相反射的两个排列，余下的6个排列各自做一个反射，得到6个排列。此时共有 14 个排列。新得的6个排列，各自循环，可派生出 24个排列。此时的计数为 8 + 24 = 32。其中有重复的排列... . 不妨具体考察一下。 R: a b c d ~ d c b a C: a b c d ~ b c d a ~ c d a b ~ d a b c C: d c b a ~ c b a d ~ b a d c ~ a d c b 以上是第一轮 RC 操作(一个R两个C)。 . 仔细观察：两个C 序列中，互为反射的有两组(4个排列)！排除两个C序列的奇数组，余下的4个排列各自做一个反射： R: b c d a ~ a d c b; d a b c ~ c b a d R: c b a d ~ d a b c; a d c b ~ b c d a 仔细观察可知，以上两个 R组 的输出端分别是对方组的输入端！换句话说，产生的排列没有跑出第一轮的RC操作。一方面，这体现出 RC 操作形成了一个封闭的系统 (这是有意思的地方)；另一方面，这体现出 RC 操作不足以得到四元置换的全部排列。 . 好在三元置换提示，还有个“固定”操作。经过演算发现，可以在三元置换的基础上，通过迭代获得四元置换的全部排列。一般地，对于 n 元置换，通过嵌套的 RCF 操作，即可获得其全部排列。(具体算法保留 :) . 关于置换暂时就探索到这里。这里的启发是： 全排列的数量非常庞大，每个排列中元素的位置完全随意，可是全部的排列却是有结构的 。
有 n 个不同球，从中选择 m 个，不考虑选择的顺序，可以列出多少种选择？这问题是简单的，若 n 阶乘表示为： fact(n) ，且把问题记作 C(n,m) 。那么： C(n,m) = fact(m)/fact(n)/fact(n-m) 。当用程序直接列出所有可选，虽然不难，可以直接想到排列加剔除的方式，然而这样的程序显然是非常的丑陋的。应该得有好点的算法去解决它：对球编号 1:n ，问题等价从 1:n 中选择 m 个不同的数字。假设 C(n,m-1) 的排列已知，则每一种排列 {a,b,c,…x} 衍生 C(n,m) 的排列 {a,b,c…x,y} ，其中 y 为 (x+1):n 中的任意，共衍生排列 n-x 项。注：要求每列的数字顺序为增序，即 abc… 。 MATLAB 程序描述： function re=getspre(n,m) re=(1:n)'; while (size(re,2)m) tmp= ]; end re=tmp; end end getspre(5,3) ans = 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 算法要求每个排列是单调递增序列，则令所有选择无重复，对于任意可能出现在 C(n,m) 的序列必然有 C(n,m-1) 的源所以选择没有遗漏。算法结构描述排列数量是以如下方式增长的： ，共有求 和号 m-1 个。 例： 。 另，对于问题：有 n 个编号不同的球，可以有多少种不同的顺序排列方式？记为 P(n) 。那么列出 P(n) 的全部排列可以有很多种方式列出，但程序的结构应力求用更少的时间复杂度，以及更少的内存资源。下面是一个方式，用 MATLAB 描述： function H=sepn(n) if (n==1) H=1; return ; end regu=sepn(n-1); H= ; for i=2:n tx=x(i:i+n-2); H= ; end H= ; L=reshape(ones(size(regu,1),1)*(n:-1:1), ; end sepn(3) ans = 1 2 3 2 1 3 3 1 2 1 3 2 2 3 1 3 2 1 假设 P(n-1) 的排列已知，序列 T={1,2,…n,1,2,…n} ，那么做序列 Xi={T(i),T(i+1),T(i+2)…T(i+n-2)}, 其中 i=1:n 。对所有 Xi 序列进行 P(n-1) 排列，所有得到的序列末位最后补上 T(i+n-1) 。算法不需要任何多余的判断和剔除，而且存储结构上也不需要多余的资源，最后的到的数组所有位在整个过程中都只赋值一次。方式用 C++ 或者 JAVA 来做会看到更简易结构： package amk2; public class funcs { public int px ; public int n ; public int T ; public funcs( int a){ int i; T =1; for (i=1;i=a;i++) T *=i; n =a; px = new int ; }; public void exe() { int i,j,t; int k; int ln=1; int ; px =0; //******************** M ************************* for (k=1;k n ;k++) { for (i=0;i=k;i++) { tmp =i; tmp =i; } for (t=1;t=k;t++) { for (i=0;iln;i++) { for (j=0;jk;j++) px =tmp +t]; px =t-1; } } for (i=0;iln;i++) px =k; ln*=(k+1); } //******************** M *************************** for (i=0;i T ;i++) { for (j=0;j n ;j++) { System. out .print( px ); System. out .print( ' ' ); } System. out .print(( char )0x0d); } } } 程序中的 M 段描述的就是这个算法结构。 funcs abc = new funcs(3); 则： 0 1 2 1 0 2 1 2 0 2 1 0 2 0 1 0 2 1 最后若是问题是所有 n 个编号的球，取出 m 个排列，允许重复？有上述的两个接口程序，得到这个问题的程序解答很容易，这儿就不列出了。 ************************************************************************************** 在做 P(n) 时，曾想过用第 n 数插入到所有 P(n-1) 的排列的各个间隔中，很容易理解，问题是这样的结构需要链表，不是一个好的方式。常常有些有意思的东西，只是抬笔很麻烦，好在昨夜失眠，还是写点什么好了。
上次的日记出了一个数学题（ http://www.sciencenet.cn/m/user_content.aspx?id=49508 ），我找到答案了！！！看来还是要我自己动手才行，pose到网络上也没有人能帮我，汗！！！查了N多文献，真不容易啊，解答很难看懂，请各位见谅了，因为我也不知道怎么用简单的语言把它描述出来。 我把题目稍微变一下： 有很多个盒子，每个盒子分别标上0、1、2、3、4、等等的标号。有N个完全相同的小球，我任意的放进这些盒子里。最后，我要把每个盒子里的球的数量乘以盒子的标号，然后把他们加起来要等于M. （N和M为正整数） 问，一共有多少种放法？ （求出关于N和M的表达式） 注意，题目稍微变了一点点，上次的标号是从1开始的，这次标号是从0开始的，但是这个并没有多少影响，本质还是一样。两个题目有什么关系就留个读者自己思考了。 当M=N的时候，这个问题就是等同于有多少种方案把M分成任意个正整数之和。例如，当M=4时，有5种分配方案，M=1+1+1+1, M=2+1+1, M=2+2, M=3+1, M=4。这个问题是一个数学上非常有名的问题，最初由欧拉提出来的（我和欧拉居然想到了同样的问题，哈哈哈），请参考G. E. Andrews, 《The Theory of Partitions》 Addison-Wesley出版社，1976。在M小于500的时候，都有表可以查，这个在一本书里《Handbook of Mathematical Functions》, edited by M.Abramowitz and I. A. Stegun (Dover, New York, 1972), Chap. 24。了精确的解析解可以在这里找到：H. Rademacher, Proc. Natl. Acad. Sci. Washington 23, 78 (1937)。但是这个精确解析解并不好用，Hardy和Ramanujan给了一个很好用的近似解析解（G. H. Hardy and S. Ramanujan, Proc. London Math. Soc. 17, 75 (1918)） p(m)~exp / 其中c=sqrt(2/3)Pi. 当M大于N的时候，就要对上式有一点点修正，（请看P. Erdos and J. Lehner, Duke Math. J. 8, 335 (1941)） P(m)~p(m)exp /c] 其中 x(M)=cN/(2sqrt(M))-ln . 可以看到当sqrt 远小于N的时候，p(m)和P(m)几乎相等。
标签: 排列
