| 不过这里我就不写了，读者有兴趣可以写写。 12.递减进位制数法： 考虑到递增进制法中由于最低位是二进制，而且低位的进制都比较低，在求下一个排列时，中介数加1往往会导致很多的进位，计算比较麻烦，所以有了递减进位，实际上就是将递增进位制的中介数倒过来即可。如342221变成122243.求序号时的公式记住也是倒过来。 ((((k[1]*3) k[2])*4 k[3])*5..k[n-2]*n k[n-1]，其中k[i]就是递减进制中介数，i从1开始表示从左往右数，即数组的序号（对应n -i 1位）。这里的n表示的是原排列的元素个数。 如122243表示为（（（（1*3 2）*4 2）*5 2）*6 4）*7 3 = 4735. 由于低位都是比较高的进制，所以不容易产生进位，求下一个排列非常地简单。 我们看这个例子：122243 1 = 122244.这里我们不需要再进位，而是很方便的计算。122244对应的序号是4736.反过来求出原排列的方法也很简单，先反序得到递增中介数再运算即可。 122244 = 442221(反序) = __ __ __ __ __ __ __ = __ __ 7 __ __ __ __ = __ 6 7__ __ __ __ = __ 6 7 __ 5__ __ = __ 6 7 4 5 __ __ = 3 6 7 4 5 2 1.（读者可以自行练习空格法） 和原来的122243对应的排列3 6 4 7 5 2 1相对比，发现仅仅是4和7交换了位置。我们可以再看看122244 1 = 122245 = 542221（反序）= __ __ __ __ __ __ __ = __ 7 __ __ __ __ __ = __ 7 6 __ __ __ __ = __ 7 6 __ 5 __ __ = __ 7 6 4 5 __ __ = 3 7 6 4 5 2 1. 我们可以发现它仅仅是上一个排列的6和7交换了位置。读者可能发现，如果再加两次，就会有进位，此时排列又更替了。所以，实际上，递减进位制数法的排序采用的就是这种两个相邻元素交换的方式，并且是从右往左单向交换（至于它的数学原理这里就不深究了，有兴趣的读者可以研究一下）。通过递减进位制法也可以得到全排列的算法，相比于递增进位制法较简单。 13.邻位对换法： 我们从递减进制数法从得到启示，递减进制法中的交换是单向的，这导致交换到头是排列会发生更替，如果我们采用双向的交换，便可以不断地交换下去，于是产生了邻位对换法。邻位对换法在找下一个排列的方法上在很多情况下要比字典序算法要快上许多，因为每次的下一个排列只是交换两个相邻的元素，当然缺点是有到左端或者右端时要进行找最大可移动数的弊端，整体上速度和字面序算法差不多。 当然，读者可能还没有理解邻位对换法的概念，下面开始讲解。在讲解之前先介绍数学中的两个概念，不过其实在这节里没有用，下面一节才用到。 定义1：在一个序列中任意两个元素对如果满足a[k] < a[m](k < m)，则称为正序，否则称为逆序。 定义2：如果一个排列中逆序的数目为奇数，则称为奇排列，若为偶数则称为偶排列。 初始的时候，我们假设这个序列是一个升序的序列，而且最小元素至少为1，升序的序列总是偶排列，并且我们设定初始所有数的移动（其实就是交换）的方向均从右向左。 我们给出可移动的概念：如果一个数沿着它的方向的邻位比它小，则称这个数是可移动的。 由这个概念可以知道，1是永远不可移动的，最大的数除非是在两端而且方向指向序列外面，要不一直是可移动的。 我们再规定一个性质：如果一个可移动的数发生了移动，那么比它大的所有数的方向都反过来。对于一个排列而言，它的邻位对换法的下一个排列是最大的可移动的数移动后的结果。 我们看一个例子： 1，2，3，4.[很显然，这是一个偶排列，因为它是升序序列。1<2,1<3,1<4,2<3,2<4,3<4,都是正序]。为了得到下一个排列，我们取最大的数4，它是最大的可移动数，并把它向左移动： 1，2，4，3.实际上是3和4的交换，这便是它的下一个排列。再移动： 11/16页 1，4，2，3.再移动， 4，1，2，3. 由此我们得到了四个排列，每次都是通过交换相邻元素实现的。当4到头了之后，无法移动了，此时我们找到可移动的最大的数3，并把它向左移动1次，得到 4，1，3，2. 此时由于4的移动方向已经反过来了，所以最大可移动数为4，把4依次向右移动： 1，4，3，2 1，3，4，2 1，3，2，4. 4到了头，再次无法移动了，此时最大的可移动的数变成了3，把3向左移动一次，得到 3，1，2，4. 此时4的移动方向再反过来向左，得到 3，1，4，2. 3，4，1，2. 4，3，1，2. 此时3也到头了，此时我们找可移动的最大的数，2.得到 4，3，2，1. 4和3的移动方向再反向右， 3，4，2，1 3，2，4，1 3，2，1，4. 4到头后，由于此时3的移动方向向右，得到 2，3，1，4. 则4的方向又反，向左移动 2，3，4，1 2，4，3，1. 4，2，3，1. 此时3再向右移动，得到 4，2，1，3. 此时4再向右移动 2，4，1，3. 2，1，4，3. 2，1，3，4. 由此，我们从一个升序排列得到了全排列。通过这个例子，读者应该可以大概了解邻位对换法的基本过程了： 1.找到最大可移动数并移动至端点 2.找到现存的最大可移动数移动一次 3.回到原最大可移动数并移动至另一端点 4.找到现存的最大可移动数移动一次 ...... 5.找不到最大可移动数，循环结束，遍历结束。 由这个过程也可以直接得到一个非递归的算法，首先我们要写一个找到最大可移动数并移动一次的方法： bool Movable(int A[],direct[],int n) //direct参数用于接收每个元素移动方向的数组。 12/16页 { int max = 1;//初始化最大可移动数为1，因为规定1是最小的数，可以自己设定。 int pos = -1;//初始化最大可移动数的位置为-1. /*下面先找到最大可移动数位置*/ for(int i=0;i { if(a[i] < max) continue; if((i < n-1 && a[i] > a[i 1] && direct[i]) || (i > 0 && a[i] >a[i-1] && ! direct[i])) { max = a[i]; Pos = i; } } /*下面对它进行移动*/ if(pos = = -1) return false; if(p[pos]) { swap(A[pos],A[pos 1]); swap(direct[pos],direct[pos 1]);//我这里用同样名字了，可以写模版，也可以改 函//数名字 } else { swap(A[pos],A[pos-1]); swap(direct[pos],direct[pos-1]);//我这里用同样名字了，可以写模版，也可以改 函//数名字 } /*最后调整所有比最大可移动数大的数的方向*/ for(int i = 0;i { if(A[i] > max) direct[i] = !direct[i]; } return true; } 有了这个方法后，便可以进行全排列了。 17.邻位对换法全排列： void Full_Array(int A[], int n) { bool* direct = new bool[n]; //产生一个记录每个元素移动方向的数组 13/16页 sort(A,A n); //将原序列变成一个升序 for(int i=0;i direct[i] = false; //初始化移动方向为false，表示从右向左。 do { Print(A,n); if(A[n-1] = = n) for(int i=n-1;i>0;i--) { swap(A[i],A[i-1]); swap(direct[i],direct[i-1]); //我这里用同样名字了，可以写模版，也可以改 函//数名字 Print(A,n); } else for(int i=0;i < n; i ) { swap(A[i],A[i 1]); swap(direct[i],direct[i 1]); //我这里用同样名字了，可以写模版，也可以改 函//数名字 Print(A,n); } }while(Movable(A,direct,n)); delete []direct; } 15.邻位对换法的下一个排列： 为了让读者更容易理解和掌握邻位对换法的基本过程，我先通过一个例子让大家了解如何去得到下一个排列，并接着给出了相应的算法，但是，如果我们得到了一个排列比如： 2，3，4，1.我们仅仅知道通过一次邻位交换可以得到它的下一个排列，但是是哪一位的交换呢？ 首先，我们得找到最大的数的位置。2，3，4，1.中最大的数位于第3个位置。位置是好找的，那方向如何判断呢？ 我们接着要判断最大的数此时的移动方向。之前给出了奇排列和偶排列的概念，在这里便用的上了。每当我们的最大的数从一端移到另一端时，就要进行最大可移动数的交换，这个过程过后，在不考虑最大数的数列中便会增加一个逆序。而初始的1，2，3的逆序为0，最大的数在移动的过程中不会改变除去最大数后的数列的顺序，所以，不考虑最大数后的数列的逆序为偶数个时（偶排列），最大数在向左移动，逆序为奇数个时（奇排列），最大数向右移动。2，3，4，1中不考虑最大数的序列2，3，1的逆序为1，所以4在向右移动。 同样地，如果最大数此时在某一端点，我们可以通过上述性质判断是移动最大数还是找到最大可移动数并进行交换。当然这里我们还有问题没有解决：如何判断非最大数的数此时的方向呢？如果无法判断这个，还是无法找到下一个排列。 14/16页 与上面类似地，我们可以得到更一般的结论：一个非最大数的方向由所有比它小的数构成的序列的逆序决定的，如果是偶数个时，向左，奇数个时向右[也即的所有的数包括最大数都满足这条规则]。 2，3，4，1中容易知道此时3是向右的，2是向左的，4是向左的，1是不动的。读者可以自己对1，2，3，4这个全排列的每一个进行练习。 16.邻位对换法的中介数： 邻位对换法的中介数也不难求。对于某个排列如2341，，从1开始看起（1没有方向，不用算），如果它是向左的，则右边所有比它小的数的个数为中介数的最高位，如果是向右的，则左边所有比它小的数的个数为中介数的最高位，位逐次降低，如2对应k[1] = 1，最高位为1，3对应k[2] = 1，第三位为1，4是向左的，第二位为k[3] = 1. 得到111为2341的中介数。 对应的序号的求法为 (1 * 3 1) * 4 2 = 17，和递减进位的公式一样，所以通过序号求中介数也是和递减进位、递增进位类似，除以n取余，除以n-1除余，。。。。。。 邻位对换法由中介数求原排列的方法似乎也不是很简单，读者就不用掌握了，这里就概括一下：首先要判断最大数的方向，这个和上面一样，要由其它数构成的序列的奇偶性决定，所以要求其它数构成序列的奇偶性，这个奇偶性通过求序号的公式来得到，由性质原排列中取所有小于等于k的数构成的数列（顺序不变）的奇偶性和对应的序号的奇偶性相同。我举简单的例子：2341的中介数为112.那么231的中介数为11（舍掉低相应位数即可得到相应的中介数），则它的序号为1*3 1 = 4是偶数，所以最高位的方向4的方向向左。以此类推即可。 17.组合数的字典序与生成： 最后我们讲讲组合数的生成。首先我们看看列出集合的所有子集、要列出一个集合{1,2,3,4}的所有子集是很容易的，我们可以按照二进制数的顺序，0000，0001，0010，0011，0100，0101，0110，0111......来表示我们要取的元素，其中0表示不取，1表示取，这样就获得了一个顺序。而组合也包含在这个顺序当中。我们看从{1,2,3,4}中选取两个元素的所有组合： 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111. 蓝色标记的是我们所取的组合。对应的顺序便是 ｛3，4｝｛2，4｝｛2，3｝｛1，4｝｛1，3｝｛1，2｝我们可以用字典序对这些组合进行排序：{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}.共6种。按照我的习惯，我们先看看我们平常列举组合数所采取的策略。比如说1，2，3，4，5取3个元素的组合。我们先从小的取：1，2，3.再把最后一个数改变:1,2,4;1,2,5.当到达5之后，含有1，2的所有组合已经被罗列完了。改变2为3，1，3，4；1，3，5；此时我们不能再选择2进行罗列，否则会重复。改变3为4，此时2和3都不能放入，1，4，5.改变4为5时，2，3，4都不能放入，不存在组合了。这时改变1为2。之后不能再选择1罗列。所以， 对于一个组合C1C2C3C4...Cr(每个代表一个数，一共r个数，代表一个组合，数从[1,n]中选)，由于一个组合自身是不讲顺序的，我们可以对组合进行升序排列，使得C1 C(r - m)到达n - m后就不能再递增上去。由k = r - (r - k)得到 C(k)到达n - (r - k) = n - r k 后就不能再递增上去。 那么，对于C1C2C3C4...Cr，我们从Cr开始向前找，直到找到有Ci < n - r i，并执行 Ci = Ci 1。由于所有的组合都已经强制升序，所以Cj = Ci (j-i),j = i 1,i 2,...r即它后面 15/16页 |
|
|
