Go語言實現的排列組合問題例項(n個數中取m個)

NO IMAGE

本文例項講述了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排列組合演算法問題之全排列實現方法Go語言對字串進行SHA1雜湊運算的方法GO語言執行環境下載、安裝、配置圖文教程go語言檔案正規表示式搜尋功能示例Go語言正規表示式用法例項小結【查詢、匹配、替換等】Go語言中三種不同md5計算方式的效能比較Go語言中反射的正確使用PHP與Go語言之間的通訊詳解深入理解GO語言的物件導向利用Go語言實現簡單Ping過程的方法Go語言如何併發超時處理詳解