当前位置：首页 > JavaScript

js实现排列

2026-03-13 18:57:30JavaScript

排列的概念

排列是指从一组元素中按照一定顺序选取若干个元素的所有可能组合。例如，从 [1, 2, 3] 中选取 2 个元素的排列为 [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]。

递归实现排列

递归是一种常见的排列生成方法，通过逐步固定前缀并递归处理剩余元素实现。

function permute(arr) {
  const result = [];
  const backtrack = (current, remaining) => {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      const newRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));
      backtrack(current, newRemaining);
      current.pop();
    }
  };
  backtrack([], arr);
  return result;
}

堆算法（非递归实现）

堆算法通过交换元素位置生成排列，适合内存敏感的场景。

function heapPermute(arr) {
  const result = [];
  const generate = (n, arr) => {
    if (n === 1) {
      result.push([...arr]);
      return;
    }
    for (let i = 0; i < n; i++) {
      generate(n - 1, arr);
      if (n % 2 === 0) {
        [arr[i], arr[n - 1]] = [arr[n - 1], arr[i]];
      } else {
        [arr[0], arr[n - 1]] = [arr[n - 1], arr[0]];
      }
    }
  };
  generate(arr.length, arr);
  return result;
}

使用生成器实现排列

生成器可以按需生成排列，避免一次性占用过多内存。

function* permuteGenerator(arr) {
  if (arr.length <= 1) yield arr;
  else {
    const [first, ...rest] = arr;
    for (const perm of permuteGenerator(rest)) {
      for (let i = 0; i <= perm.length; i++) {
        yield [...perm.slice(0, i), first, ...perm.slice(i)];
      }
    }
  }
}

处理重复元素的排列

当输入数组包含重复元素时，需跳过重复排列。

js实现排列

function permuteUnique(arr) {
  const result = [];
  arr.sort((a, b) => a - b);
  const backtrack = (current, remaining) => {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      if (i > 0 && remaining[i] === remaining[i - 1]) continue;
      current.push(remaining[i]);
      const newRemaining = remaining.slice(0, i).concat(remaining.slice(i + 1));
      backtrack(current, newRemaining);
      current.pop();
    }
  };
  backtrack([], arr);
  return result;
}