JavaScript algorithm question: Find the sequence number of any non-repeating N-digit number from 1 to 9 in the combination_javascript skills

The specific question is as follows:

Select N numbers from 1--9 to form non-repeating N digits, number them from small to large, when you enter any number M, you can find the corresponding number

. For example, N=3, M=213. Output: [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)]-- ->X=2

The first thing I thought of when I saw the question was to generate a fully arranged array from smallest to largest, and then traverse the array to get the corresponding serial number (array subscript plus 1), or I thought of each one from smallest to largest. Generate push into the array, and then determine whether the number is the number given by the current question. If so, the required sequence number is the length of the current array. What is better than the previous one is that there is no need to waste time to calculate and generate the subsequent items. The complexity of the generation itself is not high. If it is expanded to hexadecimal or even hexadecimal and a large number is given, it will not be good. It will also waste some space to save unused data. Maybe we can try other methods that don't require generation.

Let’s idealize the question first. If a number N is given, then M is composed of N digits from 1 to N (for example, N=4, then M is composed of 1234 digits, not other 1349 and other combinations). The reason for this is that we need to simplify the conditions so that we can analyze the commonalities and get a solution to the problem, and it is not difficult to transform from a random situation into an ideal situation, so this article will not be lengthy. Let’s first analyze the example given in the question, [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)] 213 is in the third position, the first number is 2, that is to say the first number is 1 are all in front of him (123,132), let’s look at the second number and The following number combination 13, the first letter 1 is already the smallest, there cannot be any number in front of it, and the third number 3 is not needed Look, because if the first digits are determined, there is only one possibility for the last digit. The result is that 213 is preceded by 2 (the first digit) 0 (the second digit) 0 (tail digit) =2 number, that is to say, the current number is in the 3rd digit. Comparatively, the answer is indeed like this, and the analysis of other numbers is the same. From this we can conclude that we need a function (that is, setAll() in the code below) that can calculate the total number of possibilities that a certain digit is smaller than the current number, and then add up to 1 to get the desired result. Please see the code implementation:

//函数功能:得到每一位，如果是其它数的话比当前小的可能性总数
//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