Soalan algoritma JavaScript: Cari nombor jujukan mana-mana nombor N-digit tidak berulang dari 1 hingga 9 dalam kemahiran kombinasi_javascript

Soalan khusus adalah seperti berikut:

Pilih N nombor daripada 1--9 untuk membentuk N digit yang tidak berulang, nomborkannya dari kecil hingga besar, apabila anda memasukkan sebarang nombor M, anda boleh mencari nombor yang sepadan

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

Perkara pertama yang saya fikirkan apabila saya melihat soalan itu ialah untuk menjana tatasusunan tersusun sepenuhnya daripada terkecil kepada terbesar, dan kemudian melintasi tatasusunan untuk mendapatkan nombor siri yang sepadan (subskrip tatasusunan tambah 1), atau saya fikir daripada setiap satu daripada yang paling kecil kepada yang terbesar Hasilkan tolakan ke dalam tatasusunan, dan kemudian tentukan sama ada nombor itu adalah nombor yang diberikan oleh soalan semasa satu ialah tidak perlu membuang masa untuk mengira dan menjana item seterusnya. Kerumitan penjanaan itu sendiri tidak tinggi Jika ia dikembangkan kepada perenambelasan atau pun perenambelasan dan sejumlah besar diberikan, ia juga akan membazirkan sedikit ruang untuk menyimpan data yang tidak digunakan. Mungkin kita boleh mencuba kaedah lain yang tidak memerlukan penjanaan.

Mari kita idealkan soalan dahulu Jika nombor N diberikan, maka M terdiri daripada N digit dari 1 hingga N (contohnya, N=4, maka M terdiri daripada 1234 digit, bukan 1349 dan lain-lain. kombinasi lain). Sebabnya ialah kita perlu memudahkan syarat supaya kita boleh menganalisis persamaan dan mendapatkan penyelesaian kepada masalah itu, dan tidak sukar untuk mengubah situasi rawak kepada situasi ideal, jadi artikel ini tidak akan panjang. . Mari kita analisis dahulu contoh yang diberikan dalam soalan, [123(1), 132(2), 213(3), 231(4), 312(5), 321(6)] 213 berada di kedudukan ketiga, nombor pertama ialah 2, iaitu nombor pertama ialah 1 semuanya berada di hadapannya (123,132), mari kita lihat nombor kedua dan Gabungan nombor berikut 13, huruf pertama 1 sudah menjadi yang terkecil, tidak boleh ada sebarang nombor di hadapannya, dan nombor ketiga 3 tidak diperlukan Lihat, kerana jika digit pertama ditentukan, hanya ada satu kemungkinan untuk digit terakhir Hasilnya ialah 213 didahului oleh 2 (digit pertama) 0 (digit kedua) 0 (digit ekor) =2 nombor, iaitu nombor semasa berada dalam digit ke-3 Secara perbandingan, jawapannya ialah memang macam ni, dan analisis nombor lain pun sama. Daripada ini kita boleh membuat kesimpulan bahawa kita memerlukan fungsi (iaitu, setAll() dalam kod di bawah) yang boleh mengira jumlah bilangan kemungkinan bahawa digit tertentu lebih kecil daripada nombor semasa, dan kemudian menambah sehingga 1 untuk mendapatkan hasil yang dikehendaki. Sila lihat pelaksanaan kod:

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