溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如何用Go語言生成一個排列，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
目前，生成一個序列的排列常用的有以下幾種算法：
暴力法（Brute Force）插入法（Insert）字典法（Lexicographic）SJT算法（Steinhaus-Johnson-Trotter）堆算法（Heap）
下面依次介紹算法的內容，實現和優缺點。
在介紹這些算法之前，我們先做一些示例和代碼上的約定：
我的代碼實現是使用 Go 語言，且僅實現了求int切片的所有排列，其它類型自行擴展也不難。除非特殊說明，我假定輸入的int中無重復元素，有重復元素可自行去重，其中有個別算法可處理重復元素的問題。
完整代碼放在Github上。
暴力法是很直接的一種分治法：先生成 n-1 個元素的排列，加上第 n 個元素即可得到 n 個元素的排列。算法步驟如下：
將第 n 個元素依次交換到最后一個位置上遞歸生成前 n-1 個元素的排列加上最后一個元素即為 n 個元素的排列
算法實現也很簡單。這里引入兩個輔助函數，拷貝和反轉切片，后面代碼都會用到：
func copySlice(nums []int) []int {
n := make([]int, len(nums), len(nums))
copy(n, nums)
return n
}
// 反轉切片nums的[i, j]范圍
func reverseSlice(nums []int, i, j int) {
for i < j {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}
算法代碼如下：
func BruteForce(nums []int, n int, ans *[][]int) {
if n == 1 {
*ans = append(*ans, copySlice(nums))
return
}
n := len(nums)
for i := 0; i < n; i++ {
nums[i], nums[n-1] = nums[n-1], nums[i]
BruteForce(nums, n-1, ans)
nums[i], nums[n-1] = nums[n-1], nums[i]
}
}
作為一個接口，需要做到盡可能簡潔，第二個參數初始值就是前一個參數切片的長度。優化接口：
func bruteForceHelper(nums []int, n int, ans *[][]int) {
// 生成排列邏輯
...
}
func BruteForce(nums []int) [][]int{
ans := make([][]int, 0, len(nums))
bruteForceHelper(nums, len(nums), &ans)
return ans
}
優點：邏輯簡單直接，易于理解。
缺點：返回的排列數肯定是n!，性能的關鍵在于系數的大小。由于暴力法的每次循環都需要交換兩個位置上的元素，遞歸結束后又需要再交換回來，在n較大的情況下，性能較差。
插入法顧名思義就是將元素插入到一個序列中所有可能的位置生成新的序列。從 1 個元素開始。例如要生成{1,2,3}的排列：
先從序列 1 開始，插入元素 2，有兩個位置可以插入，生成兩個序列 12 和 21將 3 插入這兩個序列的所有可能位置，生成最終的 6 個序列
1
12 21
123 132 312 213 231 321
實現如下：
func insertHelper(nums []int, n int) [][]int {
if n == 1 {
return [][]int{[]int{nums[0]}}
}
var ans [][]int
for _, subPermutation := range insertHelper(nums, n-1) {
// 依次在位置0-n上插入
for i := 0; i <= len(subPermutation); i++ {
permutation := make([]int, n, n)
copy(permutation[:i], subPermutation[:i])
permutation[i] = nums[n-1]
copy(permutation[i+1:], subPermutation[i:])
ans = append(ans, permutation)
}
}
return ans
}
func Insert(nums []int) [][]int {
return insertHelper(nums, len(nums))
}
優點：同樣是簡單直接，易于理解。
缺點：由于算法中有不少的數據移動，性能與暴力法相比降低了16%。
該算法有個前提是序列必須是有升序排列的，當然也可以微調對其它序列使用。它通過修改當前序列得到下一個序列。我們為每個序列定義一個權重，類比序列組成的數字的大小，序列升序排列時“權重”最小，降序排列時“權重”最大。下面是 1234 的排列按**“權重”由小到大：
1234
1243
1324
1342
1423
1432
2134
...
我們觀察到一開始最高位都是 1，稍微調整一下后面三個元素的順序就可以使得整個“權重”增加，類比整數。當后面三個元素已經逆序時，下一個序列最高位就必須是 2 了，因為僅調整后三個元素已經無法使“權重”增加了。算法的核心步驟為：
對于當前的序列，找到索引i滿足其后的元素完全逆序。這時索引i處的元素需要變為后面元素中大于該元素的最小值。然后剩余元素升序排列，即為當前序列的下一個序列。
該算法用于 C++ 標準庫中next_permutation算法的實現，見GNU C++ std::next_permutation。
func NextPermutation(nums []int) bool {
if len(nums) <= 1 {
return false
}
i := len(nums) - 1
for i > 0 && nums[i-1] > nums[i] {
i--
}
// 全都逆序了，達到最大值
if i == 0 {
reverse(nums, 0, len(nums)-1)
return false
}
// 找到比索引i處元素大的元素
j := len(nums) - 1
for nums[j] <= nums[i-1] {
j--
}
nums[i-1], nums[j] = nums[j], nums[i-1]
// 將后面的元素反轉
reverse(nums, i, len(nums)-1)
return true
}
func lexicographicHelper(nums []int) [][]int {
ans := make([][]int, 0, len(nums))
ans = append(ans, copySlice(nums))
for NextPermutation(nums) {
ans = append(ans, copySlice(nums))
}
return ans
}
func Lexicographic(nums []int) [][]int {
return lexicographicHelper(nums)
}
NextPermutation函數即可用于解決前文 LeetCode 算法題。其返回false表示已經到達最后一個序列了。
優點：NextPermutation可以單獨使用，性能也不錯。
缺點：稍微有點難理解。
SJT 算法在前一個排列的基礎上通過僅交換相鄰的兩個元素來生成下一個排列。例如，按照下面順序生成 123 的排列:
123(交換23) ->
132(交換13) ->
312(交換12) ->
321(交換32) ->
231(交換31) ->
213
一個簡單的方案是通過 n-1 個元素的排列生成 n 個元素的排列。例如我們現在用 2 個元素的排列生成 3 個元素的排列。
2 個元素的排列只有 2 個：1 2 和 2 1。
通過在 2 個元素的排列中所有不同的位置插入 3，我們就能得到 3 個元素的排列。
在 1 2 的不同位置插入 3 得到：1 23，132 和31 2。在 2 1 的不同位置插入 3 得到：2 13，231 和32 1。
上面是插入法的邏輯，但是插入法由于有大量的數據移動導致性能較差。SJT 算法不要求生成所有 n-1 個元素的排列。它記錄排列中每個元素的方向。算法步驟如下：
查找序列中可移動的最大元素。一個元素可移動意味著它的值大于它指向的相鄰元素。交換該元素與它指向的相鄰元素。修改所有值大于該元素的元素的方向。重復以上步驟直到沒有可移動的元素。
假設我們需要生成序列 1 2 3 4 的所有排列。首先初始化所有元素的方向為從右到左。第一個排列即為初始序列：
<1 <2 <3 <4
所有可移動的元素為 2，3 和 4。最大的為 4。我們交換 3 和 4。由于此時 4 是最大元素，不用改變方向。得到下一個排列：
<1 <2 <4 <3
4 還是最大的可移動元素，交換 2 和 4，不用改變方向。得到下一個排列：
<1 <4 <2 <3
4 還是最大的可移動元素，交換 1 和 4，不用改變方向。得到下一個排列：
<4 <1 <2 <3
當前 4 已經無法移動了，3 成為最大的可移動元素，交換 2 和 3。注意，元素 4 比 3 大，所以要改變元素 4 的方向。得到下一個排列：
>4 <1 <3 <2
這時，元素 4 又成為了最大的可移動元素，交換 4 和 1。注意，此時元素 4 方向已經變了。得到下一個排列：
<1 >4 <3 <2
交換 4 和 3，得到下一個排列：
<1 <3 >4 <2
交換 4 和 2：
<1 <3 <2 >4
這時元素 3 為可移動的最大元素，交換 1 和 3，改變元素 4 的方向：
<3 <1 <2 <4
繼續這個過程，最后得到的排列為（強烈建議自己試試）：
<2 <1 >3 >4
已經沒有可移動的元素了，算法結束。
func getLargestMovableIndex(nums []int, dir []bool) int {
maxI := -1
l := len(nums)
for i, num := range nums {
if dir[i] {
if i > 0 && num > nums[i-1] {
if maxI == -1 || num > nums[maxI] {
maxI = i
}
}
} else {
if i < l-1 && num > nums[i+1] {
if maxI == -1 || num > nums[maxI] {
maxI = i
}
}
}
}
return maxI
}
func sjtHelper(nums []int, ans *[][]int) {
l := len(nums)
// true 表示方向為從右向左
// false 表示方向為從左向右
dir := make([]bool, l, l)
for i := range dir {
dir[i] = true
}
maxI := getLargestMovableIndex(nums, dir)
for maxI >= 0 {
maxNum := nums[maxI]
// 交換最大可移動元素與它指向的元素
if dir[maxI] {
nums[maxI], nums[maxI-1] = nums[maxI-1], nums[maxI]
dir[maxI], dir[maxI-1] = dir[maxI-1], dir[maxI]
} else {
nums[maxI], nums[maxI+1] = nums[maxI+1], nums[maxI]
dir[maxI], dir[maxI+1] = dir[maxI+1], dir[maxI]
}
*ans = append(*ans, copySlice(nums))
// 改變所有大于當前移動元素的元素的方向
for i, num := range nums {
if num > maxNum {
dir[i] = !dir[i]
}
}
maxI = getLargestMovableIndex(nums, dir)
}
}
func Sjt(nums []int) [][]int {
ans := make([][]int, 0, len(nums))
ans = append(ans, copySlice(nums))
sjtHelper(nums, &ans)
return ans
}
優點：作為一種算法思維可以學習借鑒。
缺點：性能不理想。
Heap算法優雅、高效。它是從暴力法演化而來的，我們前面提到暴力法性能差主要是由于多次交換，堆算法就是通過減少交換提升效率。
算法步驟如下：
如果元素個數為奇數，交換第一個和最后一個元素。如果元素個數為偶數，依次交換第 i 個和最后一個元素。
Wikipedia上有詳細的證明，有興趣可以看看。
func heapHelper(nums []int, n int, ans *[][]int) {
if n == 1 {
*ans = append(*ans, copySlice(nums))
return
}
for i := 0; i < n-1; i++ {
heapHelper(nums, n-1, ans)
if n&1 == 0 {
// 如果是偶數，交換第i個與最后一個元素
nums[i], nums[n-1] = nums[n-1], nums[i]
} else {
// 如果是奇數，交換第一個與最后一個元素
nums[0], nums[n-1] = nums[n-1], nums[0]
}
}
heapHelper(nums, n-1, ans)
}
// Heap 使用堆算法生成排列
func Heap(nums []int) [][]int {
ans := make([][]int, 0, len(nums))
heapHelper(nums, len(nums), &ans)
return ans
}
Heap 算法非常難理解，而且很容易寫錯，我現在純粹是背下來了
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
