In this tutorial, we will learn how to compute all permutations of a string in Go using recursion. Permutations are all possible rearrangements of the characters of a string.
Permutations of a string are all possible arrangements of its characters. For example, permutations of 'abc' include 'abc', 'acb', 'bac', 'bca', 'cab', and 'cba'.
The syntax to compute all permutations of a string in Go using recursion is:
func permute(prefix string, str string) {
n := len(str)
if n == 0 {
fmt.Println(prefix)
} else {
for i := 0; i < n; i++ {
permute(prefix+string(str[i]), str[:i]+str[i+1:])
}
}
}
We can create a function named permute
to compute all permutations of a given string using recursion.
For example,
permute
that takes two parameters: prefix
of type string
and str
of type string
.n
of the string str
.n
is 0, print the prefix
(base case).str
, recursively call permute
with updated prefix
and str
by excluding the current character.permute
with an empty prefix and the input string, and print the result.package main
import (
"fmt"
)
// permute computes all permutations of a given string
func permute(prefix string, str string) {
n := len(str)
if n == 0 {
fmt.Println(prefix)
} else {
for i := 0; i < n; i++ {
permute(prefix+string(str[i]), str[:i]+str[i+1:])
}
}
}
func main() {
input := "abc"
fmt.Printf("Permutations of '%s':\n", input)
permute("", input)
}
Permutations of 'abc': abc acb bac bca cab cba