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 を加えたもの) を取得することでした。それぞれを最小から最大まで考えて、配列にプッシュを生成し、その数値が現在の質問で指定された数値であるかどうかを判断します。そうである場合、必要なシーケンス番号は現在の配列の長さよりも優れています。前者は、後続の項目を計算して生成するために時間を無駄にする必要がないことです。生成自体の複雑さは高くありませんが、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 番目の数字を調べる必要はありません。前の数字が決定されている場合、最後の数字の可能性は 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 には、現在の桁の数値とその次の桁の数値が格納されます。 number
// たとえば、213 の配列は [2,1,1]; a[0] は 2 です。これは、213 の最初の 2 が 213 と a[ の 3 つの数値の中で 2 番目に小さいためです。 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;ifor(var j=i 1;jif( m[i]>gt; m[j])a[i] ;
}
} // 配列
コンソールを生成します。 log("配列 a:",a);
for(i=1,sum=1;isum =getAll( a[i-1],m.length -i 1); //ループ内で getAll を呼び出し、各桁と次の数値の組み合わせが現在の組み合わせよりも小さい可能性の合計数を計算します。
}
return m " が " 合計でランク付けされます。完全な配置の "位置"
}
console.log(find(213)) //出力 3
console.log(find(123)); //出力 1
コンソール.log(find(231)); //出力 4
console.log(find(312)); //出力 5
console.log(find(4321)) //出力 24
console.log(find(21)); //出力 2
console.log(find(1)); //出力 1