JavaScript 中的排列

Anika Tabassum Era 2023年10月12日

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