排列与下一个排列

Source: Dev.to

请提供您希望翻译的正文内容，我会按照要求将其翻译成简体中文并保留原有的格式、代码块和链接。

介绍

排列是问题求解和数据结构（PS/DSA）中的基本概念。
它们出现在递归、回溯、组合学、图遍历、面试题以及优化/状态探索任务中。深入理解排列还能让 Next Permutation（下一个排列）问题变得简单直观。

排列是元素的有序排列。
对于 n 个不同的元素，排列的总数为 n!。

示例

对于数组：

[1, 2, 3]

所有排列：

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

顺序很重要（[1,2] ≠ [2,1]）。探索排列意味着探索所有可能的状态。

为什么排列在 PS / DSA 中很重要

排列训练你在：

• 递归
• 回溯
• 状态恢复
• 深度优先搜索
• 选择–探索–撤销 模式

许多高级问题都建立在排列之上：

• N‑皇后
• 数独
• 子集与组合
• 第 K 个排列
• 单词排列

回溯模板

1. 选择 – 交换或标记元素为已使用。
2. 探索 – 递归调用。
3. 撤销选择 – 恢复交换 / 取消标记（回溯）。

经典的原地回溯算法：

function permute(nums) {
  const result = [];

  function backtrack(index) {
    if (index === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = index; i  a - b);
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i  0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

对 [1,1,2] 的结果：

[1,1,2]
[1,2,1]
[2,1,1]

下一排列

目标： 找到字典序（词典顺序）中 Q > P 的最小排列 Q。

字典序

对于 [1,2,3]，按顺序的排列为：

123
132
213
231
312
321

下一个排列就是下一行。

算法概述

function nextPermutation(nums) {
  // 1. 找到枢轴
  let i = nums.length - 2;
  while (i >= 0 && nums[i] = 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  if (i >= 0) {
    // 2. 找到后继
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) {
      j--;
    }
    // 3. 交换
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 4. 反转后缀
  reverse(nums, i + 1);
}

function reverse(arr, start) {
  let l = start,
      r = arr.length - 1;
  while (l < r) {
    [arr[l], arr[r]] = [arr[r], arr[l]];
    l++;
    r--;
  }
}

该算法即使在存在重复值的情况下也能正确工作，因为字典序比较天然能够处理它们。

示例

• [1,1,2] → [1,2,1] → [2,1,1] → 再调用一次后回到 [1,1,2]。
• [3,2,1]（最大排列）→ 未找到枢轴 → 反转整个数组 → [1,2,3]（最小排列）。

对比表

常见陷阱：忘记回溯

在生成所有排列时，如果未恢复先前状态（交换回去或取消标记），会导致结果错误或出现重复的排列。回溯步骤对于独立探索每个分支是必不可少的。

摘要

• 全排列 通过递归和回溯教授穷举状态探索。
• 回溯 强调 选择 → 探索 → 撤销 的模式，这在许多组合问题中至关重要。
• 下一个排列 展示了在字典序中前进一步的最小贪心改动，只使用 O(1) 额外空间。

这两种技术都是问题求解者武器库中的必备工具。 👍