go語言如何實現全排列

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

思路：

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

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

• 選出兩個數字之后，最后就只剩下一個數字了，所以最后一個位置上的數就是唯一確定的了。 之后這個樹的所有葉子結點就是全排列的結果。

回溯過程：

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

• 最后一步選擇的是3那么回退的時候就要撤回3，回到1,2結點

• 由于1,2階段3已經被選擇過了，所以繼續撤銷2，回退到1結點，這個階段本可以選擇2或者3，但是2已經選擇過了，所以下一步就要選擇3，得到1,3結點，之后再進行剛才的選擇回退操作

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

將已經選擇的數放進一個列表里temp，這個其實就是樹的路徑，因為要不斷地添加刪除所以這個應該是個棧。在設置一個布爾數組used表示當前已經考慮的數字是否在之前

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

代碼：

package main

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

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