快捷導(dǎo)航

go語言實現(xiàn)全排列的示例代碼

更新時間：2023年03月07日 10:32:12 作者：大熊的飼養(yǎng)員

本文主要介紹了go語言實現(xiàn)全排列的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

思路：

首先畫出全排列的樹形結(jié)構(gòu)，以123為例，一開始排列為空列表，第一個位置有三種可能，分別是1、2、3，畫出三個分支；
由于第一個位置已經(jīng)被占用，那么第二個位置可選擇的就只有兩個，所以又可以展開兩個分支，如：1下的1,2和1,3；
選出兩個數(shù)字之后，最后就只剩下一個數(shù)字了，所以最后一個位置上的數(shù)就是唯一確定的了。之后這個樹的所有葉子結(jié)點就是全排列的結(jié)果。

回溯過程：

先選擇1，之后按順序選擇2，最后沒有可選數(shù)字就得到了1,2,3；為了得到所有的排列，這時候就要進行回溯。
最后一步選擇的是3那么回退的時候就要撤回3，回到1,2結(jié)點
由于1,2階段3已經(jīng)被選擇過了，所以繼續(xù)撤銷2，回退到1結(jié)點，這個階段本可以選擇2或者3，但是2已經(jīng)選擇過了，所以下一步就要選擇3，得到1,3結(jié)點，之后再進行剛才的選擇回退操作

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

將已經(jīng)選擇的數(shù)放進一個列表里temp，這個其實就是樹的路徑，因為要不斷地添加刪除所以這個應(yīng)該是個棧。在設(shè)置一個布爾數(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ù)組（要對空列表進行初始化）
?? ?if nlen==0{
?? ??? ?return result
?? ?}
?? ?//創(chuàng)建中間變量，存放臨時結(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)臨時temp長度和所給的數(shù)字長度相等時(也就是遞歸到了第幾層)，將該temp加入結(jié)果
?? ?if depth == nlen {
?? ??? ?//由于go語言的特性如果不特別說明創(chuàng)建的切片本質(zhì)上都是指向同一個內(nèi)存空間
?? ??? ?//如果想要循環(huán)賦值的切片與原來切片不相關(guān)，需要另外開辟空間，這里用到copy函數(shù)，開辟獨立空間
?? ??? ?current := make([]int, depth)
?? ??? ?copy(current, temp)
?? ??? ?*result = append(*result, current)
?? ?}
?? ?//遍歷數(shù)組中的數(shù)字，進行排列組合
?? ?for i := 0; i < nlen; i++ {
?? ??? ?//減枝，當(dāng)該位置數(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
?? ?}
}

到此這篇關(guān)于go語言實現(xiàn)全排列的示例代碼的文章就介紹到這了,更多相關(guān)go語言全排列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: