↓Skip to main content

全排列算法

·1648 words·8 mins· 📖
Permutations
Table of Contents

A permutation is an act of arranging the objects or numbers in order. Combinations are the way of selecting the objects or numbers from a group of objects or collection, in such a way that the order of the objects does not matter.

排列组合是组合/离散数学中的基础和重要的概念。

$$ P_n^m = A_n^m = n(n-1)(n-2)…(n-m+1) = \frac {n!}{(n-m)!} $$

当 \(n = m\) 时，也就是全排列：

\(P_n = n(n-1)(n-2)…3 \times 2 \times 1 = n!\)

默认是不放回排列，如果是重复排列，那么排列数就是 \(n^m\)

哈哈，跑偏了，这篇不是要演示 KaTex 的用法 （虽然确实挺有意思的 😹）

应用 #

排列算法 #

我们知道排列数是阶乘级增长，10个数的排列就达到了 \(10! = 3628800\)，百万级的规模。

所以，即使我们 O(1) 生成一个排列，那生成全排列的算法复杂度也是 O(n!)，非常恐怖。

在 wiki1 上有一个有意思的图，表示了九种算法，生成全排列的顺序。

Ordering of all permutations of length \({\displaystyle n=4}\) generated by different algorithms. The permutations are color-coded, where 1[❤️], 2[💛], 3[💚], 4[💙]

这九种算法分别是：

  1. 字典序
  2. 邻位对换法
  3. Heap 算法
  4. Ehrlich’s star-transposition algorithm
  5. Zaks’ prefix reversal algorithm
  6. Sawada-Williams’ algorithm
  7. Corbett’s algorithm
  8. Single-track ordering
  9. Single-track Gray code

下面是参考了一些网站2，用 Swift 实现常见的全排列生成算法。

回溯法 #

主要思路：交换、排列、恢复

func permute1(_ nums: [Int]) -> [[Int]] {
    TICK()
    var ans = [[Int]]()
    func _p(_ a: [Int], _ l: Int, _ r: Int) {
        var tmp = a
        if l == r {
            ans.append(a)
            return
        }
        for i in l...r {
            tmp.swapAt(l, i)
            _p(tmp, l + 1, r)
            tmp.swapAt(i, l)
        }
    }
    _p(nums, 0, nums.count - 1)
    TOCK()
    return ans
}

插入法 #

主要思路：对于 n 的全排列，将第 n+1 个数，插入到 (0…n) 这 n+1 个位置就可以得到 n+1 的全排列。

func permute2(_ nums: [Int]) -> [[Int]] {
    TICK()
    let ans : [[Int]] = nums.reduce([[]], { partialResult, a in
        var nextResult = [[Int]]()
        for lastArray in partialResult {
            let sz = lastArray.count
            // 将 a 插入到 n-1 排列中的 sz 个位置
            for i in (0...sz) {
                // ArraySlice<Int> 类型
                let temp = lastArray[0..<i] + [a] + lastArray[i..<sz]
                nextResult.append(Array(temp))
            }
        }
        return nextResult
    })
    TOCK()
    return ans
}

reduce 是个挺有意思的方法，有两个参数，一个是初始值，一个是闭包，闭包接收两个参数，一是上一步的结果，另一个是序列中的值。

上面的代码等价于：

var ans : [[Int]] = [[]]
for i in 0..<nums.count {
    var nextResult = [[Int]]()
    for (_, item) in ans.enumerated() {
        let sz = item.count
        // 将 a 插入到 n-1 排列中的 sz 个位置
        for k in (0...sz) {
            // ArraySlice<Int> 类型
            let temp = item[0..<k] + [nums[i]] + item[k..<sz]
            nextResult.append(Array(temp))
        }
    }
    ans = nextResult
}

字典序 #

  • 首次定义全升序为最小的序列，全降序为最大的序列。

  • 问题变成从最小逐一生成下一个排列，生成下一个排列(nextPermutation) 的算法有四步：

    1. 从后向前找到第一个逆序的位置 \(j\), 即 \(p_j < p_{j+1} >= p_{j+2}\)
    2. 重新从后向前找到第一个比 \(p_j\) 大的数 \(p_k\)，由于 \([j+1, n)\) 是降序的 (第一步决定)， \(k\) 必然也是满足这个条件的最小的数，即 \(P_k = \min\{P_i | P_i > P_j, i > j\}\)
    3. 交换 \(j\) 和 \(k\) 位置的数
    4. 将 \([j+1, n)\) 反转 (降序变升序，其实就是重排序)
func permute3(_ nums: [Int]) -> [[Int]] {
    TICK()
    let nextPermutation : ([Int]) -> [Int]? = {
        array in
        var result = array
        let sz = array.count
        var j = -1
        // 找到第一个比后面数小的数
        for i in (0..<sz-1).reversed() {
            if result[i] < result[i+1] {
                j = i;
                break;
            }
        }
        // 找不到说明已经是全逆序，即最后一个排列
        if (j == -1) {
            return nil
        }
        var k = -1
        // 找到 [j+1, sz) 中比 j 大的数中最小的一个 k
        // 第一个就是最小的，因为 [j+1, sz) 是递减的
        for i in (j+1..<sz).reversed() {
            if result[i] > result[j] {
                k = i
                break
            }
        }
        // 交换 j - k
        result.swapAt(j, k)
        // [j+1, sz)
        result = Array(result[0...j] + result[j+1..<sz].reversed())
        return result
    }
    var ans = [[Int]]()
    ans.append(nums.sorted())
    while let next = nextPermutation(ans.last!) {
        ans.append(next)
    }
    TOCK()
    return ans
}

递归法 ✨ #

主要思路是，枚举原数组所有位置，将位置上的数移到结果数组中，直到原数组清空。

func permute4(_ nums: [Int]) -> [[Int]] {
    TICK()
    var ans = [[Int]]()
    func _p(_ a: [Int], _ result: [Int]) {
        let sz = a.count
        if sz == 0 {
            ans.append(result)
            return
        }
        for i in 0..<sz {
            let rest = Array(a[0..<i] + a[i+1..<sz])
            _p(rest, result + [a[i]])
        }
    }
    _p(nums, [])
    TOCK()
    return ans
}

邻位对换法3 #

也就是 Steinhaus–Johnson–Trotter 算法。

首先，定义升序是正方向，而对于 \(a[i] > a[j], i < j\)，就是一个逆序对。

  • 初始化一个方向数组，默认全 0，表示向左交换，如果变成 1，就是向右交换
  • 确认一个元素是否能交换（活动状态）：在它的方向上，它的邻位比自己小。

算法步骤就是：

  1. 初始化方向数组，全部向左交换
  2. 找到所有处于活动状态元素中最大的一个
  3. 将它与邻位交换
  4. 将所有大于上面这个元素（非活动状态）的其他元素方向反转
  5. 跳转 2，直至找不到这样的元素
func permute5(_ nums: [Int]) -> [[Int]] {
    TICK()
    var a = nums
    let sz = a.count
    var ans = [[Int]]()
    // -1 means left, 1 means right
    var directions = [Int](repeating: -1, count: sz)
    func _movable() -> Int? {
        var max = 1
        var pos = -1
        for i in 0..<sz {
            if a[i] < max {
                continue
            }
            if (directions[i] > 0 && i < sz - 1 && a[i] > a[i+1]) ||
                (directions[i] < 0 && i > 0 && a[i] > a[i-1]) {
                max = a[i]
                pos = i
            }
        }
        if (pos >= 0) {
            return pos
        }
        return nil
    }
    ans.append(a)
    while let max_i = _movable() {
        let max_v = a[max_i]
        a.swapAt(max_i, max_i + directions[max_i])
        // 注意：方向也要跟着交换
        directions.swapAt(max_i, max_i + directions[max_i])
        ans.append(a)
        for i in 0..<sz {
            if (a[i] > max_v) {
                directions[i] = -directions[i]
            }
        }
    }
    TOCK()
    return ans
}

相比字典序来说，邻位交换在交换这一步更快，但是查找最大可移动元素和修改方向时，需要遍历。整体来说，时间差不多。

Heap 算法4 #

func _permute6(_ nums: [Int]) -> [[Int]] {
    TICK()
    var ans = [[Int]]()
    func _heap(k: Int, a: inout [Int]) {
        if k == 1 {
            ans.append(a)
            return
        }
        // Generate permutations with k-th unaltered
        // Initially k = length(A)
        _heap(k: k-1, a: &a)
        // Generate permutations for k-th swapped with each k-1 initial
        for i in 0..<k-1 {
            // Swap choice dependent on parity of k (even or odd)
            if k % 2 == 0 {
                a.swapAt(i, k-1)
            } else {
                a.swapAt(0, k-1)
            }
            _heap(k: k-1, a: &a)
        }
    }
    var a = nums
    _heap(k: a.count, a: &a)
    TOCK()
    return ans
}

递增进位法 #

func permute7(_ nums: [Int]) -> [[Int]] {
    TICK()
    var ans = [[Int]]()
    let sz = nums.count
    var inc = [Int](repeating: 0, count: sz)
    // inc[i] 表示 (i+1) 右边比它的小的数的个数，是 (i+1) 进制数
    // inc[0] 总是 0
    func _outInc() -> String {
        let rev : [String] = inc[1...].reversed().map({ String($0) })
        return rev.joined()
    }
    
    // 最低位是 2 进制，递增时进位多
    func _increace() -> Bool {
        var i = 1
        var carry = 1
        while i < sz {
            if carry == 0 {
                break
            }
            let sum = inc[i] + carry
            inc[i] = sum % (i + 1)
            carry = sum / (i + 1)
            i += 1
        }
        // 如果还有进位，说明已经到了最大的排列
        return (carry == 0)
    }
    
    func _next() -> Bool {
        // 根据当前中介数求排列
        var p = [Int](repeating: 0, count: sz)
        for i in (0..<sz).reversed() {
            var count = 0
            var j = sz - 1
            // inc[i] + 1 的空位，放 sz - i
            while j >= 0 {
                if p[j] == 0 {
                    count += 1
                }
                if (count > inc[i]) {
                    break
                }
                j -= 1
            }
            // p[j] = i + 1
            p[j] = nums[i]
        }
        ans.append(p)
        
        //print(_outInc())
        // 中介数 + 1
        return _increace()
    }
    
    while _next() {
        
    }
    TOCK()
    return ans
}

递减进位法 #

func permute8(_ nums: [Int]) -> [[Int]] {
    TICK()
    var ans = [[Int]]()
    let sz = nums.count
    var inc = [Int](repeating: 0, count: sz)
    // inc[i] 表示 (n-i) 右边比它的小的数的个数，是 (n-i) 进制数
    // inc[sz-1] 总是 0
    func _outInc() -> String {
        let rev : [String] = inc[0..<sz-1].reversed().map({ String($0) })
        return rev.joined()
    }
    
    // 最低位是 n 进制，递增时进位少
    func _increace() -> Bool {
        var i = 0
        var carry = 1
        while i < sz - 1 {
            if carry == 0 {
                break
            }
            let sum = inc[i] + carry
            inc[i] = sum % (sz - i)
            carry = sum / (sz - i)
            i += 1
        }
        // 如果还有进位，说明已经到了最大的排列
        return (carry == 0)
    }
    
    func _next() -> Bool {
        // 根据当前中介数求排列
        var p = [Int](repeating: 0, count: sz)
        for i in 0..<sz {
            var count = 0
            var j = sz - 1
            // inc[i] + 1 的空位，放 sz - i
            while j >= 0 {
                if p[j] == 0 {
                    count += 1
                }
                if (count > inc[i]) {
                    break
                }
                j -= 1
            }
            // p[j] = sz - i
            p[j] = nums[sz - i - 1]
        }
        ans.append(p)
        
        //print(_outInc())
        // 中介数 + 1
        return _increace()
    }
    
    while _next() {
        
    }
    TOCK()
    return ans
}

可以看出来，递减进位制和递增进位制法非常类似。区别仅在于：

  • 中介数的最低位，递减法是 \(n\) 进制数，而递增法是 \(2\) 进制，这样在迭代时，递增法需要进位的次数更多。

快速排列 #

QuickPerm 算法5。

func permute9(_ nums: [Int]) -> [[Int]] {
    TICK()
    var ans = [[Int]]()
    var a = nums
    // init: [0,0,0...0]
    var p = [Int](repeating: 0, count: a.count)
    ans.append(a)
    var i = 1
    var j : Int
    while i < a.count {
        if (p[i] < i) {
            // if i is odd, j = p[i]; else 0
            j = i % 2 * p[i]
            // swap(a[i], a[j])
            (a[i], a[j]) = (a[j], a[i])
            ans.append(a)
            p[i] += 1
            i = 1
        } else {
            p[i] = 0
            i += 1
        }
    }
    TOCK()
    return ans
}

开始我没太理解这个算法的逻辑，后来看到了 Heap 算法的 非递归实现。

不能说比较相似吧，只能说一模一样。唯一的区别是这个算法改进了起始点从 i = 0 变成了 i = 1，因为 i = 0 进入循环后什么也没有变化就进入了 i = 1 的状态。但是这一点优化，在数据量巨大的情况下，是质的提升！

另外，在它的官网上，这一实现被称为 Counting，还有另一种实现叫 Countdown，区别就在于 \(P[]\) 数组的初始化和修改方式，一个递增、一个递减。

耗时统计 ⌛ #

以下是通过 TICK/TOCK 宏生成的各个算法的执行时间 （以 10 个数排列为例）

算法时间
回溯法4.97 s
插入法4.58 s
字典序8.24 s
递归法11.49 s
邻位对换法28.37 s
Heap 算法2.57 s
递增进位法16.70 s
递减对换法19.67 s
快速排列算法0.78 s

不愧是 快速排列 算法！

  • 统计宏
var g_start_time = NSDate()
public func TICK() {
    g_start_time = NSDate()
}
public func TOCK(function: String = #function) {
    print(String(format: "[%@] cost: %.2lf s", function, -g_start_time.timeIntervalSinceNow))
}

最佳实践 🚀 #

上面讲了非常多的算法，但是有些难以理解，我觉得对于同类算法，只需记住最容易理解的逻辑即可。

func permute(_ nums: [Int]) -> [[Int]] {
    guard !nums.isEmpty else { return [] }
    
    var ans = [[Int]]()
    var a = nums
    let n = nums.count
    func _p(_ index: Int) {
        if index == n {
            ans.append(a)
            return
        }
        for i in index..<n {
            a.swapAt(index, i)
            _p(index + 1)
            a.swapAt(i, index)
        }
    }
    _p(0)
    return ans
}

关于去重 #

对于有重复元素的排列6：

最容易想到的是，不管重复元素，先求出所有排列。然后再去重。

我们在上面的最佳实践上稍加改动：

func permuteUnique(_ nums: [Int]) -> [[Int]] {
    guard !nums.isEmpty else { return [] }
    
    var ans = Set<[Int]>()
    var a = nums
    let n = nums.count
    func _p(_ index: Int) {
        if index == n {
            ans.insert(a)
            return
        }
        for i in index..<n {
            a.swapAt(index, i)
            _p(index + 1)
            a.swapAt(i, index)
        }
    }
    _p(0)
    return Array(ans)
}

也还行，就是依赖 Set 的性质，有点耗时。那么怎么在求排列过程中直接忽略重复项呢？

func permuteUnique2(_ nums: [Int]) -> [[Int]] {
    guard !nums.isEmpty else { return [] }
    
    var ans = [[Int]]()
    var a = nums
    let n = nums.count
    func _p(_ index: Int) {
        if index == n {
            ans.append(a)
            return
        }
        
        var used = Set<Int>()
        for i in index..<n {
            if used.contains(a[i]) {
                continue
            }
            used.insert(a[i])
            a.swapAt(index, i)
            _p(index + 1)
            a.swapAt(index, i)
        }
    }
    _p(0)
    return ans
}

对于重复的元素只选择一次！

Cheers! 🎉

  1. https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations ↩︎

  2. https://www.baeldung.com/cs/array-generate-all-permutations ↩︎

  3. Steinhaus–Johnson–Trotter algorithm ↩︎

  4. https://en.wikipedia.org/wiki/Heap%27s_algorithm ↩︎

  5. https://www.quickperm.org/quickperm.php ↩︎

  6. https://segmentfault.com/a/1190000040142137 ↩︎

↑