本文实例讲述了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语言程序设计有所帮助。
您可能感兴趣的文章:- Golang排列组合算法问题之全排列实现方法
- Go语言对字符串进行SHA1哈希运算的方法
- GO语言运行环境下载、安装、配置图文教程
- go语言文件正则表达式搜索功能示例
- Go语言正则表达式用法实例小结【查找、匹配、替换等】
- Go语言中三种不同md5计算方式的性能比较
- Go语言中反射的正确使用
- PHP与Go语言之间的通信详解
- 深入理解GO语言的面向对象
- 利用Go语言实现简单Ping过程的方法
- Go语言如何并发超时处理详解
