📄 1_5.htm
字号:
<html><head><title>Untitled Document</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"><style ttype="text/css"><!-- .overline{text-decoration:overline}--></style></head><body bgcolor="#FFFFFF"><h1>1.5全排列的生成算法</h1><p><b>全排列的生成算法</b>就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 </p><p>这里介绍全排列算法四种：<br> (A)字典序法<br> (B)递增进位制数法<br> (C)递减进位制数法<br> (D)邻位对换法 </p><h4>1.5.1字典序法</h4><p>对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。 </p><p><b>[例]</b>字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。</p><p><b>[注意]</b> 一个全排列可看做一个字符串，字符串可有前缀、后缀。</p><p>1）<b>生成给定全排列的下一个排列</b> 所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。 </p><p><b>[例]</b>839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。 </p><p><a href="1_5pic/5_1.zip">下载算法演示</a></p><h4>1.5.2递增进位制数法</h4><p>1)由排列求中介数</p><p>在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。<br> 在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。 右端位逢2进1，右起第2位逢3进1，…， 右起第i位逢i+1进1，i=1,2,…,n-1. 这样的中介数我们称为递增进位制数。 上面是由中介数求排列。</p><p>由序号（十进制数）求中介数（递增进位制数）如下：<br> m=m<sub>1</sub>,0≤m≤n!-1<br> m<sub>1</sub>=2m<sub>2</sub>+k<sub>n-1</sub>,0≤k<sub>n-1</sub>≤1<br> m<sub>2</sub>=3m<sub>3</sub>+k<sub>n-2</sub>,0≤k<sub>n-2</sub>≤2<br> ……………<br> m<sub>n-2</sub>=(n-1)m<sub>n-1</sub>+k<sub>2</sub>,0≤k<sub>2</sub>≤n-2<br> m<sub>n-1</sub>=k<sub>1</sub>,0≤k<sub>1</sub>≤n-1<br> p<sub>1</sub>p<sub>2</sub>…p<sub>n</sub>←→(k<sub>1</sub>k<sub>2</sub>…k<sub>n-1</sub>)↑←→m </p><p>在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。 </p><p>为方便起见，令a<sub>i+1</sub>=k<sub>n-1</sub>，i=1,2,…,n-1<br> (k<sub>1</sub>k<sub>2</sub>…k<sub>n-1</sub>)↑=(a<sub>n</sub>a<sub>n-1</sub>…a<sub>2</sub>)↑ <br> a<sub>i</sub>：i的右边比i小的数字的个数<br> 在这样的定义下，<br> 有839647521←→(67342221)↑<br> (67342221)↑+1=(67342300)↑←→849617523<br> 6×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1 =279905 </p><p>由(a<sub>n</sub>a<sub>n-1</sub>…a<sub>2</sub>)↑求p<sub>1</sub>p<sub>2</sub>…p<sub>n</sub>。</p><p>从大到小求出n,n-1,…,2,1的位置</p><p>_ ... _ n _ _ …_ (a<sub>n</sub>个空格)<br> n的右边有a<sub>n</sub>个空格。<br> n-1的右边有a<sub>n-1</sub>个空格。<br> …………<br> 2的右边有a<sub>2</sub>个空格。<br> 最后一个空格就是1的位置。 </p><p><a href="1_5pic/5_2.zip">下载算法演示</a></p><h4>1.5.3递减进位制数法</h4><p>在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。 </p><p>(a<sub>n</sub>a<sub>n-1</sub>…a<sub>2</sub>)↑→(a<sub>2</sub>a<sub>3</sub>…a<sub>n-1</sub>a<sub>n</sub>)↓<br> 839647521→ (12224376)↓<br> <img src="1_5pic/image002.gif" width="148" height="48"></p><p>(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989<br> [注意]求下一个排列十分容易 </p><h4>1.5.4邻位对换法</h4><p>递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。 </p><p>这个算法可描述如下：<br> 对1—n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1—n的n个排列。<br> 对1—n-1的每一个奇排列，n从左到右插入n个空档，生成1—n的n个排列。<br> 对[2,n]的每个数字都是如此。 </p><p><a href="1_5pic/5_4.zip">下载算法演示</a></p><table width="70%" border="1" cellspacing="0" cellpadding="1" align="center"> <tr> <td colspan="5"> <div align="center">839647521</div> </td> </tr> <tr> <td width="16%"> <div align="center"></div> </td> <td width="14%"> <div align="center">字典序法</div> </td> <td width="22%"> <div align="center">递增进位制法</div> </td> <td width="19%"> <div align="center">递减进位制法 </div> </td> <td width="29%"> <div align="center">邻位对换法 </div> </td> </tr> <tr> <td width="16%"> <div align="center">下一个</div> </td> <td width="14%"> <div align="center">839651247</div> </td> <td width="22%"> <div align="center">849617523</div> </td> <td width="19%"> <div align="center">893647521</div> </td> <td width="29%"> <div align="center">836947521</div> </td> </tr> <tr> <td width="16%"> <div align="center">中介数</div> </td> <td width="14%"> <div align="center">72642321↑</div> </td> <td width="22%"> <div align="center">67342221↑</div> </td> <td width="19%"> <div align="center">12224376↓</div> </td> <td width="29%"> <div align="center">10121372↓</div> </td> </tr> <tr> <td width="16%"> <div align="center">序 号</div> </td> <td width="14%"> <div align="center">297191</div> </td> <td width="22%"> <div align="center">279905</div> </td> <td width="19%"> <div align="center">340989</div> </td> <td width="29%"> <div align="center">203393 </div> </td> </tr></table><p> </p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -