Frage zum JavaScript-Algorithmus: Finden Sie die Sequenznummer einer beliebigen sich nicht wiederholenden N-stelligen Zahl von 1 bis 9 in den Kombinations-Javascript-Fähigkeiten

Die konkrete Frage lautet wie folgt:

Wählen Sie N Zahlen von 1--9 aus, um sich nicht wiederholende N Ziffern zu bilden, nummerieren Sie sie von klein nach groß. Wenn Sie eine beliebige Zahl M eingeben, können Sie die entsprechende Zahl finden

Die Anzahl von

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

Das erste, woran ich dachte, als ich die Frage sah, war, ein vollständig angeordnetes Array vom kleinsten zum größten zu generieren und dann das Array zu durchlaufen, um die entsprechende Seriennummer (Array-Index plus 1) zu erhalten, oder dachte ich Generieren Sie einen Push in das Array und bestimmen Sie dann, ob die Nummer die in der aktuellen Frage angegebene ist. Wenn ja, ist die erforderliche Sequenznummer die Länge des aktuellen Arrays Einer davon besteht darin, dass keine Zeit mit der Berechnung und Generierung der nachfolgenden Elemente verschwendet werden muss. Die Komplexität der Generierung selbst ist nicht hoch, wenn sie auf hexadezimal oder sogar hexadezimal erweitert wird und eine große Zahl angegeben wird. Außerdem wird etwas Platz zum Speichern ungenutzter Daten verschwendet. Vielleicht können wir andere Methoden ausprobieren, die keine Generierung erfordern.

Idealisieren wir zunächst die Frage. Wenn eine Zahl N gegeben ist, dann besteht M aus N Ziffern von 1 bis N (z. B. N=4, dann besteht M aus 1234 Ziffern, nicht aus anderen 1349). andere Kombinationen). Der Grund dafür ist, dass wir die Bedingungen vereinfachen müssen, damit wir die Gemeinsamkeiten analysieren und eine Lösung für das Problem finden können, und es nicht schwierig ist, von einer zufälligen Situation in eine ideale Situation umzuwandeln, sodass dieser Artikel nicht zu lang wird . Lassen Sie uns zunächst das in der Frage gegebene Beispiel analysieren: [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)] 213 steht an dritter Stelle, die erste Zahl ist 2, das heißt die erste Zahl ist 1 sind alle vor ihm (123,132), Schauen wir uns die zweite Zahl an und die folgende Zahlenkombination 13, der erste Buchstabe 1 ist bereits der kleinste, davor darf keine Zahl stehen, und die dritte Zahl 3 wird nicht benötigt. Schauen Sie, denn wenn die ersten Ziffern ermittelt werden, gibt es nur eine Möglichkeit für die letzte Ziffer. Das Ergebnis ist, dass 213 2 (die erste Ziffer) 0 (die zweite Ziffer) 0 (Endziffer) =2 Zahl, das heißt, die aktuelle Zahl steht in der 3. Ziffer. Vergleichsweise lautet die Antwort tatsächlich so, und die Analyse anderer Zahlen ist die gleiche. Daraus können wir schließen, dass wir eine Funktion benötigen (d. h. setAll() im Code unten), die die Gesamtzahl der Möglichkeiten berechnen kann, dass eine bestimmte Ziffer kleiner als die aktuelle Zahl ist, und diese dann zu 1 addieren kann, um die zu erhalten gewünschtes Ergebnis. Bitte sehen Sie sich die Code-Implementierung an:

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