go語言如何實(shí)現(xiàn)全排列

今天小編給大家分享一下go語言如何實(shí)現(xiàn)全排列的相關(guān)知識點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

思路：

• 首先畫出全排列的樹形結(jié)構(gòu)，以123為例，一開始排列為空列表，第一個(gè)位置有三種可能，分別是1、2、3，畫出三個(gè)分支；

• 由于第一個(gè)位置已經(jīng)被占用，那么第二個(gè)位置可選擇的就只有兩個(gè)，所以又可以展開兩個(gè)分支，如：1下的1,2和1,3；

• 選出兩個(gè)數(shù)字之后，最后就只剩下一個(gè)數(shù)字了，所以最后一個(gè)位置上的數(shù)就是唯一確定的了。 之后這個(gè)樹的所有葉子結(jié)點(diǎn)就是全排列的結(jié)果。

回溯過程：

• 先選擇1，之后按順序選擇2，最后沒有可選數(shù)字就得到了1,2,3；為了得到所有的排列，這時(shí)候就要進(jìn)行回溯。

• 最后一步選擇的是3那么回退的時(shí)候就要撤回3，回到1,2結(jié)點(diǎn)

• 由于1,2階段3已經(jīng)被選擇過了，所以繼續(xù)撤銷2，回退到1結(jié)點(diǎn)，這個(gè)階段本可以選擇2或者3，但是2已經(jīng)選擇過了，所以下一步就要選擇3，得到1,3結(jié)點(diǎn)，之后再進(jìn)行剛才的選擇回退操作

這個(gè)樹除了葉子結(jié)點(diǎn)以外，其他結(jié)點(diǎn)做的事情都是一樣的，也就是在已經(jīng)選了數(shù) 的前提下需要在剩下還沒有選擇的數(shù)里，按照順序選擇一棵樹，所以這就是一個(gè)遞歸。那么遞歸終止的條件就是數(shù)字的個(gè)數(shù)已經(jīng)選完了。所以我們需要一個(gè)變量來記錄已經(jīng)選了多少個(gè)數(shù)字，其實(shí)這個(gè)變量等價(jià)遞歸到了第幾層depth，當(dāng)遍歷的層數(shù)和輸入數(shù)組的個(gè)數(shù)相等的時(shí)候，所有的元素就都被考慮完了，就可以退出遞歸。

將已經(jīng)選擇的數(shù)放進(jìn)一個(gè)列表里temp，這個(gè)其實(shí)就是樹的路徑，因?yàn)橐粩嗟靥砑觿h除所以這個(gè)應(yīng)該是個(gè)棧。在設(shè)置一個(gè)布爾數(shù)組used表示當(dāng)前已經(jīng)考慮的數(shù)字是否在之前

已經(jīng)選擇過，也就是判斷是否在path變量里，初始化都為FALSE，表示都未被選擇。

代碼：

package main

func main() {
}
func permute(nums []int) [][]int  {
    //保存輸入數(shù)組的長度
    nlen := len(nums)
    //初始化，用來存放結(jié)果
    var result [][]int
    //如果傳入長度為0，那就直接返回空數(shù)組（要對空列表進(jìn)行初始化）
    if nlen==0{
        return result
    }
    //創(chuàng)建中間變量，存放臨時(shí)結(jié)果
    var temp []int
    //創(chuàng)建bool值，判斷該位置數(shù)字是否用過
    used := make([]bool, nlen)
    //回溯函數(shù)
    BackTrack(used, temp, nums, &result,nlen,0)
    return result
}
func BackTrack(used []bool, temp []int, nums []int, result *[][]int,nlen int,depth int) {
    //判斷回溯函數(shù)結(jié)束條件
    //當(dāng)臨時(shí)temp長度和所給的數(shù)字長度相等時(shí)(也就是遞歸到了第幾層)，將該temp加入結(jié)果
    if depth == nlen {
        //由于go語言的特性如果不特別說明創(chuàng)建的切片本質(zhì)上都是指向同一個(gè)內(nèi)存空間
        //如果想要循環(huán)賦值的切片與原來切片不相關(guān)，需要另外開辟空間，這里用到copy函數(shù)，開辟獨(dú)立空間
        current := make([]int, depth)
        copy(current, temp)
        *result = append(*result, current)
    }
    //遍歷數(shù)組中的數(shù)字，進(jìn)行排列組合
    for i := 0; i < nlen; i++ {
        //減枝，當(dāng)該位置數(shù)字使用過時(shí)則跳過
        if used[i] {
            continue
        }
        //沒有使用過就添加數(shù)字
        temp = append(temp, nums[i])
        //將該位置數(shù)字設(shè)置為訪問過的狀態(tài)
        used[i] = true
        //遞歸繼續(xù)搜索該支線
        BackTrack(used, temp, nums, result,nlen,depth+1)
        //回溯，恢復(fù)到之前的狀態(tài)
        temp = temp[:len(temp)-1]
        used[i] = false
    }
}

以上就是“go語言如何實(shí)現(xiàn)全排列”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注億速云行業(yè)資訊頻道。