JavaScript アルゴリズムの質問: combin_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 を加えたもの) を取得することでした。配列へのプッシュを生成し、その数値が現在の質問で指定された数値であるかどうかを判断します。そうである場合、必要なシーケンス番号は、前の配列の長さよりも優れたものになります。 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 は 3 番目の位置にあり、最初の数字は 2、つまり最初の数字 1 はすべて彼の前にあります (123,132)。 2 番目の数字を見てみましょう。次の数字の組み合わせ 13、最初の文字 1 はすでに最小であり、その前に数字を置くことはできません。3 番目の数字 3 は必要ありません。最初の桁が決まれば、最後の桁の可能性は 1 つだけなので、結果として 213 の前に 2 (最初の桁) 0 (2 桁目) 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