Go でリストのすべての順列を効率的に生成するにはどうすればよいですか?-Golang-php.cn

Go でリストのすべての順列を効率的に生成するにはどうすればよいですか?

Susan Sarandon

リリース： 2024-12-07 16:44:14

オリジナル

802 人が閲覧しました

How Can I Efficiently Generate All Permutations of a List in Go?

Go ですべての順列を生成する: 効率的なアプローチ

データセットを扱うとき、多くの場合、要素のリストの可能なすべての順列を生成する必要があります。 Go は、順列の効率的な作成を可能にする堅牢なプログラミング環境を提供します。

ヒープのアルゴリズムは、順列を生成するためのよく知られた方法です。要素のペアを交換することによって、前の順列から各順列を構築します。次のヒープアルゴリズムの実装は、配列のすべての順列を返します:

func permutations(arr []int) [][]int {
    var helper func([]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 で順列を生成するためのその他のリソースには、次のものがあります。

[総合ガイド]順列について生成](https://www.section.io/engineering-education/go-generate-all-permutations-of-a-list/)
[GitHub での Go 実装](https://github .com/senghoo/golang-permutations)
[Python の itertools.permutations() に相当するもの行く](https://stackoverflow.com/questions/9179817/permutations-in-go)

以上がGo でリストのすべての順列を効率的に生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。