Go语言实现的排列组合问题实例(n个数中取m个)

本文实例讲述了Go语言实现的排列组合问题。分享给大家供大家参考，具体如下：

（一）组合问题

组合是一个基本的数学问题，本程序的目标是输出从n个元素中取m个的所有组合。

例如从[1,2,3]中取出2个数，一共有3中组合：[1,2],[1,3],[2,3]。（组合不考虑顺序，即[1,2]和[2,1]属同一个组合）

本程序的思路（来自网上其他大神）：

（1）创建有n个元素数组，数组元素的值为1表示选中，为0则没选中。
（2）初始化，将数组前m个元素置1，表示第一个组合为前m个数。
（3）从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
（4）当某次循环没有找到“10“组合时，说明得到了最后一个组合，循环结束。

例如求5中选3的组合：

1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5

效率情况：20个元素中取5个，共15504个结果，耗时约10ms.

代码实现：
复制代码 代码如下:package huawei
import (
    "fmt"
    "time"
)
/*
【排列组合问题：n个数中取m个】
*/
func Test10Base() {
    nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    m := 5
    timeStart := time.Now()
    n := len(nums)
    indexs := zuheResult(n, m)
    result := findNumsByIndexs(nums, indexs)
    timeEnd := time.Now()
    fmt.Println("count:", len(result))
    fmt.Println("result:", result)
    fmt.Println("time consume:", timeEnd.Sub(timeStart))
    //结果是否正确
    rightCount := mathZuhe(n, m)
    if rightCount == len(result) {
        fmt.Println("结果正确")
    } else {
        fmt.Println("结果错误，正确结果是：", rightCount)
    }
}
//组合算法(从nums中取出m个数)
func zuheResult(n int, m int) [][]int {
    if m < 1 || m > n {
        fmt.Println("Illegal argument. Param m must between 1 and len(nums).")
        return [][]int{}
    }
    //保存最终结果的数组，总数直接通过数学公式计算
    result := make([][]int, 0, mathZuhe(n, m))
    //保存每一个组合的索引的数组，1表示选中，0表示未选中
    indexs := make([]int, n)
    for i := 0; i < n; i++ {
        if i < m {
            indexs[i] = 1
        } else {
            indexs[i] = 0
        }
    }
    //第一个结果
    result = addTo(result, indexs)
    for {
        find := false
        //每次循环将第一次出现的 1 0 改为 0 1，同时将左侧的1移动到最左侧
        for i := 0; i < n-1; i++ {
            if indexs[i] == 1 && indexs[i+1] == 0 {
                find = true
                indexs[i], indexs[i+1] = 0, 1
                if i > 1 {
                    moveOneToLeft(indexs[:i])
                }
                result = addTo(result, indexs)
                break
            }
        }
        //本次循环没有找到 1 0 ，说明已经取到了最后一种情况
        if !find {
            break
        }
    }
    return result
}
//将ele复制后添加到arr中，返回新的数组
func addTo(arr [][]int, ele []int) [][]int {
    newEle := make([]int, len(ele))
    copy(newEle, ele)
    arr = append(arr, newEle)
    return arr
}
func moveOneToLeft(leftNums []int) {
    //计算有几个1
    sum := 0
    for i := 0; i < len(leftNums); i++ {
        if leftNums[i] == 1 {
            sum++
        }
    }
    //将前sum个改为1，之后的改为0
    for i := 0; i < len(leftNums); i++ {
        if i < sum {
            leftNums[i] = 1
        } else {
            leftNums[i] = 0
        }
    }
}
//根据索引号数组得到元素数组
func findNumsByIndexs(nums []int, indexs [][]int) [][]int {
    if len(indexs) == 0 {
        return [][]int{}
    }
    result := make([][]int, len(indexs))
    for i, v := range indexs {
        line := make([]int, 0)
        for j, v2 := range v {
            if v2 == 1 {
                line = append(line, nums[j])
            }
        }
        result[i] = line
    }
    return result
}

注：n个元素中取m个一共有多少种取法可直接通过数学公式计算得出，即：
复制代码 代码如下://数学方法计算排列数(从n中取m个数)
func mathPailie(n int, m int) int {
    return jieCheng(n) / jieCheng(n-m)
}
//数学方法计算组合数(从n中取m个数)
func mathZuhe(n int, m int) int {
    return jieCheng(n) / (jieCheng(n-m) * jieCheng(m))
}
//阶乘
func jieCheng(n int) int {
    result := 1
    for i := 2; i <= n; i++ {
        result *= i
    }
    return result
}

通过此公式可以简单的验证一下上述程序的结果是否正确。

（二）排列问题

从n个数中取出m个进行排列，其实就是组合算法之后，对选中的m个数进行全排列。而全排列的问题在之前的文章中已经讨论过了。

代码实现：
复制代码 代码如下:func pailieResult(nums []int, m int) [][]int {
    //组合结果
    zuhe := zuheResult(nums, m)
    //保存最终排列结果
    result := make([][]int, 0)
    //遍历组合结果，对每一项进行全排列
    for _, v := range zuhe {
        p := quanPailie(v)
        result = append(result, p...)
    }
    return result
}
//n个数全排列
//如输入[1 2 3]，则返回[123 132 213 231 312 321]
func quanPailie(nums []int) [][]int {
    COUNT := len(nums)
    //检查
    if COUNT == 0 || COUNT > 10 {
        panic("Illegal argument. nums size must between 1 and 9.")
    }
    //如果只有一个数，则直接返回
    if COUNT == 1 {
        return [][]int{nums}
    }
    //否则，将最后一个数插入到前面的排列数中的所有位置
    return insertItem(quanPailie(nums[:COUNT-1]), nums[COUNT-1])
}
func insertItem(res [][]int, insertNum int) [][]int {
    //保存结果的slice
    result := make([][]int, len(res)*(len(res[0])+1))
    index := 0
    for _, v := range res {
        for i := 0; i < len(v); i++ {
            //在v的每一个元素前面插入新元素
            result[index] = insertToSlice(v, i, insertNum)
            index++
        }
        //在v最后面插入新元素
        result[index] = append(v, insertNum)
        index++
    }
    return result
}
//将元素value插入到数组nums中索引为index的位置
func insertToSlice(nums []int, index int, value int) []int {
    result := make([]int, len(nums)+1)
    copy(result[:index], nums[:index])
    result[index] = value
    copy(result[index+1:], nums[index:])
    return result
}

希望本文所述对大家Go语言程序设计有所帮助。

# Go语言  # 排列  # 组合  # Golang排列组合算法问题之全排列实现方法  # Go语言对字符串进行SHA1哈希运算的方法  # GO语言运行环境下载、安装、配置图文教程  # go语言文件正则表达式搜索功能示例  # Go语言正则表达式用法实例小结【查找、匹配、替换等】  # Go语言中三种不同md5计算方式的性能比较  # Go语言中反射的正确使用  # PHP与Go语言之间的通信详解  # 深入理解GO语言的面向对象  # 利用Go语言实现简单Ping过程的方法  # Go语言如何并发超时处理详解  # 中取  # 第一个  # 将其  # 没有找到  # 是否正确  # 是一个  # 左端  # 排列组合  # 过了  # 遍历  # 大神  # 给大家  # 有几个  # 只有一个  # 可直接  # 所述  # 时将  # 值为  # 每一项  # 得到了 

相关文章： 如何在阿里云完成域名注册与建站？  建站为何优先选择香港服务器？  C#如何序列化对象为XML XmlSerializer用法  html制作网站的步骤有哪些,iapp如何添加网页？  如何解决VPS建站LNMP环境配置常见问题？  b2c电商网站制作流程,b2c水平综合的电商平台？  企业在线网站设计制作流程,想建设一个属于自己的企业网站，该如何去做？  如何通过wdcp面板快速创建网站？  外贸公司网站制作哪家好,maersk船公司官网？  平台云上自主建站：模板化设计与智能工具打造高效网站  上海制作企业网站有哪些,上海有哪些网站可以让企业免费发布招聘信息？  已有域名建站全流程解析：网站搭建步骤与建站工具选择  如何制作公司的网站链接,公司想做一个网站，一般需要花多少钱？  如何快速搭建二级域名独立网站？  高防服务器如何保障网站安全无虞？  怎么制作网站设计模板图片,有电商商品详情页面的免费模板素材网站推荐吗？  Android自定义控件实现温度旋转按钮效果  微信小程序制作网站有哪些,微信小程序需要做网站吗？  建站之星后台管理：高效配置与模板优化提升用户体验  GML (Geography Markup Language)是什么，它如何用XML来表示地理空间信息？  网站制作的步骤包括,正确网址格式怎么写？  网站制作软件有哪些,制图软件有哪些？  如何破解联通资金短缺导致的基站建设难题？  如何在建站宝盒中设置产品搜索功能？  枣阳网站制作,阳新火车站打的到仙岛湖多少钱？  如何彻底卸载建站之星软件？  教育培训网站制作流程,请问edu教育网站的域名怎么申请？  电影网站制作价格表,那些提供免费电影的网站，他们是怎么盈利的？  定制建站平台哪家好？企业官网搭建与快速建站方案推荐  如何选择最佳自助建站系统？快速指南解析优劣  小型网站制作HTML,*游戏网站怎么搭建？  如何在IIS中新建站点并解决端口绑定冲突？  如何在Windows虚拟主机上快速搭建网站？  建站主机数据库如何配置才能提升网站性能？  广州商城建站系统开发成本与周期如何控制？  微信网站制作公司有哪些,民生银行办理公司开户怎么在微信网页上查询进度？  IOS倒计时设置UIButton标题title的抖动问题  nginx修改上传文件大小限制的方法  如何快速上传建站程序避免常见错误？  建设网站制作价格,怎样建立自己的公司网站？  如何选择高效便捷的WAP商城建站系统？  网站制作免费,什么网站能看正片电影？  如何在Mac上搭建Golang开发环境_使用Homebrew安装和管理Go版本  如何在景安服务器上快速搭建个人网站？  小建面朝正北，A点实际方位是否存在偏差？  再谈Python中的字符串与字符编码（推荐）  如何选择靠谱的建站公司加盟品牌？  南京做网站制作公司,南京哈发网络有限公司，公司怎么样，做网页美工DIV+CSS待遇怎么样？  建站之星安装失败：服务器环境不兼容？  如何高效配置IIS服务器搭建网站？