【文章內(nèi)容簡介】 reverse(_F, _L)。 return (false)。 }}}9. 字典序的中介數(shù)，由中介數(shù)求序號：這里我要引入一個新的概念：中介數(shù)。為什么要引入這么一個概念呢？很多時候，我們要通過一個排列得出它的字典序中的位置（序號），比如1234567應(yīng)該排在第0位（開始位），1234576應(yīng)該排在第1位，7654321排在第7！1 = 5039位。當(dāng)然，我們可以通過計算Next_Permutation函數(shù)的迭代次數(shù)來得到這個數(shù)據(jù)，但這樣時間復(fù)雜度最差為O（n!），是非常不劃算的，因為我們僅僅要求一個數(shù)的位置。所以我們要先從數(shù)學(xué)的角度去計算這個問題。3456721排在第幾位？1. 先看看首位3，在以3開頭的數(shù)前面有以2開頭和以1開頭的數(shù)，這些數(shù)的個數(shù)為2*6!個，其中2代表1和2兩個數(shù)。2. 再看看第二位4。如果已經(jīng)確定由3開頭，那么在4開頭前面的數(shù)有幾種呢？也是以2開頭的數(shù)和以1開頭的所有數(shù)，因為3已經(jīng)放在開頭，所以這里不算，這些數(shù)的個數(shù)為2*5！。3. 再往下看，在5開頭前面的有幾種呢？由于4已經(jīng)放在前面，這里還是只有*4！。，再6開頭的前面有2*3！，再7開頭前面有2*2！，在2開頭前面有1*1！個（因為只剩1了）,在1開頭前面的沒有了。（0*0！）于是我們得到在3456721前面的數(shù)有2*6！+ 2*5！+ 2*4！+2*3！+2*2！+1*1 = 1745位。也說是說，在3456721前面的數(shù)一共有1745位，由于我們是從0開始的，所以它的位置也就是1745位。上述計算過程對應(yīng)了相應(yīng)的算法：從高位往低位看，或者對于數(shù)組而言從序號小的往大的看，按照3，4，5，6，7，2，1[a[0],a[1],a[2],a[3],a[4],a[5],a[6]]的順序，看它的右邊比它小的數(shù)的個數(shù)k[1],k[2],k[3]...（因為左邊的數(shù)已經(jīng)確定了），每一位的k[i]*[(ni1)]! [此處n = 7]乘以它所在的位數(shù)1的階乘，比如3在第7位（在數(shù)組中是第0位，所以用n0），減1得到后面還剩6位，而k[0]為2，因為在3的右邊比3小的數(shù)只有兩個。其它的位依次類推。為了簡化公式，我們一般取i=為數(shù)組序號加1（即a[0]我們認(rèn)為是a[1],用來和實際意義相近，因為我們實際中第一個數(shù)都是1而不是C語言中的0）。得到公式： n1 ∑k[i](ni)! i=1其中i為數(shù)組的序號，從1開始，實際寫算法時應(yīng)從0開始，n為數(shù)組元素的個數(shù)，k[i]表示第i個元素的右邊（從第i+1個元素開始到數(shù)組末尾）比第i 個元素小的元素的個數(shù)。有了上述公式，就可以方便的計算一個排列在字典序中的位置了。比如7654321= 6 * 6！+ 5 * 5！ + 4 * 4! + 3 *3! + 2*2! + 1*1! = 5039.到此，我們給出字典序中介數(shù)的定義：定義：由上述算法給出的數(shù)組k[i]按照順序排列所形成的數(shù)叫做這個排列的字典序中介數(shù)。如7654321的中介數(shù)為654321,3456721的中介數(shù)為222221。中介數(shù)之所以稱為中介數(shù)，是因為我們知道一個排列的中介數(shù)后，便可以很方便得求得它在字典序中的序號，而這個數(shù)在實際上沒有明確的意義，所以稱為中介數(shù)，要注意的是，中介數(shù)比原來排列的位數(shù)（數(shù)組的元素個數(shù)）少一位，因為最后一位的結(jié)果必然是0。讀者應(yīng)多多練習(xí)求一個排列的中介數(shù)以及相應(yīng)的序號。以上算法的時間復(fù)雜度為，其中求中介數(shù)為，由中介數(shù)到序號為O（n）。這個算法比初始的想法的O(n!)要好的多。這個算法實際的代碼我就不寫了，讀者可以自己寫，這要是掌握這個算法的原理和過程。這里還要說的是這個算法不適合于有重復(fù)數(shù)字的情況，下面所講的所有算法均不適合（可以想想為什么）。：通過中介數(shù)可以很方便地求序號，而通過一個排列可以很方便地得到它的中介數(shù)，那么自然要想到另一個過程：通過中介數(shù)能否很方便地反推回排列呢？首先，顯然地，中介數(shù)和排列是一一對應(yīng)的，不存在一個中介數(shù)對應(yīng)多個排列的情況（讀者可以想想為什么）。所以，必然有辦法可以求回去。按照我的習(xí)慣，還是從基本的想法做起，我們是怎樣求得中介數(shù)的，由此反推回如何求排列。比如222221。乍一看似乎很難入手，正如微分容易而積分難一樣，當(dāng)然，這個逆過程比積分要簡單的多，因為我們已經(jīng)確定它是唯一的。方法：從最左邊開始推算：2開頭，證明最高位的右邊比它小的數(shù)只有兩個，因為3已經(jīng)有了，那么還有比它小的兩個數(shù)，那就是4了，以此類推，我們可以很方便地求得一個中介數(shù)的原排列。方法即從最左邊推算。這是一個逆過程，最初看看是個不錯的想法，做出來也比較快，而實際上不是這樣的。我們看看我們實際的運算過程：最左邊的數(shù)如果是x1，那么它的原排列位是x1+1，當(dāng)我們?nèi)タ吹诙€數(shù)時，我們先假想它是x2+1，如果第一個排列位比x2+1來得大，那么沒有問題，如果比它小或者相等，則要加上1，所以實際上，我們每求一位數(shù)，都要先讓它和前面的所有數(shù)進(jìn)行比較來獲得它的定位。求解中介數(shù)還有一些類似的方法，這里我便不羅列了，反正大同小異，表面上看起來比較簡單，但實際實現(xiàn)起來是比較復(fù)雜的（由其是對計算機(jī)而言）。而且，在這種方法中，我們很難通過已知的排列序號反推出原來的排列，所以有必要給出新的中介數(shù)形式。：為了改變由中介數(shù)求原排列的復(fù)雜性，我們要修改我們定義中介數(shù)的方法，我們的中介數(shù)是和相應(yīng)的位數(shù)相關(guān)聯(lián)的，中介數(shù)的下標(biāo)對應(yīng)了位的下標(biāo)。我們定義一種新的中介數(shù)，稱為遞增進(jìn)位制數(shù)，它的下標(biāo)對應(yīng)了數(shù)字大?。榱撕啽?，下面還是叫做中介數(shù)，為了區(qū)分，我們把原來的中介數(shù)叫作初始中介數(shù)）。我們看一個新的數(shù)：（讀者應(yīng)該已經(jīng)會求了），我們不按照從左到右的順序排，而是按照數(shù)字的大小來排，3對應(yīng)的是2，因為是原排列位上的數(shù)是3，所以把它放在第3位；6對應(yīng)的是4，因為原排列位上的是6，所以把它放在第6位，4對應(yīng)的是2，放在第4位，7對應(yīng)3，放在第7位，5對應(yīng)2，放在第5位，2對應(yīng)1，放在第2位，1對應(yīng)的是0，我們沒有寫出來。我們得到342221(0).相當(dāng)于對初始中介數(shù)進(jìn)行了排序，按照原來位上數(shù)字的大小排序，這樣的數(shù)稱為遞增進(jìn)位制數(shù)。讀者可能還看不出來這個數(shù)和遞增進(jìn)位制這個名詞有任何關(guān)系，它只是從中介數(shù)演變過來而已。實際上，經(jīng)過這樣的一個演變，每一位上的數(shù)都不會超過位的大小，比如第4位上的2（我用藍(lán)色記號的），它是不能達(dá)到4的，因為第4位對應(yīng)原排列上的4，而原排列上的4產(chǎn)生的初始中介數(shù)位是不可能大于4的（因為初始中介數(shù)是它右邊比它小的數(shù)的個數(shù)，原排列是4，不可能有5個比它小的數(shù)）。所以就形成了遞增進(jìn)位制數(shù)。它的第一位恒為0，（所以用括號把0括號起來了），是個一進(jìn)制數(shù)，第二位為1或0，是個二進(jìn)制數(shù)，第三位為2或1或0，是個三進(jìn)制數(shù)，以此類推。為了便于讀者理解，我給出這樣一個數(shù)的運算：342221 (0)+ 1 = 342221 + 1（因為一進(jìn)制數(shù)加任何數(shù)都相當(dāng)于把它進(jìn)位）= ，1+1進(jìn)位了，第二位為0，第三位是個3進(jìn)制數(shù)，2+1還是進(jìn)位了，第三位為0，第四位是個四進(jìn)制數(shù)，沒有進(jìn)位。和字典序一樣，原理還是加法，只是每一位的進(jìn)制都不相同，當(dāng)然，如果做一個比較復(fù)雜的運算就比較難了。讀者可以自己練習(xí)幾個。由這樣的中介數(shù)求它的序號的方法為(((((k[1]*(n1) + k[2])*(n2)+k[3])*(n3)..*2 + k[n1].)，其中k[i]就是新的中介數(shù)，i從1開始表示從左往右數(shù)，即數(shù)組的序號（對應(yīng)n i + 1位）。這里的n表示的是原排列的元素個數(shù)。實際上就是一種奇特的進(jìn)制，要注意的是，此時的序號并不是按照字典序排序的，而是一個新的排序方式。1234576 新的中介數(shù)：100000。序號：720而不是原來的1。但是范圍是一樣的，而且始末點是一樣的。1234567 0 76543215039(讀者自己算一下)。講了這么多，讀者可能覺得這個方法看著非常麻煩，它到底哪里有利于求原排列呢？下面就講它確定原排列的方法：數(shù)空格法。__ __ __ __ __ __ __我們畫這樣七個空格，來求342221的原排列：第7位數(shù)字是3，我們從右向左數(shù)3個空格，再往前數(shù)一個空格，空格中填入對應(yīng)的位數(shù)7，把對應(yīng)的空格擦除。__ __ __ 7 __ __ __。第6位數(shù)字是4，我們從右向左數(shù)4個空格，其中已經(jīng)放上數(shù)的不算空格，再往前數(shù)一個空格，空格中填入6，把對應(yīng)空格擦除。__ 6 __ 7 __ __ __。接下來的步驟也是一樣的，第5位的數(shù)字是2，數(shù)2個空格，再往前數(shù)一個空格填入5。__ 6 __ 7 5 __ __。第4位是2，數(shù)2個空格再往前數(shù)一個空格填入4。__