几种计算全排列的方法
基于golang实现，有非并发实现和并发实现
递归
全排列问题，比如打印1-9的共9个字母的全排列。先输出1，然后是2-9的全排列，输出2，然后1-9中去除2的全排列。于是很自然想到递归的方法。写出伪代码：
permutaion(prefix, set) {
if set 为空
print prefix
for s in set:
permuetaion(prefix+s, set - s)
}
go递归实现
func permutaionImpl(prefix []byte, s []byte, cur int) {
if cur == len(s) {
fmt.Println(prefix)
return
}
for _, b := range s {
exist := false
for i := 0; i < cur; i++ {
if prefix[i] == b {
exist = true
break
}
}
if !exist {
prefix[cur] = b
permutaionImpl(prefix, s, cur+1)
}
}
}
func Permutation(s []byte) {
//前缀slice
p := make([]byte, len(s), len(s))
permutaionImpl(p, s, 0)
}
并发1
刚才实现的是go单线程执行的，改成并发版本的, 参考rob pike讲Go Concurrency Patterns，多个goroutine通过channel连接起来。goroutine1发送1给goroutine2, goroutine2发送12给goroutine3，goroutine3发送123给goroutine4， 以此类推。
func prefixIncrement(in []byte, s []byte, next chan []byte) {
for _, c := range s {
exist := false
for _, e := range in {
if e == c {
exist = true
break
}
}
if exist {
continue
}
temp := make([]byte, 0)
temp = append(temp, in...)
temp = append(temp, c)
next <- temp
}
}
func permutaionConImpl(req chan []byte, out chan []byte, s []byte) {
go func() {
//递归退出条件: len(v) == len(s)-1
v, ok := <-req
if !ok {
return
}
next := out
if len(v) != len(s)-1 {
next = make(chan []byte)
permutaionConImpl(next, out, s)
}
prefixIncrement(v, s, next)
for in := range req {
prefixIncrement(in, s, next)
}
close(next)
}()
}
// PermutationConcurrency 并发计算全排列
func PermutationConcurrency(s []byte) {
req, out := make(chan []byte), make(chan []byte)
//开启goroutine计算
permutaionConImpl(req, out, s)
over := make(chan struct{})
//要开goroutine读取out，如果放在主函数中，会导致死锁。
go func() {
for res := range out {
fmt.Println(res)
}
close(over)
}()
for _, c := range s {
sl := []byte{c}
req <- sl
}
close(req)
<-over
}
并发2
并发1中把每个排列的阶段拆分到不同的goroutine， 从goroutine1开始每个goroutine越来越繁忙，最后一个goroutine要输出n!个slice，任务轻重很不均衡。于是也可以考虑让每个goroutine做同样的事情，比如下面的实现
func PermutationConcurrencyVertical(s []byte) {
var sg sync.WaitGroup
for _, c := range s {
sg.Add(1)
//要传参数进去，避免只取到最后一个值
go func(k byte) {
p := make([]byte, len(s), len(s))
p[0] = k
permutaionImpl(p, s, 1)
defer sg.Done()
}(c)
}
sg.Wait()
}
并发3
如果能提前知道要开几个goroutine，那就可以不用递归的方式创建goroutine了，代码逻辑会更清晰易懂。
func permutaionCal(left chan []byte, right chan []byte, s []byte) {
for v := range left {
prefixIncrement(v, s, right)
}
close(right)
}
func PermutaionChain(s []byte) {
leftmost := make(chan []byte)
left := leftmost
right := leftmost
for i := 0; i < len(s)-1; i++ {
right = make(chan []byte)
go permutaionCal(left, right, s)
left = right
}
go func(c chan []byte) {
for _, v := range s {
c <- []byte{v}
}
close(c)
}(leftmost)
for v := range right {
fmt.Println(v)
}
}
对比
benchmark 4个byte的全排列：
递归 5000 308919 ns/op 768 B/op 24 allocs/op
并发1 5000 382600 ns/op 1774 B/op 93 allocs/op
并发3 5000 310740 ns/op 1675 B/op 92 allocs/op
benchmark 7个byte的全排列：
递归 20 62281150 ns/op 161372 B/op 5040 allocs/op
并发1 20 71853908 ns/op 275384 B/op 18781 allocs/op
并发3 20 84848114 ns/op 275663 B/op 18780 allocs/op
递归版本最快，分配内存最少，应为中间结果都是写入一个前缀slice的，通过cur下标来标记slice的结尾。并发版本要在不同的goroutine之间传递slice，分配的内存相对多一些。在这个例子中，并发没有表现出比单线程更快，原因可能是每个goroutine的计算过程较短，不能充分发挥出多核的优势，反而将时间浪费在了goroutine之间的消息传递上。
