几种计算全排列的方法

劫客轮蹲 · · 1878 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

基于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()
}

代码地址

https://github.com/amither/go-slice/tree/master/permutation


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:劫客轮蹲

查看原文:几种计算全排列的方法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1878 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传