无重复字符串的排列组合(golang)

栏目: IT技术 · 发布时间: 1个月前

来源: studygolang.com

内容简介:假设已经得到了除了当前字符之外的其它字符拼接好的字符串,则与当前字符进行拼接。递归的想法是0..i的字符不变,将i..n-1的字符排列组合进行拼接。动态规划的想法是:将第i个字符换为每个可以替换的字符,可以替换的字符是i+1往后的所有字符。将替换后的结果存储下来,在此基础上的所有字符串替换下一个i+1字符为所有可以替换的字符,即可保证获得所有的排列组合。这个想法更接近排列组合的算法思想。

本文转载自:https://studygolang.com/articles/29674,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有。

方法一:递归

假设已经得到了除了当前字符之外的其它字符拼接好的字符串,则与当前字符进行拼接。

func permutation(S string) []string {
    if len(S) == 1 {
        return []string{S}
    }
    // 与拼接得到的各个字符串再进行拼接
    ret := []string{}
    for i, s := range S {
        // 差了第i个字符的剩余字符串往下传,并将得到的结果进行合并
        tmp := fmt.Sprintf("%s%s", S[:i], S[i+1:])
        res := permutation(tmp)
        for _, r := range res {
            ret = append(ret, fmt.Sprintf("%c%s", s, r))
        }
    }
    return ret
}

方法二:动态规划

递归的想法是0..i的字符不变,将i..n-1的字符排列组合进行拼接。动态规划的想法是:将第i个字符换为每个可以替换的字符,可以替换的字符是i+1往后的所有字符。将替换后的结果存储下来,在此基础上的所有字符串替换下一个i+1字符为所有可以替换的字符,即可保证获得所有的排列组合。这个想法更接近排列组合的算法思想。

func permutation(S string) []string {
    if len(S) == 1 {
        return []string{S}
    }
    // 在交换完第i个的所有字符串的基础上进行下一次交换
    list := []string{S}
    l := len(S)
    for i := 0; i < l-1; i ++ {
        for _, item := range list {
            for j := i + 1; j < l; j ++ {
                s := []byte(item)
                s[i], s[j] = s[j], s[i]
                list = append(list, fmt.Sprintf("%s", s))
            }
        }
    }
    return list
}

欢迎关注我们的微信公众号,每天学习 Go 知识

无重复字符串的排列组合(golang)

以上所述就是小编给大家介绍的《无重复字符串的排列组合(golang)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

关注码农网公众号

关注我们,获取更多IT资讯^_^


为你推荐:

相关软件推荐:

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

组合数学

组合数学

(美)Richard A. Brualdi / 冯速 等 / 机械工业出版社 / 2012-5 / 69.00元

本书是系统阐述组合数学基础、理论、方法和实例的优秀教材,出版三十多年来多次改版,被MIT、哥伦比亚大学、UIUC、威斯康星大学等众多国外高校采用,对国内外组合数学教学产生了较大影响,也是相关学科的主要参考文献之一。 本书侧重于组合数学的概念和思想,包括鸽巢原理、计数技术、排列与组合、P條ya计数法、二项式系数、容斥原理、生成函数和递推关系以及组合结构(匹配、试验设计、图)等,深入浅出地表达了......一起来看看 《组合数学》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

随机密码生成器
随机密码生成器

多种字符组合密码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具