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