JavaScript 알고리즘 질문: Combination_javascript 기술에서 1부터 9까지 반복되지 않는 N자리 숫자의 시퀀스 번호를 찾으세요.

구체적인 질문은 다음과 같습니다.

1~9 사이에서 N 숫자를 선택하여 반복되지 않는 N 숫자를 만들고, 작은 것부터 큰 것까지 번호를 매기고, 임의의 숫자 M을 입력하면 해당 숫자를 찾을 수 있습니다

의 수입니다. 예를 들어 N=3, M=213 출력: [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)] -- ->X=2

질문을 보고 가장 먼저 생각난 것은 가장 작은 것부터 가장 큰 것까지 완전히 배열된 배열을 생성한 다음 배열을 순회하여 해당 일련 번호(배열 첨자 + 1)를 얻는다는 것이었습니다. 가장 작은 것부터 가장 큰 것 순으로 배열에 푸시를 생성한 다음 그 숫자가 현재 질문에 제공된 숫자인지 확인합니다. 그렇다면 필요한 시퀀스 번호는 이전 배열보다 낫습니다. 하나는 후속 항목을 계산하고 생성하는 데 시간을 낭비할 필요가 없다는 것입니다. 생성 자체의 복잡도는 높지 않으며, 16진수나 심지어 16진수까지 확장해서 큰 숫자를 준다면 사용하지 않는 데이터를 저장하기 위해 공간을 낭비하는 것도 좋지 않습니다. 어쩌면 생성이 필요하지 않은 다른 방법을 시도해 볼 수도 있습니다.

먼저 질문을 이상화해 보겠습니다. 숫자 N이 주어지면 M은 1부터 N까지 N개의 숫자로 구성됩니다(예: N=4이면 M은 1349가 아닌 1234개의 숫자로 구성됩니다. 다른 조합). 그 이유는 공통점을 분석하고 문제에 대한 해결책을 얻기 위해서는 조건을 단순화할 필요가 있고, 임의의 상황에서 이상적인 상황으로 전환하는 것은 어렵지 않기 때문에 이 글은 길지 않을 것이다. . 먼저 질문에 제시된 예를 분석해 보겠습니다. [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번째 숫자입니다. 정말 이렇고, 다른 숫자에 대한 분석도 마찬가지다. 이것으로부터 우리는 특정 숫자가 현재 숫자보다 작을 가능성의 총 개수를 계산한 다음 1을 더하여 다음을 얻을 수 있는 함수(즉, 아래 코드의 setAll())가 필요하다는 결론을 내릴 수 있습니다. 원하는 결과를 확인하세요.

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