> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# 全排列
- URL: https://blog.hacking.pub/2019/05/24/quan-pai-lie/
- Published: 2019-05-24T09:56:53.000Z
- Updated: 2019-05-24T09:56:53.000Z
- Author: chainhelen

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

##### 原始写法

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

```
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)
	}
}

```