Question sur l'algorithme JavaScript : recherchez le numéro de séquence de tout nombre à N chiffres non répétitif de 1 à 9 dans les compétences combinaison_javascript

La question spécifique est la suivante :

Sélectionnez N nombres de 1 à 9 pour former N chiffres non répétitifs, numérotez-les de petit à grand, lorsque vous entrez un nombre M, vous pouvez trouver le numéro correspondant

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

La première chose à laquelle j'ai pensé lorsque j'ai vu la question était de générer un tableau entièrement organisé du plus petit au plus grand, puis de parcourir le tableau pour obtenir le numéro de série correspondant (indice du tableau plus 1), ou j'ai pensé de chacun du plus petit au plus grand. Générez un push dans le tableau, puis déterminez si le nombre est le nombre donné par la question actuelle. Si tel est le cas, le numéro de séquence requis est la longueur du tableau actuel. La première est qu’il n’est pas nécessaire de perdre du temps pour calculer et générer les éléments suivants. La complexité de la génération elle-même n'est pas élevée. Si elle est étendue en hexadécimal ou même en hexadécimal et qu'un grand nombre est donné, cela ne sera pas bon, cela gaspillera également de l'espace pour sauvegarder les données inutilisées. Peut-être pouvons-nous essayer d'autres méthodes qui ne nécessitent pas de génération.

Idéalisons d'abord la question. Si un nombre N est donné, alors M est composé de N chiffres de 1 à N (par exemple, N=4, alors M est composé de 1234 chiffres, pas d'autres 1349 et autres combinaisons). La raison en est que nous devons simplifier les conditions afin de pouvoir analyser les points communs et trouver une solution au problème, et il n'est pas difficile de passer d'une situation aléatoire à une situation idéale, donc cet article ne sera pas long. . Analysons d'abord l'exemple donné dans la question, [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)] 213 est en troisième position, le premier chiffre est 2, c'est à dire que le premier chiffre est 1 sont tous devant lui (123,132), regardons le deuxième chiffre et la combinaison de chiffres suivante 13, la première lettre 1 est déjà la plus petite, il ne peut y avoir aucun chiffre devant elle, et le troisième chiffre 3 n'est pas nécessaire. Regardez, car si les premiers chiffres sont déterminés, il n'y a qu'une seule possibilité pour le dernier chiffre. Le résultat est que 213 est précédé de 2 (le premier chiffre) 0 (le deuxième chiffre) 0 (chiffre de queue) =2 nombre, c'est-à-dire que le nombre actuel est dans le 3ème chiffre. Comparativement, la réponse est. en effet comme ça, et l'analyse des autres nombres est la même. De là, nous pouvons conclure que nous avons besoin d'une fonction (c'est-à-dire setAll() dans le code ci-dessous) qui puisse calculer le nombre total de possibilités pour qu'un certain chiffre soit plus petit que le nombre actuel, puis additionner jusqu'à 1 pour obtenir le résultat souhaité. Veuillez consulter l'implémentation du code :

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