Javascript algorithm question: Find the sequence number of any non-repeating N-digit number from 1 to 9 in the combination

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

WBOY

Release： 2016-05-16 17:51:46

Original

1210 people have browsed it

The specific question is as follows:

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

. 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 digit, and the first digit is 2. That is to say, those whose first number is 1 are all in front of it (123,132). Let’s look at the combination of the second number and the following number 13. The first letter 1 is already the smallest. There cannot be any number in front of it, and the third There is no need to look at the number 3, because if the previous digits are determined, there is only one possibility for the last digit. The result is that 213 is preceded by 2 (first digit) 0 (second digit) 0 (last digit) )=2 numbers, that is to say, the current number is in the 3rd digit. By comparison, 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:

Copy code The code is as follows:

 
//Function: get each bit, if If it is other numbers, the total number of possibilities is smaller than the current one 
//a The current number serial number (from small to large) 
//n The total number of current numbers 
function getAll(a,n){ 
var sum =1; //Total number
for(var i=n;i>1;i--)sum=sum*i; //Calculate the total number of possibilities of placing n different numbers in n ordered positions
return sum*(a-1)/n; //Calculate the total number of possibilities for a number smaller than the current number with a as the first number
} 

//m Number sequence to be calculated
//a stores the number of the current digit and the number of the following digits. Its size sequence number 
// For example, the a array of 213 is [2,1,1]; a[0] is 2 It’s because the first 2 of 213 ranks the second smallest among the three numbers of 213; and a[1] is 1 because the first 1 of 13 ranks the first smallest among 13 
function find(m){ 
m= (m "").split(""); //Split the current number into the array to facilitate calculation of each digit
var a=new Array(m.length 1).join(1) .split(""); //Quickly generate an array with length m and all values ​​​​are 1. For the function description of the a array, please see the comment in the function header above 
for(var i=0;ifor(var j=i 1;jif( m[i]> m[j])a[i] ; 
 } 
} //Generate an array 
console.log("array a:",a); 
for(i=1,sum=1;isum =getAll( a[i-1],m.length-i 1); //Call getAll in a loop to calculate the total number of possibilities that the combination of each digit and the following number is smaller than the current combination 
} 
return m " ranks at the " sum " position" of the full arrangement; 
} 
console.log(find(213)); //Output 3 
console.log(find(123)); //Output 1 
console.log(find(231)); //Output 4 
console.log(find(312)); //Output 5 
console.log(find(4321)) ; //Output 24 
console.log(find(21)); //Output 2 
console.log(find(1)); //Output 1 