Wie kann der Heap-Algorithmus alle Permutationen in Go generieren?

Generieren aller Permutationen in Go

Einführung

Generieren aller möglichen Permutationen einer Liste von Elemente sind ein häufiges Problem bei der Programmierung. In diesem Artikel wird der Heap-Algorithmus untersucht, einer der einfachsten Ansätze zur Generierung aller Permutationen. Die generierten Permutationen werden nicht lexikografisch sortiert.

Heap-Algorithmus

Der Heap-Algorithmus generiert jede Permutation, indem er ein Elementpaar zum Austauschen auswählt. Es beginnt mit einem Basisfall, bei dem das Array nur ein Element enthält. Bei größeren Arrays iteriert es durch die Elemente und tauscht Paare aus, um rekursiv neue Permutationen zu generieren.

Go-Implementierung

Unten finden Sie eine Go-Implementierung des Heap-Algorithmus:

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
}

Nutzung Beispiel

Hier ist ein Beispiel für die Verwendung der Permutationsfunktion:

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

Ausgabe

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

Zusätzliche Hinweise

• Die Permutationen werden generiert, aber nicht sortiert lexikographisch.
• Für die lexikografische Sortierung sollten Sie die Verwendung eines faktoriellen Zahlensystems in Betracht ziehen, um die Permutationen zu generieren.

Das obige ist der detaillierte Inhalt vonWie kann der Heap-Algorithmus alle Permutationen in Go generieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!