Skip to content

Instantly share code, notes, and snippets.

@kingishb

kingishb/main.go

Created December 13, 2019 04:38
Show Gist options
  • Save kingishb/1fb73c2e4cc85f63bec9f23fdb4e26dd to your computer and use it in GitHub Desktop.
Save kingishb/1fb73c2e4cc85f63bec9f23fdb4e26dd to your computer and use it in GitHub Desktop.
Download ZIP
gen permutations with heap's algorithm - https://en.wikipedia.org/wiki/Heap%27s_algorithm
Raw
main.go
package main
import "fmt"
// swap swaps elements in a slice
func swap(i, j int, slice []int) {
v1 := slice[i]
v2 := slice[j]
slice[i] = v2
slice[j] = v1
}
// permute generates permutations by heap's algorithm.
// https://en.wikipedia.org/wiki/Heap%27s_algorithm
func permutations(n int, ints []int) {
if n == 1 {
fmt.Println(ints)
} else {
for i := 0; i < n; i++ {
permutations(n-1, ints)
if n%2 == 0 {
swap(i, n-1, ints)
} else {
swap(0, n-1, ints)
}
}
}
}
func main() {
permutations(3, []int{1, 2, 3})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment