快捷導(dǎo)航

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

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

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

思路：

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

回溯過(guò)程：

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

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

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

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

代碼：

package main

func main() {
}
func permute(nums []int) [][]int ?{
?? ?//保存輸入數(shù)組的長(zhǎng)度
?? ?nlen := len(nums)
?? ?//初始化，用來(lái)存放結(jié)果
?? ?var result [][]int
?? ?//如果傳入長(zhǎng)度為0，那就直接返回空數(shù)組（要對(duì)空列表進(jìn)行初始化）
?? ?if nlen==0{
?? ??? ?return result
?? ?}
?? ?//創(chuàng)建中間變量，存放臨時(shí)結(jié)果
?? ?var temp []int
?? ?//創(chuàng)建bool值，判斷該位置數(shù)字是否用過(guò)
?? ?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長(zhǎng)度和所給的數(shù)字長(zhǎng)度相等時(shí)(也就是遞歸到了第幾層)，將該temp加入結(jié)果
?? ?if depth == nlen {
?? ??? ?//由于go語(yǔ)言的特性如果不特別說(shuō)明創(chuàng)建的切片本質(zhì)上都是指向同一個(gè)內(nèi)存空間
?? ??? ?//如果想要循環(huán)賦值的切片與原來(lái)切片不相關(guān)，需要另外開(kāi)辟空間，這里用到copy函數(shù)，開(kāi)辟獨(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ù)字使用過(guò)時(shí)則跳過(guò)
?? ??? ?if used[i] {
?? ??? ??? ?continue
?? ??? ?}
?? ??? ?//沒(méi)有使用過(guò)就添加數(shù)字
?? ??? ?temp = append(temp, nums[i])
?? ??? ?//將該位置數(shù)字設(shè)置為訪問(wèn)過(guò)的狀態(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語(yǔ)言實(shí)現(xiàn)全排列的示例代碼的文章就介紹到這了,更多相關(guān)go語(yǔ)言全排列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: