当前位置：首页 > JavaScript

js实现排列

2026-01-31 20:57:09JavaScript

排列的基本概念

排列是指从一组元素中按照一定顺序选取部分或全部元素的所有可能组合方式。在JavaScript中，排列可以通过递归或迭代的方式实现。

递归实现排列

递归方法通过不断缩小问题规模来生成所有排列。每次选择一个元素作为排列的第一个元素，然后递归处理剩余元素。

function permute(arr) {
  let result = [];

  if (arr.length === 1) {
    return [arr];
  }

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
    const remainingPerms = permute(remaining);

    for (const perm of remainingPerms) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

// 示例用法
console.log(permute([1, 2, 3]));

迭代实现排列

迭代方法使用堆算法（Heap's algorithm）来生成排列，避免了递归带来的栈溢出风险。

function permuteIterative(arr) {
  let result = [arr.slice()];
  let c = new Array(arr.length).fill(0);
  let i = 1;

  while (i < arr.length) {
    if (c[i] < i) {
      if (i % 2 === 0) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
      } else {
        [arr[c[i]], arr[i]] = [arr[i], arr[c[i]]];
      }
      result.push(arr.slice());
      c[i]++;
      i = 1;
    } else {
      c[i] = 0;
      i++;
    }
  }

  return result;
}

// 示例用法
console.log(permuteIterative([1, 2, 3]));

排列的优化实现

对于大型数组，可以使用生成器函数来按需生成排列，减少内存消耗。

function* permuteGenerator(arr) {
  if (arr.length === 1) {
    yield arr;
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const perm of permuteGenerator(remaining)) {
      yield [current, ...perm];
    }
  }
}

// 示例用法
for (const perm of permuteGenerator([1, 2, 3])) {
  console.log(perm);
}