leetcode46：全排列

数组元素的随机组合，全排列，数列里的 C33 全排列实现
更新于: 2021-12-19 12:57:29

给出一个数字数组<Number>[], 如[1, 2, 3]， 如何打印出所有的排列A33(这里打不出来上下标，见谅)。
即： 打印出[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]。

问题分析

  1. 2个数的全排列
  2. 3个数转化为2个数
  3. 4个数转化为3个数
  4. 方法的专业名词是：邻位互换法
  5. 如果已经确定好了大小顺序：实现就是字典序法
例如：给定{1,2,3}，全排列为3！个，即：
{1,2,3}，{1,3,2}
{2,1,3}，{2,3,1}
{3,1,2}，{3,2,1}
// 2个数的情况(1,2)
[1,2]
[2,1]

// 3个数的情况，与2个数的转化关系
1, [2,3]
2, [1,3]
3, [1,2]

2个数的情况

function sf2() {
  var [n1, n2] = [].slice.call(arguments);
  return [
    [n1, n2],
    [n2, n1],
  ];
}

3个数的情况

function sf3() {
  var args = [].slice.call(arguments);
  var res = [];
  for (var i = 0; i < args.length; i++) {
    var value = args[i];
    var extra = args.slice(0);
    extra.splice(i, 1);
    var ret = sf2.apply(null, extra);
    ret.forEach((item) => {
      item.unshift(value);
    });
    res = res.concat(ret);
  }
  return res;
}

4个数的情况

function sf4() {
  var args = [].slice.call(arguments);
  var res = [];
  for (var i = 0; i < args.length; i++) {
    var value = args[i];
    var extra = args.slice(0);
    extra.splice(i, 1);
    var ret = sf3.apply(null, extra);
    ret.forEach((item) => {
      item.unshift(value);
    });
    res = res.concat(ret);
  }
  return res;
}

总结

  1. 2个数的情况
  2. 其它情况，代码其实是一模一样(参见: sf4/sf3代码)
function sf2() {
  var [n1, n2] = [].slice.call(arguments);
  return [
    [n1, n2],
    [n2, n1],
  ];
}

function sf() {
  var args = [].slice.call(arguments);
  var res = [];
  if (args.length === 2) return sf2(...args);

  for (var i = 0; i < args.length; i++) {
    var value = args[i];
    var extra = args.slice(0);
    extra.splice(i, 1);
    var ret = sf.apply(null, extra);
    ret.forEach((item) => {
      item.unshift(value);
    });
    res = res.concat(ret);
  }
  return res;
}

console.log(sf(1, 2, 3, 4));

知识点

全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
公式：全排列数f(n)=n!(定义0!=1)

 

最终实现代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function sf2() {
  var [n1, n2] = [].slice.call(arguments);
  return [
    [n1, n2],
    [n2, n1],
  ];
}

function permute(nums) {
  var args = nums;
  var res = [];
  if (args.length === 1) return [ args ];
  if (args.length === 2) return sf2(...args);

  for (var i = 0; i < args.length; i++) {
    var value = args[i];
    var extra = args.slice(0);
    extra.splice(i, 1);
    var ret = permute(extra);
    ret.forEach((item) => {
      item.unshift(value);
    });
    res = res.concat(ret);
  }
  return res;
}

 

参考