javascript演算法題：求任一個1-9位元不重複的N位數在該組合中的大小排列序號_javascript技巧

具體題目是這樣的：

　　從1--9中選取N個數字，組成不重複的N位數，從小到大進行編號，當輸入其中任何一個數M時，能找出該數字對應

的編號。如N=3，M=213.     輸出：[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]-- ->X=2

　　首先看到題目想到的是產生一個從少到大的全排列的數組，然後再遍歷數組得到對應的序號(數組下標加1)，又或者想到一個個從小到大的產生push進數組，然後判斷該數是不是當前題目給的數，如果是的話要求的序號就是當前數組的長度，比前面好的一點的是不用浪費時間去計算生成後面的項。生成本身複雜度不高，如果擴展到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在第三位，首數字是2，也就是說首數字是1的都在他前面(123,132)，再來看第二個數字和後面的數的組合13，首字母1已經是最小的了，他前面不可能有任何數，而第三個數字3就不用看了，因為如果前面的位數都確定了，最後一位就只有一種可能了，得出來的結果就是213的前面有2(首位) 0(二位) 0(尾位)=2個數，也就是說當前數在第3位，對比一下答案確實是這樣的，其它數的分析也一樣。由此可以得出我們要一個函數(也就是下面程式碼的setAll())可以算出某一位比當前數小的可能性總數，然後累加起來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