JavaScriptで「美しい配置」を数える：バックトラッキングによる効率的な解法

美しい配置（Beautiful Arrangement）とは？

1からnumまでのnum個の整数があるとします。これらの整数を使って構成される配列が「美しい配置」であるためには、配列のi番目の位置（1 ≦ i ≦ N）について、次のいずれかの条件が満たされている必要があります。

• i番目の位置にある数値が、iで割り切れる。

• iが、i番目の位置にある数値で割り切れる。

問題

数値numを受け取り、そのnumに対して構築できる「美しい配置」の総数を返すJavaScript関数を作成してください。

例えば、関数への入力が次の場合：

const input = 2;

期待される出力は次のとおりです。

const output = 2;

出力の説明

1つ目の美しい配置は [1, 2] です。

2つ目の美しい配置は [2, 1] です。

実装コード

const num = 4;
const countArrangements = (num = 1) => {
   let ans = 0
   const recur = (curr, vis) => {
      if (curr === 1){
         ans++;
      }else{
         for (let i = num; i; i--) {
            let possible = (i % curr === 0 || curr % i === 0);
            let visited = vis & 1 << i;
            if (possible && !visited){
               recur(curr-1, vis | 1 << i);
            }
         }
      }
   };
   recur(num, 0);
   return ans;
};
console.log(countArrangements(num));

コードの解説

まず、結果を格納する変数（ans）を定義し、分岐する可能性をすべて探索するための再帰関数を作成します。この再帰関数が必要とする引数は2つだけです。現在配置しようとしている数値（curr）と、すでに使用済みの数値を記録するフラグ（vis）です。

ここでのポイントは、visをビットマスクとして扱っている点です。各ビットが対応する数値の使用状況を表すことで、メモリを節約しながら高速に状態管理ができます。また、条件式 i % curr === 0 || curr % i === 0 によって、その数値が現在の位置と割り切れる関係（約数・倍数の関係）にあるかどうかを判定し、条件を満たさない組み合わせは早期に枝刈りすることで、探索範囲を大幅に絞り込んでいます。

実行結果

コンソールには次のように出力されます。

8

これは、num = 4 の場合に構築可能な「美しい配置」が全部で8通り存在することを示しています。この手法はバックトラッキングの一種であり、無駄な探索を切り捨てることで、全順列を生成するよりもはるかに効率的に答えを求められます。