脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Golang - Go语言实现的排列组合问题实例(n个数中取m个)

Go语言实现的排列组合问题实例(n个数中取m个)

2020-05-05 13:56books1958 Golang

这篇文章主要介绍了Go语言实现的排列组合问题,结合实例形式分析了Go语言实现排列组合数学运算的原理与具体操作技巧,需要的朋友可以参考下

本文实例讲述了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语言程序设计有所帮助。

延伸 · 阅读

精彩推荐
  • Golanggolang 通过ssh代理连接mysql的操作

    golang 通过ssh代理连接mysql的操作

    这篇文章主要介绍了golang 通过ssh代理连接mysql的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...

    a165861639710342021-03-08
  • GolangGolang中Bit数组的实现方式

    Golang中Bit数组的实现方式

    这篇文章主要介绍了Golang中Bit数组的实现方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...

    天易独尊11682021-06-09
  • Golanggo语言制作端口扫描器

    go语言制作端口扫描器

    本文给大家分享的是使用go语言编写的TCP端口扫描器,可以选择IP范围,扫描的端口,以及多线程,有需要的小伙伴可以参考下。 ...

    脚本之家3642020-04-25
  • Golanggolang的httpserver优雅重启方法详解

    golang的httpserver优雅重启方法详解

    这篇文章主要给大家介绍了关于golang的httpserver优雅重启的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...

    helight2992020-05-14
  • GolangGolang通脉之数据类型详情

    Golang通脉之数据类型详情

    这篇文章主要介绍了Golang通脉之数据类型,在编程语言中标识符就是定义的具有某种意义的词,比如变量名、常量名、函数名等等,Go语言中标识符允许由...

    4272021-11-24
  • Golanggo日志系统logrus显示文件和行号的操作

    go日志系统logrus显示文件和行号的操作

    这篇文章主要介绍了go日志系统logrus显示文件和行号的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...

    SmallQinYan12302021-02-02
  • Golanggolang如何使用struct的tag属性的详细介绍

    golang如何使用struct的tag属性的详细介绍

    这篇文章主要介绍了golang如何使用struct的tag属性的详细介绍,从例子说起,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看...

    Go语言中文网11352020-05-21
  • Golanggolang json.Marshal 特殊html字符被转义的解决方法

    golang json.Marshal 特殊html字符被转义的解决方法

    今天小编就为大家分享一篇golang json.Marshal 特殊html字符被转义的解决方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 ...

    李浩的life12792020-05-27