Go語(yǔ)言實(shí)現(xiàn)的排列組合問(wèn)題實(shí)例(n個(gè)數(shù)中取m個(gè))

package huawei
import (
    "fmt"
    "time"
)
/*
【排列組合問(wèn)題：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ù)直接通過(guò)數(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)沒(méi)有找到 1 0 ，說(shuō)明已經(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
}

//數(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
}

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
}