Bagaimanakah Algoritma Heap Boleh Menjana Semua Pilihatur dalam Go?

Menjana Semua Pilihatur dalam Go

Pengenalan

Menjana semua pilih atur yang mungkin bagi senarai elemen adalah masalah biasa dalam pengaturcaraan. Artikel ini meneroka algoritma Heap, salah satu pendekatan paling mudah untuk menjana semua pilih atur. Pilih atur yang dijana tidak akan diisih secara leksikografik.

Algoritma Heap

Algoritma Heap menjana setiap pilihatur dengan memilih sepasang elemen untuk ditukar. Ia bermula dengan kes asas di mana tatasusunan hanya mempunyai satu elemen. Untuk tatasusunan yang lebih besar, ia berulang melalui elemen, bertukar-tukar pasangan untuk menjana pilih atur baharu secara rekursif.

Pelaksanaan Go

Di bawah ialah pelaksanaan Go bagi algoritma Heap:

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
}

Penggunaan Contoh

Berikut ialah contoh cara menggunakan fungsi pilih atur:

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

Output

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

Nota Tambahan

• Pilihan dijana tetapi tidak diisih mengikut leksikografi.
• Untuk pengisihan leksikografi, pertimbangkan untuk menggunakan sistem nombor faktorial untuk menjana pilih atur.

Atas ialah kandungan terperinci Bagaimanakah Algoritma Heap Boleh Menjana Semua Pilihatur dalam Go?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!