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的组合:
11100//1,2,3
11010//1,2,4
10110//1,3,4
01110//2,3,4
11001//1,2,5
10101//1,3,5
01101//2,3,5
10011//1,4,5
01011//2,4,5
00111//3,4,5
效率情况:20个元素中取5个,共15504个结果,耗时约10ms.
代码实现:
packagehuawei import( "fmt" "time" ) /* 【排列组合问题:n个数中取m个】 */ funcTest10Base(){ 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("timeconsume:",timeEnd.Sub(timeStart)) //结果是否正确 rightCount:=mathZuhe(n,m) ifrightCount==len(result){ fmt.Println("结果正确") }else{ fmt.Println("结果错误,正确结果是:",rightCount) } } //组合算法(从nums中取出m个数) funczuheResult(nint,mint)[][]int{ ifm<1||m>n{ fmt.Println("Illegalargument.Parammmustbetween1andlen(nums).") return[][]int{} } //保存最终结果的数组,总数直接通过数学公式计算 result:=make([][]int,0,mathZuhe(n,m)) //保存每一个组合的索引的数组,1表示选中,0表示未选中 indexs:=make([]int,n) fori:=0;i<n;i++{ ifi<m{ indexs[i]=1 }else{ indexs[i]=0 } } //第一个结果 result=addTo(result,indexs) for{ find:=false //每次循环将第一次出现的10改为01,同时将左侧的1移动到最左侧 fori:=0;i<n-1;i++{ ifindexs[i]==1&&indexs[i+1]==0{ find=true indexs[i],indexs[i+1]=0,1 ifi>1{ moveOneToLeft(indexs[:i]) } result=addTo(result,indexs) break } } //本次循环没有找到10,说明已经取到了最后一种情况 if!find{ break } } returnresult } //将ele复制后添加到arr中,返回新的数组 funcaddTo(arr[][]int,ele[]int)[][]int{ newEle:=make([]int,len(ele)) copy(newEle,ele) arr=append(arr,newEle) returnarr } funcmoveOneToLeft(leftNums[]int){ //计算有几个1 sum:=0 fori:=0;i<len(leftNums);i++{ ifleftNums[i]==1{ sum++ } } //将前sum个改为1,之后的改为0 fori:=0;i<len(leftNums);i++{ ifi<sum{ leftNums[i]=1 }else{ leftNums[i]=0 } } } //根据索引号数组得到元素数组 funcfindNumsByIndexs(nums[]int,indexs[][]int)[][]int{ iflen(indexs)==0{ return[][]int{} } result:=make([][]int,len(indexs)) fori,v:=rangeindexs{ line:=make([]int,0) forj,v2:=rangev{ ifv2==1{ line=append(line,nums[j]) } } result[i]=line } returnresult }
注:n个元素中取m个一共有多少种取法可直接通过数学公式计算得出,即:
//数学方法计算排列数(从n中取m个数) funcmathPailie(nint,mint)int{ returnjieCheng(n)/jieCheng(n-m) } //数学方法计算组合数(从n中取m个数) funcmathZuhe(nint,mint)int{ returnjieCheng(n)/(jieCheng(n-m)*jieCheng(m)) } //阶乘 funcjieCheng(nint)int{ result:=1 fori:=2;i<=n;i++{ result*=i } returnresult }
通过此公式可以简单的验证一下上述程序的结果是否正确。
(二)排列问题
从n个数中取出m个进行排列,其实就是组合算法之后,对选中的m个数进行全排列。而全排列的问题在之前的文章中已经讨论过了。
代码实现:
funcpailieResult(nums[]int,mint)[][]int{ //组合结果 zuhe:=zuheResult(nums,m) //保存最终排列结果 result:=make([][]int,0) //遍历组合结果,对每一项进行全排列 for_,v:=rangezuhe{ p:=quanPailie(v) result=append(result,p...) } returnresult } //n个数全排列 //如输入[123],则返回[123132213231312321] funcquanPailie(nums[]int)[][]int{ COUNT:=len(nums) //检查 ifCOUNT==0||COUNT>10{ panic("Illegalargument.numssizemustbetween1and9.") } //如果只有一个数,则直接返回 ifCOUNT==1{ return[][]int{nums} } //否则,将最后一个数插入到前面的排列数中的所有位置 returninsertItem(quanPailie(nums[:COUNT-1]),nums[COUNT-1]) } funcinsertItem(res[][]int,insertNumint)[][]int{ //保存结果的slice result:=make([][]int,len(res)*(len(res[0])+1)) index:=0 for_,v:=rangeres{ fori:=0;i<len(v);i++{ //在v的每一个元素前面插入新元素 result[index]=insertToSlice(v,i,insertNum) index++ } //在v最后面插入新元素 result[index]=append(v,insertNum) index++ } returnresult } //将元素value插入到数组nums中索引为index的位置 funcinsertToSlice(nums[]int,indexint,valueint)[]int{ result:=make([]int,len(nums)+1) copy(result[:index],nums[:index]) result[index]=value copy(result[index+1:],nums[index:]) returnresult }
希望本文所述对大家Go语言程序设计有所帮助。