從 1~9 中挑選 N 個數字,組成不重複的 N 位數,並由小到大編號。輸入其中任一個數 M,求出它對應的編號。
例如 N=3、M=213:
[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)] ---> X=2
最直覺的做法是先生成由小到大的全排列陣列,再用索引加一當答案;或者一路遞增生成並比對,命中時取當前長度。後者稍微好些,因為不必計算後續的項。但這兩種做法在基數擴大到 16 進位、36 進位,或位數很長時就不太可行,而且還得浪費空間存放用不到的資料。或許可以換個不需要生成的思路。
先把題目理想化:假設給定 N 後,M 就是由 1~N 這幾個數字組成的 N 位數(例如 N=4 時 M 由 1234 組合,而非 1349 之類)。這樣簡化條件後比較容易歸納出通用解法,而從任意情況轉為理想情況並不難,此處不贅述。
回頭分析題目的例子 [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)]。213 排在第 3 位,首位是 2,代表所有首位為 1 的排列(123、132)都在它前面。再看第二位與後面的組合 13,首字 1 已是最小,前面不可能再有數;第三位 3 不必看,因為前兩位一旦確定,最後一位就只剩一種可能。於是 213 前面共有 2(首位)+ 0(二位)+ 0(尾位)= 2 個數,序號即為第 3 位——與答案相符。
由此可得:我們需要一個函式能算出「某一位若換成更小的數字,會有多少種排列」,把每一位的貢獻累加後加 1,就是答案。
//函數功能:得到每一位,如果是其它數的話比當前小的可能性總數 //a 當前數序號(從小到大) //n 當前數總數 function getAll(a,n){ var sum=1; //總數 for(var i=n;i>1;i--)sum=sum*i; //算出n個有序的位置放n個不同的數字的可能性總數 return sum*(a-1)/n; //算出比首位為a的比當前數小的數的可能性總數 } //m 要計算的數序列 //a 存放當前位的數在和它後位的數而組成的數它的大小序號 // 比如 213 的 a數組為 [2,1,1]; a[0]為2是因為 213 首位2在213三個數字中排第2小;而a[1]為1是因為13的首位1在13中排第一小 function find(m){ m=(m+"").split(""); //把當前數拆分放在數組裡面好方便對每一位進行計算 var a=new Array(m.length+1).join(1).split(""); //快速生成長度為m的長度的值都為1的數組,a數組的功能說明看上面函數頭的注釋 for(var i=0;i<m.length-1;i++){ for(var j=i+1;j<m.length;j++){ if(+m[i]>+m[j])a[i]++; } } //生成a數組 console.log("a數組:",a); for(i=1,sum=1;i<m.length;i++){ sum+=getAll(+a[i-1],m.length-i+1); //循環調用getAll計算每一位與其後面的數成的組合比當前組合小的可能性總數 } return m+" 排在全排列的第"+sum+"位"; } console.log(find(213)); //輸出3 console.log(find(123)); //輸出1 console.log(find(231)); //輸出4 console.log(find(312)); //輸出5 console.log(find(4321)); //輸出24 console.log(find(21)); //輸出2 console.log(find(1)); //輸出1
演算法的關鍵在 a 陣列:它記錄每一位在其「自身與後位數字」中所排的相對大小序號。有了它,每一位的貢獻就能用簡單的排列數公式算出,整體複雜度降到 O(N²),不必真的把全排列展開。