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语言程序设计有所帮助。

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2017-05-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

计算属性的setter和getter

        刚才通过计算lastName和firstName获取了整个姓名,当时我们只是通过一直的data对象中属性进行合成的,这个也就是计算属性(comp...

27710
来自专栏Golang语言社区

Go语言的fmt包中文教程

Fmt包 import "fmt" 简介 ▾ Package fmt包含有格式化I/O函数,类似于C语言的printf和scanf。格式字符串的规则来源于C但更...

46370
来自专栏Golang语言社区

【Go 语言社区】Golang 语言再谈接口

Go编程提供所谓的接口是另一种数据类型,代表了一组方法签名。结构数据类型实现这些接口对接口的方法签名,并其实现方法具体定义。 Syntax /* define ...

369150
来自专栏十月梦想

类的传参以及super属性和super对象

在上述例子我们也看到了指定的子类特有的方法直接指定,那么我们如何指定子类特有的属性呢?我们这里用到了super方法;

14520
来自专栏Golang语言社区

【JS游戏编程基础】关于js里的this关键字的理解

this关键字在c++,java中都提供了这个关键字,在刚开始学习时觉得有难度,但是只要理解了,用起来就方便多了,下面通过本篇文章给大家详解js里this关键字...

495100
来自专栏柠檬先生

你不知道的javaScript笔记(6)

语法   语句表达式       句子是完整表达某个意思的一组词,由一个或多个短语组成,他们之间由标点符号或者连接词连接起来。       语句相当于句子,表达...

22270
来自专栏C/C++基础

C#常见转义字符

·一种特殊的字符常量; ·以反斜线"\"开头,后跟一个或几个字符。 ·具有特定的含义,不同于字符原有的意义,故称“转义”字符。 ·主要用来表示那些用一般...

8510
来自专栏Golang语言社区

Go语言的fmt包中文教程

Fmt包 import "fmt" 简介 ▾ Package fmt包含有格式化I/O函数,类似于C语言的printf和scanf。格式字符串的规则来源于C但更...

26660
来自专栏无所事事者爱嘲笑

关于setTimeout和setInterval的函数参数问题

17720
来自专栏猿人谷

一个正则表达式测试(只可输入中文、字母和数字)

  在项目中碰到了正则表达式的运用,正则还是非常强大的,不管什么编程语言,基本上都可以用到。之前在用java时特别是对用户名或密码使用正则非常爽,写脚本上用正则...

99860

扫码关注云+社区

领取腾讯云代金券