javascript algorithm problem: find the order number of the size of any 1 9 non repeating N bit in the combination

  • 2020-05-24 05:14:19
  • OfStack

The specific topic is as follows:

Select N digits from 1--9 to form non-repeating N digits, and number them from small to large. When any one of the digits, M, can be found out

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

First saw the title of is to generate a full arranged from small to large array, and then through the array to get the corresponding serial number (array subscript 1), or thought of 1 each since the childhood push generated into the array, and then concludes that the number is currently subject to the number, if so required the serial number is the length of the array, better than the previous 1 point is not a waste of time to compute generated at the back of the item. The complexity of generation itself is not high, if it is extended to hexadecimal or even 36th, and given a large number, it is not good, and one part of the space needs to be wasted to save the data that is not used. Maybe we can try other methods that don't have to be generated.

Let's idealize the problem first. If we give a number N, then M is made up of 1-N N digits (e.g., N=4, then M is made up of 1234 digits instead of 1349 and so on). The reason why we do this is because we want to simplify the conditions so that we can analyze the commonalities to get the solution, and it is not difficult to convert from the random case to the ideal case, which I will not talk about in this article. Analysis under the first title for example, [123 (1), 132 (2), 213 (3), 231 (4), 312 (5), 321 (6)] in 3rd 213, the first number is 2, that is to say, the first number is 1 (123132) in front of him, look at the second behind the Numbers, and the combination of the number 13, 1 is the smallest initials, he can't have any in front of the number, and the third number 3 you don't have to look at, because if the previous digits are identified, the last one is only one possibility, So what we get is that 213 is preceded by 2(the first place)+0(the second place)+0(the last place)=2 Numbers, which means that the current number is in the third place, which is exactly what we get when we compare it to 1, and the analysis of the other Numbers is the same. It can be concluded that if we want a function (setAll() in the following code), we can calculate the total number of possibilities that a certain bit is less than the current number, and then add up to +1 to get the desired result. Please see the code implementation:


// The functionality : For each 1 Bits, the total number of possibilities that are less than current if it's something else 
//a   Current number (from small to large) 
//n   Total current number 
function getAll(a,n){
 var sum=1; // The total number of 
 for(var i=n;i>1;i--)sum=sum*i; // Calculate the n In an ordered position n The total number of possibilities 
 return sum*(a-1)/n; // So let's figure out PI over the first place is PI a The total number of possibilities of a number less than the current number 
}

//m  The sequence of Numbers to calculate 
//a  The size number of the number that holds the current bit and the number that follows it 
//   Such as  213  the  a The array is  [2,1,1]; a[0] for 2 because  213  The first 2 in 2133 Number number number 2 small ; while a[1] for 1 because 13 The top of the 1 in 13 Out of the first 1 small 
function find(m){
 m=(m+"").split(""); // Split the current number into an array to make it easier to split each one 1 Bit counting 
 var a=new Array(m.length+1).join(1).split(""); // The fast generation length is m The length of PI is equal to PI 1 The array, a See the comments in the function header above for a functional description of the array 
 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]++;
 }
 } // generate a An array of 
 console.log("a Array: ",a);
 for(i=1,sum=1;i<m.length;i++){
 sum+=getAll(+a[i-1],m.length-i+1); // Cycle call getAll Calculate each 1 The total number of possible combinations of bits and the Numbers that follow them that are less than the current combination 
 }
 return m+"  In the top of the list "+sum+" position ";
}
console.log(find(213)); // The output 3
console.log(find(123)); // The output 1
console.log(find(231)); // The output 4
console.log(find(312)); // The output 5
console.log(find(4321)); // The output 24
console.log(find(21)); // The output 2
console.log(find(1)); // The output 1

Related articles: