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