如何用Go語(yǔ)言生成一個(gè)排列，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)建站基于分布式IDC數(shù)據(jù)中心構(gòu)建的平臺(tái)為眾多戶提供成都棕樹(shù)機(jī)房 四川大帶寬租用 成都機(jī)柜租用 成都服務(wù)器租用。

算法

目前，生成一個(gè)序列的排列常用的有以下幾種算法：

暴力法（Brute Force）插入法（Insert）字典法（Lexicographic）SJT算法（Steinhaus-Johnson-Trotter）堆算法（Heap）

下面依次介紹算法的內(nèi)容，實(shí)現(xiàn)和優(yōu)缺點(diǎn)。

在介紹這些算法之前，我們先做一些示例和代碼上的約定：

我的代碼實(shí)現(xiàn)是使用 Go 語(yǔ)言，且僅實(shí)現(xiàn)了求int切片的所有排列，其它類型自行擴(kuò)展也不難。除非特殊說(shuō)明，我假定輸入的int中無(wú)重復(fù)元素，有重復(fù)元素可自行去重，其中有個(gè)別算法可處理重復(fù)元素的問(wèn)題。

完整代碼放在Github上。

暴力法

描述

暴力法是很直接的一種分治法：先生成 n-1 個(gè)元素的排列，加上第 n 個(gè)元素即可得到 n 個(gè)元素的排列。算法步驟如下：

將第 n 個(gè)元素依次交換到最后一個(gè)位置上遞歸生成前 n-1 個(gè)元素的排列加上最后一個(gè)元素即為 n 個(gè)元素的排列

實(shí)現(xiàn)

算法實(shí)現(xiàn)也很簡(jiǎn)單。這里引入兩個(gè)輔助函數(shù)，拷貝和反轉(zhuǎn)切片，后面代碼都會(huì)用到：

func copySlice(nums []int) []int {

n := make([]int, len(nums), len(nums))

copy(n, nums)

return n

}

// 反轉(zhuǎ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]

}

}

作為一個(gè)接口，需要做到盡可能簡(jiǎn)潔，第二個(gè)參數(shù)初始值就是前一個(gè)參數(shù)切片的長(zhǎng)度。優(yōu)化接口：

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

}

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：邏輯簡(jiǎn)單直接，易于理解。

缺點(diǎn)：返回的排列數(shù)肯定是n!，性能的關(guān)鍵在于系數(shù)的大小。由于暴力法的每次循環(huán)都需要交換兩個(gè)位置上的元素，遞歸結(jié)束后又需要再交換回來(lái)，在n較大的情況下，性能較差。

插入法

描述

插入法顧名思義就是將元素插入到一個(gè)序列中所有可能的位置生成新的序列。從 1 個(gè)元素開(kāi)始。例如要生成{1,2,3}的排列：

先從序列 1 開(kāi)始，插入元素 2，有兩個(gè)位置可以插入，生成兩個(gè)序列 12 和 21將 3 插入這兩個(gè)序列的所有可能位置，生成最終的 6 個(gè)序列

1

12 21

123 132 312 213 231 321

實(shí)現(xiàn)

實(shí)現(xiàn)如下：

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))

}

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：同樣是簡(jiǎn)單直接，易于理解。

缺點(diǎn)：由于算法中有不少的數(shù)據(jù)移動(dòng)，性能與暴力法相比降低了16%。

字典法

描述

該算法有個(gè)前提是序列必須是有升序排列的，當(dāng)然也可以微調(diào)對(duì)其它序列使用。它通過(guò)修改當(dāng)前序列得到下一個(gè)序列。我們?yōu)槊總€(gè)序列定義一個(gè)權(quán)重，類比序列組成的數(shù)字的大小，序列升序排列時(shí)“權(quán)重”最小，降序排列時(shí)“權(quán)重”最大。下面是 1234 的排列按**“權(quán)重”由小到大：

1234

1243

1324

1342

1423

1432

2134

...

我們觀察到一開(kāi)始最高位都是 1，稍微調(diào)整一下后面三個(gè)元素的順序就可以使得整個(gè)“權(quán)重”增加，類比整數(shù)。當(dāng)后面三個(gè)元素已經(jīng)逆序時(shí)，下一個(gè)序列最高位就必須是 2 了，因?yàn)閮H調(diào)整后三個(gè)元素已經(jīng)無(wú)法使“權(quán)重”增加了。算法的核心步驟為：

對(duì)于當(dāng)前的序列，找到索引i滿足其后的元素完全逆序。這時(shí)索引i處的元素需要變?yōu)楹竺嬖刂写笥谠撛氐淖钚≈怠Ｈ缓笫Ｓ嘣厣蚺帕?，即為?dāng)前序列的下一個(gè)序列。

該算法用于 C++ 標(biāo)準(zhǔn)庫(kù)中next_permutation算法的實(shí)現(xiàn)，見(jiàn)GNU C++ std::next_permutation。

實(shí)現(xiàn)

func NextPermutation(nums []int) bool {

if len(nums) <= 1 {

return false

}

i := len(nums) - 1

for i > 0 && nums[i-1] > nums[i] {

i--

}

// 全都逆序了，達(dá)到最大值

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]

// 將后面的元素反轉(zhuǎn)

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函數(shù)即可用于解決前文 LeetCode 算法題。其返回false表示已經(jīng)到達(dá)最后一個(gè)序列了。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：NextPermutation可以單獨(dú)使用，性能也不錯(cuò)。

缺點(diǎn)：稍微有點(diǎn)難理解。

SJT算法

描述

SJT 算法在前一個(gè)排列的基礎(chǔ)上通過(guò)僅交換相鄰的兩個(gè)元素來(lái)生成下一個(gè)排列。例如，按照下面順序生成 123 的排列:

123(交換23) ->

132(交換13) ->

312(交換12) ->

321(交換32) ->

231(交換31) ->

213

一個(gè)簡(jiǎn)單的方案是通過(guò) n-1 個(gè)元素的排列生成 n 個(gè)元素的排列。例如我們現(xiàn)在用 2 個(gè)元素的排列生成 3 個(gè)元素的排列。

2 個(gè)元素的排列只有 2 個(gè)：1 2 和 2 1。

通過(guò)在 2 個(gè)元素的排列中所有不同的位置插入 3，我們就能得到 3 個(gè)元素的排列。

在 1 2 的不同位置插入 3 得到：1 23，132 和31 2。在 2 1 的不同位置插入 3 得到：2 13，231 和32 1。

上面是插入法的邏輯，但是插入法由于有大量的數(shù)據(jù)移動(dòng)導(dǎo)致性能較差。SJT 算法不要求生成所有 n-1 個(gè)元素的排列。它記錄排列中每個(gè)元素的方向。算法步驟如下：

查找序列中可移動(dòng)的最大元素。一個(gè)元素可移動(dòng)意味著它的值大于它指向的相鄰元素。交換該元素與它指向的相鄰元素。修改所有值大于該元素的元素的方向。重復(fù)以上步驟直到?jīng)]有可移動(dòng)的元素。

假設(shè)我們需要生成序列 1 2 3 4 的所有排列。首先初始化所有元素的方向?yàn)閺挠业阶蟆５谝粋€(gè)排列即為初始序列：

<1 <2 <3 <4

所有可移動(dòng)的元素為 2，3 和 4。最大的為 4。我們交換 3 和 4。由于此時(shí) 4 是最大元素，不用改變方向。得到下一個(gè)排列：

<1 <2 <4 <3

4 還是最大的可移動(dòng)元素，交換 2 和 4，不用改變方向。得到下一個(gè)排列：

<1 <4 <2 <3

4 還是最大的可移動(dòng)元素，交換 1 和 4，不用改變方向。得到下一個(gè)排列：

<4 <1 <2 <3

當(dāng)前 4 已經(jīng)無(wú)法移動(dòng)了，3 成為最大的可移動(dòng)元素，交換 2 和 3。注意，元素 4 比 3 大，所以要改變?cè)?4 的方向。得到下一個(gè)排列：

>4 <1 <3 <2

這時(shí)，元素 4 又成為了最大的可移動(dòng)元素，交換 4 和 1。注意，此時(shí)元素 4 方向已經(jīng)變了。得到下一個(gè)排列：

<1 >4 <3 <2

交換 4 和 3，得到下一個(gè)排列：

<1 <3 >4 <2

交換 4 和 2：

<1 <3 <2 >4

這時(shí)元素 3 為可移動(dòng)的最大元素，交換 1 和 3，改變?cè)?4 的方向：

<3 <1 <2 <4

繼續(xù)這個(gè)過(guò)程，最后得到的排列為（強(qiáng)烈建議自己試試）：

<2 <1 >3 >4

已經(jīng)沒(méi)有可移動(dòng)的元素了，算法結(jié)束。

實(shí)現(xiàn)

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 表示方向?yàn)閺挠蚁蜃?/p>

// false 表示方向?yàn)閺淖笙蛴?/p>

dir := make([]bool, l, l)

for i := range dir {

dir[i] = true

}

maxI := getLargestMovableIndex(nums, dir)

for maxI >= 0 {

maxNum := nums[maxI]

// 交換最大可移動(dòng)元素與它指向的元素

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))

// 改變所有大于當(dāng)前移動(dòng)元素的元素的方向

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

}

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：作為一種算法思維可以學(xué)習(xí)借鑒。

缺點(diǎn)：性能不理想。

Heap算法

描述

Heap算法優(yōu)雅、高效。它是從暴力法演化而來(lái)的，我們前面提到暴力法性能差主要是由于多次交換，堆算法就是通過(guò)減少交換提升效率。

算法步驟如下：

如果元素個(gè)數(shù)為奇數(shù)，交換第一個(gè)和最后一個(gè)元素。如果元素個(gè)數(shù)為偶數(shù)，依次交換第 i 個(gè)和最后一個(gè)元素。

Wikipedia上有詳細(xì)的證明，有興趣可以看看。

實(shí)現(xiàn)

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 {

// 如果是偶數(shù)，交換第i個(gè)與最后一個(gè)元素

nums[i], nums[n-1] = nums[n-1], nums[i]

} else {

// 如果是奇數(shù)，交換第一個(gè)與最后一個(gè)元素

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 算法非常難理解，而且很容易寫(xiě)錯(cuò)，我現(xiàn)在純粹是背下來(lái)了

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。

本文名稱：如何用Go語(yǔ)言生成一個(gè)排列
網(wǎng)址分享：http://chinadenli.net/article22/gidpjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、面包屑導(dǎo)航、搜索引擎優(yōu)化、電子商務(wù)、ChatGPT、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)