递归解法

以数组[1, 2, 3, 4]为例,返回全排列

分析:

问题可以拆分为

  • 1 - 2,3,4 (表示提前元素1和剩余元素2,3,4的全排列)
  • 2 - 1,3,4
  • 3 - 1,2,4
  • 4 - 1,2,3

以上四种情况的并集

var permutation = function (nums) {
    let result = []

    function swap(i, j) {
        let t = nums[i]
        nums[i] = nums[j]
        nums[j] = t
    }

    function recall(from, to) {
        if (from === to) {
            result.push([...nums])
            return
        }
        for (let i = from; i <= to; i++) {  // 遍历所有元素
            swap(from, i)               // 让数组中不同元素提前
            recall(from + 1, to)        // 剩下元素做全排列
            swap(from, i)               // 恢复成原来的数组
        }
    }

    recall(0, nums.length - 1)

    return result
}

拓展

如果数组中元素有重复的情况,如何处理?

以[1,2,2,3]为例

问题拆分

  • 1 - 2,2,3 (表示1和2,3,4的全排列)
  • 2 - 1,2,3
  • 3 - 1,2,2

对于下标为1,2的两个元素值都为2,所以只需要进行一次求解2和1,2,3全排列的操作

var permutation = function (nums) {
    let result = []

    function swap(i, j) {
        let t = nums[i]
        nums[i] = nums[j]
        nums[j] = t
    }

    function recall(from, to) {
        if (from === to) {
            result.push([...nums])
            return
        }
        let swapped = new Set()             // 提前元素集合
        for (let i = from; i <= to; i++) {  // 遍历所有元素
            if (swapped.has(nums[i])){      // 判断当前元素是否已经存在被提前的情况
                continue
            }
            swapped.add(nums[i])        // 加入提前元素集合
            swap(from, i)               // 让数组中不同元素提前
            recall(from + 1, to)        // 剩下元素做全排列
            swap(from, i)               // 恢复成原来的数组
        }
    }

    recall(0, nums.length - 1)

    return result
}

非递归解法

以 A[1,2,3,4,5]为例

思考

依次从小到大输出,即为所有全排列

步骤

  • 求出最小数列(所有元素顺序为递增的)
  • 递增,求当前数列的下一个数列
  • 直到最大数列(所有元素顺序为递减的)结束

问题:如何得到比当前数列大的下一个数列呢?

  • 从后往前找,直到A[j - 1] < A[j]
  • 找到[j, A.length-1] 中 最小的元素Min[j, A.length-1] ,交换A[j-1]和Min[j, A.length-1]
  • 将[j, A.length - 1]反转

通过以上三步即可得到比当前数列大的下一个数列

/**
 * 全排列
 * 非递归算法
 */
var permutation = function (nums) {
    let result = []

    function swap(i, j) {
        let tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
    }

    function reverse(start, end) {
        if (start >= end) {
            return
        }
        swap(start, end)
        reverse(++start, --end)
    }

    function minIndex(start, end) {
        if (start >= end) {
            return start
        }
        let min = Number.MAX_SAFE_INTEGER, minIndex = start
        for (let i = start; i <= end; i++) {
            if (nums[i] > nums[start - 1]) {
                min = Math.min(nums[i], min)
                minIndex = i
            }
        }
        return minIndex
    }

    function next(nums) {                               // 递增,求当前数列的下一个数列
        hasNext = false
        for (let j = nums.length - 1; j >= 1; j--) {
            if (nums[j - 1] >= nums[j]) {               // 元素递减,继续向队列头部遍历
                continue
            }
            hasNext = true
            let pos = minIndex(j, nums.length - 1)      // 求[j, length-1]中大于nums[j-1]的最小值下标
            swap(pos, j - 1)                            // 交换j-1和Min[j, length-1]
            reverse(j, nums.length - 1)                 // 反转 [j, length-1]
            break
        }
        return nums
    }

    nums = nums.sort(function (a, b) {
        return a - b
    })
    let hasNext = true
    while (hasNext) {
        result.push([...nums])
        nums = next(nums)
    }
    return result
}

思考:如果有重复元素怎么办?

解答:因为是按递增顺序进行排列的,重复也不会有影响。

练习题

【leetcode】46. 全排列