Golang排列组合算法问题之全排列实现方法

ZGCdemo 2017-01-30

本文实例讲述了Golang排列组合算法问题之全排列实现方法。分享给大家供大家参考,具体如下:

【排列组合问题】

一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号。

输入:

包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格。

输出:

输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行。

样例输入:

1 2 3

样例输出:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

代码实现:

代码如下:

package huawei

import (

    "fmt"

    "sort"

    "strings"

)

func Test7Base() {

    in := "5 2 3"

    result := outOrder(strings.Fields(in))

    dictSort(result)

    s := format(result)

    fmt.Println(s)

}

//输入trainsNums,返回全部排列

//如输入[1 2 3],则返回[123 132 213 231 312 321]

func outOrder(trainsNums []string) []string {

    COUNT := len(trainsNums)

    //检查

    if COUNT == 0 || COUNT > 10 {

        panic("Illegal argument. trainsNums size must between 1 and 9.")

    }

    //如果只有一个数,则直接返回

    if COUNT == 1 {

        return []string{trainsNums[0]}

    }

    //否则,将最后一个数插入到前面的排列数中的所有位置(递归)

    return insert(outOrder(trainsNums[:COUNT-1]), trainsNums[COUNT-1])

}

func insert(res []string, insertNum string) []string {

    //保存结果的slice

    result := make([]string, len(res)*(len(res[0])+1))

    index := 0

    for _, v := range res {

        for i := 0; i < len(v); i++ {

            //在v的每一个元素前面插入

            result[index] = v[:i] + insertNum + v[i:]

            index++

        }

        //在v最后面插入

        result[index] = v + insertNum

        index++

    }

    return result

}

//按字典顺序排序

func dictSort(res []string) {

    sort.Strings(res)

}

//按指定格式输出

func format(res []string) string {

    strs := make([]string, len(res))

    for i := 0; i < len(res); i++ {

        strs[i] = addWhiteSpace(res[i])

    }

    return strings.Join(strs, "\n")

}

//添加空格

func addWhiteSpace(s string) string {

    var retVal string

    for i := 0; i < len(s); i++ {

        retVal += string(s[i])

        if i != len(s)-1 {

            retVal += " "

        }

    }

    return retVal

}

希望本文所述对大家Go语言程序设计有所帮助。

相关推荐