百度&leetcode46：全排列问题

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

附赠leetcode地址：leetcode

本题是回溯算法的经典应用场景

1. 算法策略

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

2. 适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

3. 代码实现

我们可以写一下，数组 [1, 2, 3] 的全排列有：

先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

图片来自于：https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png

这显然是一个递归结构；

递归的终止条件是：一个排列中的数字已经选够了，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth ，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
used（object）：用于把表示一个数是否被选中，如果这个数字(num)被选择这设置为 used[num] = true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。

let permute = function(nums) {
    // 使用一个数组保存所有可能的全排列
    let res = []
    if (nums.length === 0) {
        return res
    }
    let used = {}, path = []
    dfs(nums, nums.length, 0, path, used, res)
    return res
}
let dfs = function(nums, len, depth, path, used, res) {
    // 所有数都填完了
    if (depth === len) {
        res.push([...path])
        return
    }
    for (let i = 0; i < len; i++) {
        if (!used[i]) {
            // 动态维护数组
            path.push(nums[i])
            used[i] = true
            // 继续递归填下一个数
            dfs(nums, len, depth + 1, path, used, res)
            // 撤销操作
            used[i] = false
            path.pop()
        }
      
    }
}

4. 复杂度分析

时间复杂度： O(n∗n!)，其中 n 为序列的长度

这是一个排列组合，每层的排列组合数为：A^m_n=n!/(n−m)! ，故而所有的排列有：

A¹_n + A²_n + … + A^n-1_n = n!/(n−1)! + n!/(n−2)! + … + n! = n! * (1/(n−1)! + 1/(n−2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2^n-1) < 2 * n!

并且每个内部结点循环 n 次，故非叶子结点的时间复杂度为 O(n∗n!)
空间复杂度：O(n)

leetcode

const permMutation = function (arr) {
            let res = [];
            if (arr.length <= 1) {
                return arr;
            }
            for (let i = 0; i < arr.length; i++) {
                let indexStr = arr[i];
                let otherStr = [...arr.slice(0, i), ...arr.slice(i + 1)];
                let tmp = permMutation(otherStr);
                for (let j = 0; j < tmp.length; j++) {
                    res.push(Array.prototype.flat.call([indexStr, tmp[j]], Infinity));
                }
            }
            return res;
        }

var permute = function(nums) {
  let len = nums.length;
  if(len === 0) return [[]];
  let res = [];
  let perm = function(arr, p, q, res){
    if(p === q){
      res.push([...arr])
    }
    for(let i = p; i <= q; i++){
      swap(arr, i, p);
      perm(arr, p+1, q, res);
      swap(arr, i, p);
    }
  }
  let swap = function(arr, left, right){
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
  }
  perm(nums, 0, len-1, res)
  return res;
};

题解
1.分析示列，不难发现全排列，首先将每个元素排到第一位。
2.剩余元素再重复第一步操作，依次处理各个元素。
3.通过1，2两步操作，可以利用递归实现操作，但是有个地方需要特别处理，就是对于移动的元素，
在递归操作之前，和之后该如何操作。
4.由此产生两种解决办法，一种是利用回溯，定义回溯状态标识，在递归操作完成后，重置状态
一种是利用swap函数（交换元素位置）；相对来说，swap函数更好理解一些；
5.递归函数实现：
递归终止条件：
1.swap
子全排列的数组长度等于nums的长度时，递归终止。
2.dfs
子全排列所在层数（depth）等于nums的长度时，递归终止。

循环数组内部元素：
1.swap
通过swap，将nums[i] 与 p(从0开始)交换
调用递归函数prem，传入 nums, p+1, nums.lenght, res（结果集）
递归内部可以理解为，例如1，2，3 先将1取出，求解剩余2，3 的全排列，依次类推
当递归终止后，再次调用swap函数，将数组重置成原始状态；

2.dfs
dfs函数中传入nums，len，depth（当前所在层数），path（存储当前排列结果的动态数组），
used（元素是否已存在排列中的布尔标识）， res（结果集）
调用递归dfs，判断当前元素是否在排列中used[i] === true ?，存在则跳过，不存在则
used[i] = true，将当前nums[i] 存入path中，然后调用dfs
dfs终止后，***重点来了，回溯状态需要重置，used[i] = false，path.pop() 将当前元素从已有排列中删除

全排列属于回溯入门问题，回溯还是需要多学多练

swap解法

var permute = function(nums) {
  let len = nums.length;
  if(len === 0) return [[]];
  let res = [];
  let perm = function(arr, p, q, res){
    if(p === q){
      res.push([...arr])
    }
    for(let i = p; i < q; i++){
      swap(arr, i, p);
      perm(arr, p+1, q, res);
      swap(arr, i, p);
    }
  }
  let swap = function(arr, left, right){
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
  }
  perm(nums, 0, len, res)
  return res;
};

dfs解法

var permute = function(nums) {
  let len = nums.length;
  if(len === 0) return [[]];
  let res = [];
  let path = []; //维护动态数组
  let used = {}; //保存已存在的元素
  let dfs = function(arr, len, depth, path, used, res){
    if(len === depth){
      res.push([...path]);
      return
    }
    for(let i = 0; i < len; i++){
      if(!used[i]){
        path.push(arr[i]);
        used[i] = true;
        dfs(arr, len, depth+1, path, used, res)
        //状态回溯
        used[i] = false;
        path.pop();
      }
    }
  }
  dfs(nums, len, 0, path, used, res);
  return res;
}

const permute = nums => {
const res = [];
const len = nums.length;
const curr = [];
const use = {};
if (curr.length === len) {
res.push(curr);
}

function dfs (nth) {
for (let i = 0; i < len; i++) {
if (!use[i]) {
use[i] = 1;
curr.push(nums[i]);
dfs(i);
curr.pop();
use[i] = 0;
}
}
}

dfs(0);
return res;
};

感觉递归函数不需参数也可以

function fn(arr) {
    const path = [], used = {}
    const res = []
    const loopFn = () => {
        if (path.length === arr.length) {
            res.push([...path])
            return
        }
        for (let i = 0, len = arr.length; i < len; i++){
            if (!used[i]) {
                path.push(arr[i])
                used[i] = true
                loopFn()
                path.pop()
                used[i] = false
            }
        }
    }
    loopFn()
    return res
}

function bar(list) {
  const res = [];
  function dfs(arr = []) {
    if (arr.length === list.length) {
      res.push([...arr]);
      return;
    }
    for (const item of list) {
      if (arr.indexOf(item) === -1) {
        arr.push(item);
        dfs(arr);
        arr.pop();
      }
    }
  }
  dfs([]);
  return res;
}

const res = bar([1, 2, 3]);
console.log(res);

/**
 * 回溯算法
 * @param {number[]} nums 
 */
function permute(nums) {
    let res = []

    function dfs(track) {
        // 到达决策树底部
        if (track.length === nums.length) {
            res.push([...track])
            return
        }

        for (let num of nums) {
            // 剪枝操作，避免重复遍历
            if (track.includes(num)) {
                continue
            }

            track.push(num)

            dfs(track)

            track.pop()
        }
    }

    dfs([])

    return res
}

console.log(permute([1,2,3]));

Navigation Menu

Repository navigation

百度&leetcode46：全排列问题 #102

1. 算法策略

2. 适用场景

3. 代码实现

4. 复杂度分析

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

百度&leetcode46：全排列问题 #102

Description

Activity

sisterAn commented on Sep 1, 2020

1. 算法策略

2. 适用场景

3. 代码实现

4. 复杂度分析

Jeckhenry commented on Sep 2, 2020

marlboroKay commented on Sep 3, 2020

marlboroKay commented on Sep 3, 2020

DCbryant commented on Sep 22, 2020

syc666 commented on Dec 24, 2020

z253573760 commented on Feb 2, 2021

fengmiaosen commented on Aug 1, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions