本文實(shí)例講述了Go語言實(shí)現(xiàn)的排列組合問題。分享給大家供大家參考，具體如下：
（一）組合問題
組合是一個(gè)基本的數(shù)學(xué)問題，本程序的目標(biāo)是輸出從n個(gè)元素中取m個(gè)的所有組合。
例如從[1,2,3]中取出2個(gè)數(shù)，一共有3中組合：[1,2],[1,3],[2,3]。（組合不考慮順序，即[1,2]和[2,1]屬同一個(gè)組合）
本程序的思路（來自網(wǎng)上其他大神）：
（1）創(chuàng)建有n個(gè)元素?cái)?shù)組，數(shù)組元素的值為1表示選中，為0則沒選中。
（2）初始化，將數(shù)組前m個(gè)元素置1，表示第一個(gè)組合為前m個(gè)數(shù)。
（3）從左到右掃描數(shù)組元素值的“10”組合，找到第一個(gè)“10”組合后將其變?yōu)椤?1”組合，同時(shí)將其左邊的所有“1”全部移動(dòng)到數(shù)組的最左端。
（4）當(dāng)某次循環(huán)沒有找到“10“組合時(shí)，說明得到了最后一個(gè)組合，循環(huán)結(jié)束。
例如求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個(gè)元素中取5個(gè)，共15504個(gè)結(jié)果，耗時(shí)約10ms.
代碼實(shí)現(xiàn)：
復(fù)制代碼 代碼如下:
package huawei
import (
"fmt"
"time"
)
/*
【排列組合問題：n個(gè)數(shù)中取m個(gè)】
*/
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))
//結(jié)果是否正確
rightCount := mathZuhe(n, m)
if rightCount == len(result) {
fmt.Println("結(jié)果正確")
} else {
fmt.Println("結(jié)果錯(cuò)誤，正確結(jié)果是：", rightCount)
}
}
//組合算法(從nums中取出m個(gè)數(shù))
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{}
}
//保存最終結(jié)果的數(shù)組，總數(shù)直接通過數(shù)學(xué)公式計(jì)算
result := make([][]int, 0, mathZuhe(n, m))
//保存每一個(gè)組合的索引的數(shù)組，1表示選中，0表示未選中
indexs := make([]int, n)
for i := 0; i n; i++ {
if i m {
indexs[i] = 1
} else {
indexs[i] = 0
}
}
//第一個(gè)結(jié)果
result = addTo(result, indexs)
for {
find := false
//每次循環(huán)將第一次出現(xiàn)的 1 0 改為 0 1，同時(shí)將左側(cè)的1移動(dòng)到最左側(cè)
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
}
}
//本次循環(huán)沒有找到 1 0 ，說明已經(jīng)取到了最后一種情況
if !find {
break
}
}
return result
}
//將ele復(fù)制后添加到arr中，返回新的數(shù)組
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) {
//計(jì)算有幾個(gè)1
sum := 0
for i := 0; i len(leftNums); i++ {
if leftNums[i] == 1 {
sum++
}
}
//將前sum個(gè)改為1，之后的改為0
for i := 0; i len(leftNums); i++ {
if i sum {
leftNums[i] = 1
} else {
leftNums[i] = 0
}
}
}
//根據(jù)索引號(hào)數(shù)組得到元素?cái)?shù)組
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個(gè)元素中取m個(gè)一共有多少種取法可直接通過數(shù)學(xué)公式計(jì)算得出，即：
復(fù)制代碼 代碼如下:
//數(shù)學(xué)方法計(jì)算排列數(shù)(從n中取m個(gè)數(shù))
func mathPailie(n int, m int) int {
return jieCheng(n) / jieCheng(n-m)
}
//數(shù)學(xué)方法計(jì)算組合數(shù)(從n中取m個(gè)數(shù))
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
}
通過此公式可以簡(jiǎn)單的驗(yàn)證一下上述程序的結(jié)果是否正確。
（二）排列問題
從n個(gè)數(shù)中取出m個(gè)進(jìn)行排列，其實(shí)就是組合算法之后，對(duì)選中的m個(gè)數(shù)進(jìn)行全排列。而全排列的問題在之前的文章中已經(jīng)討論過了。
代碼實(shí)現(xiàn)：
復(fù)制代碼 代碼如下:
func pailieResult(nums []int, m int) [][]int {
//組合結(jié)果
zuhe := zuheResult(nums, m)
//保存最終排列結(jié)果
result := make([][]int, 0)
//遍歷組合結(jié)果，對(duì)每一項(xiàng)進(jìn)行全排列
for _, v := range zuhe {
p := quanPailie(v)
result = append(result, p...)
}
return result
}
//n個(gè)數(shù)全排列
//如輸入[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.")
}
//如果只有一個(gè)數(shù)，則直接返回
if COUNT == 1 {
return [][]int{nums}
}
//否則，將最后一個(gè)數(shù)插入到前面的排列數(shù)中的所有位置
return insertItem(quanPailie(nums[:COUNT-1]), nums[COUNT-1])
}
func insertItem(res [][]int, insertNum int) [][]int {
//保存結(jié)果的slice
result := make([][]int, len(res)*(len(res[0])+1))
index := 0
for _, v := range res {
for i := 0; i len(v); i++ {
//在v的每一個(gè)元素前面插入新元素
result[index] = insertToSlice(v, i, insertNum)
index++
}
//在v最后面插入新元素
result[index] = append(v, insertNum)
index++
}
return result
}
//將元素value插入到數(shù)組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
}
希望本文所述對(duì)大家Go語言程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:- Golang排列組合算法問題之全排列實(shí)現(xiàn)方法
- Go語言對(duì)字符串進(jìn)行SHA1哈希運(yùn)算的方法
- GO語言運(yùn)行環(huán)境下載、安裝、配置圖文教程
- go語言文件正則表達(dá)式搜索功能示例
- Go語言正則表達(dá)式用法實(shí)例小結(jié)【查找、匹配、替換等】
- Go語言中三種不同md5計(jì)算方式的性能比較
- Go語言中反射的正確使用
- PHP與Go語言之間的通信詳解
- 深入理解GO語言的面向?qū)ο?/li>
- 利用Go語言實(shí)現(xiàn)簡(jiǎn)單Ping過程的方法
- Go語言如何并發(fā)超時(shí)處理詳解
