Golang排列組合算法問題之全排列實(shí)現(xiàn)方法

更新時(shí)間：2017年01月30日 14:28:02 作者：books1958

這篇文章主要介紹了Golang排列組合算法問題之全排列實(shí)現(xiàn)方法,涉及Go語(yǔ)言針對(duì)字符串的遍歷及排列組合相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Golang排列組合算法問題之全排列實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

【排列組合問題】

一共N輛火車（0<N<10），每輛火車以數(shù)字1-9編號(hào)，要求以字典序排序輸出火車出站的序列號(hào)。

輸入:

包括N個(gè)正整數(shù)（0<N<10），范圍為1到9，數(shù)字之間用空格分割，字符串首位不包含空格。

輸出:

輸出以字典序排序的火車出站序列號(hào)，每個(gè)編號(hào)以空格隔開，每個(gè)輸出序列換行。

樣例輸入:

1 2 3

樣例輸出:

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

代碼實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

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.")

    }

    //如果只有一個(gè)數(shù)，則直接返回

    if COUNT == 1 {

        return []string{trainsNums[0]}

    }

    //否則，將最后一個(gè)數(shù)插入到前面的排列數(shù)中的所有位置（遞歸）

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

}

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

    //保存結(jié)果的slice

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

    index := 0

    for _, v := range res {

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

            //在v的每一個(gè)元素前面插入

            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

}