全排列

发现了一个种全排列的新写法，类似于洗牌

原始写法

按照我以前的写法，如下：

package main

import "fmt"

func getPerm(ori []int, cur []int, pos int, vis []bool, resP *[][]int) {  
    if pos == len(ori) {
        *resP = append(*resP, append([]int{}, cur...))
        return
    }
    for i := 0; i < len(ori); i++ {
        if !vis[i] {
            vis[i] = true
            cur[pos] = ori[i]
            getPerm(ori, cur, pos+1, vis, resP)
            vis[i] = false
        }
    }
}

func main() {  
    ori := []int{11, 22, 33, 44, 55}
    res := make([][]int, 0)

    getPerm(ori, make([]int, len(ori)), 0, make([]bool, len(ori)), &res)

    for i := 0; i < len(res); i++ {
        fmt.Print(res[i])
        fmt.Printf("\n")
    }
}

新写法

模拟洗牌
本质是

任何一个置换都可以表示为不相交轮换的乘积，若不计因子的顺序，其分解式是唯一的。

package main

import "fmt"

func nextPerm(p []int) {  
    for i := len(p) - 1; i >= 0; i-- {
        if i == 0 || p[i]+1+i < len(p) {
            p[i]++
            return
        }
        p[i] = 0
    }
}

func getPerm(ori []int, p []int) []int {  
    cur := append([]int{}, ori...)
    for k, v := range p {
        cur[k], cur[k+v] = cur[k+v], cur[k]
    }
    return cur
}

func main() {  
    ori := []int{11, 22, 33, 44, 55}

    for p := make([]int, len(ori)); p[0] < len(p); nextPerm(p) {
        cur := getPerm(ori, p)
        fmt.Println(cur)
    }
}