JavaScript 中的排列

Anika Tabassum Era 2023年1月30日 2022年5月10日

JavaScript JavaScript Array

給定陣列的排列
給定字串的排列

在 JavaScript 中，有 slice、reduce、filter、substring 和更多方法來緩解置換給定字串或陣列的所有可能試驗的基本問題。

在這裡，我們將展示如何從給定的輸入中提取陣列和字串的組合。主要重點是將每個文字從陣列或字串中分開，並一一交換其他文字。

在以下部分中，我們將使用必要的程式碼示例詳細討論該過程。

給定陣列的排列

我們將初始化一個函式 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]);

輸出：

陣列燙髮

這裡的主要動作定義了交換部分，我們在其中將每個文字彼此交換一次試驗（例如 [1,2,3]）並提出可能的組合。

從試驗 [1,2,3]，我們將得到 [1,2,3] & [1,3,2]。這部分將被執行，直到每個文字都得到檢查。

在切換到下一個試驗之前，我們通過再次交換返回到基本試驗（1,2,3）（因為最後一個組合是 [1,3,2]）。這就是回溯的操作方式。

形成一棵樹以檢視可能的試驗，並且樹的長度等於陣列的長度。最初，我們執行一個 DFS 來解決這個問題，然後遞迴回溯過程來解決這個問題。

給定字串的排列

在字串的情況下，我們將首先拆分字串，然後我們將使用 reduce 方法通過遞迴呼叫 permutationString 函式來逐個連線可能的試驗。

程式碼片段：

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'));