JavaScript の順列

Anika Tabassum Era 2023年10月12日

JavaScript JavaScript Array

与えられた配列の順列
与えられた文字列の順列

JavaScript には、slice、reduce、filter、substring、および特定の文字列または配列のすべての可能な試行を並べ替えるという基本的な問題を軽減するための多くのメソッドがあります。

ここでは、特定の入力から配列と文字列の組み合わせを引き出す方法を示します。主な焦点は、配列または文字列から各リテラルを分割し、他のリテラルを 1つずつ交換することです。

次のセクションでは、必要なコード例を使用して手順について詳しく説明します。

与えられた配列の順列

関数 permute をその中の別の関数 backtrack で初期化します。この関数 backtrack は、適切な組み合わせのセットを実行するために再帰的に呼び出されます。

コードスニペット：

var permute = function(nums) {
  var result = [];
  var backtrack = (i, nums) => {
    if (i === nums.length) {
      result.push(nums.slice());
      return;
    }
    for (let j = i; j < nums.length; j++) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      backtrack(i + 1, nums);
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  } backtrack(0, nums);
  console.log(result);
  return result;
};
permute([1, 2, 3]);

出力：

array_perm

ここでの主なアクションは、スワッピング部分を定義します。ここでは、各リテラルを 1つの試行（例：[1,2,3]）の相互にスワッピングし、可能性のある組み合わせを引き出します。

トライアル [1,2,3] から、[1,2,3] & [1,3,2] が得られます。この部分は、すべてのリテラルがチェックされるまで実行されます。

次のトライアルに切り替える前に、再度交換してベーストライアル（1,2,3）に戻りました（最後の組み合わせは [1,3,2] だったため）。これがバックトラッキングの操作方法です。

可能な試行を確認するためにツリーが形成され、ツリーの長さは配列の長さと同じです。最初に、ケースを解決するために DFS を実行し、再帰的なバックトラッキング手順がそれを実行します。

与えられた文字列の順列

文字列の場合、最初に文字列を分割し、次に reduce メソッドを使用して、permutationString 関数を再帰的に呼び出して、可能性のある試行を 1つずつ連結します。

コードスニペット：

var permutationString = str => {
  if (str.length <= 2)
    return str.length === 2 ? [str[0] + str[1], str[1] + str[0]] : [str];
  return str.split('').reduce(
      (accumulator, letter, i) => accumulator.concat(
          permutationString(str.slice(0, i) + str.slice(i + 1))
              .map(val => letter + val)),
      []);
};
console.log(permutationString('abcd'));