Go でヒープのアルゴリズムはどのようにしてすべての順列を生成できるのでしょうか?

Go でのすべての置換の生成

はじめに

次のリストの可能なすべての置換の生成要素はプログラミングにおける一般的な問題です。この記事では、すべての順列を生成するための最も簡単なアプローチの 1 つであるヒープのアルゴリズムについて説明します。生成された順列は辞書順に並べ替えられません。

ヒープのアルゴリズム

ヒープのアルゴリズムは、交換する要素のペアを選択することによって各順列を生成します。それは、配列に要素が 1 つだけある基本的なケースから始まります。大きな配列の場合は、要素を反復処理し、ペアを交換して新しい順列を再帰的に生成します。

Go 実装

以下は、ヒープ アルゴリズムの Go 実装です。

func permutations(arr []int) [][]int {
    res := [][]int{}
    helper := func(arr []int, n int) {
        if n == 1 {
            tmp := make([]int, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < n; i++ {
                helper(arr, n-1)
                if n%2 == 1 {
                    tmp := arr[i]
                    arr[i] = arr[n-1]
                    arr[n-1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n-1]
                    arr[n-1] = tmp
                }
            }
        }
    }
    helper(arr, len(arr))
    return res
}

使用法例

順列関数の使用方法の例を次に示します。

arr := []int{1, 2, 3}
fmt.Println(permutations(arr))

出力

[[1 2 3] [2 1 3] [3 2 1] [2 3 1] [3 1 2] [1 3 2]]

追加メモ

• 順列は生成されますが、辞書順に並べ替えられません。
• 辞書順に並べ替える場合は、階乗数体系を使用して順列を生成することを検討してください。

以上がGo でヒープのアルゴリズムはどのようにしてすべての順列を生成できるのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。