How Can Heap\'s Algorithm Generate All Permutations in Go?

Generating All Permutations in Go

Introduction

Generating all possible permutations of a list of elements is a common problem in programming. This article explores Heap's algorithm, one of the simplest approaches to generating all permutations. The generated permutations will not be sorted lexicographically.

Heap's Algorithm

Heap's algorithm generates each permutation by choosing a pair of elements to interchange. It starts with a base case where the array has only one element. For larger arrays, it iterates through the elements, interchanging pairs to generate new permutations recursively.

Go Implementation

Below is a Go implementation of Heap's algorithm:

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
}

Usage Example

Here is an example of how to use the permutations function:

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

Additional Notes

• The permutations are generated but not sorted lexicographically.
• For lexicographical sorting, consider using a factorial number system to generate the permutations.

The above is the detailed content of How Can Heap\'s Algorithm Generate All Permutations in Go?. For more information, please follow other related articles on the PHP Chinese website!