[Golang] All Permutations of Given String With Distinct Characters
source link: http://siongui.github.io/2017/03/11/go-all-permutations-of-given-string-with-all-distinct-characters/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Question
Given a string containing all distinct characters, find all permutations of it. [2]
PS: I came to this question via HN [1], and it looks interesting. So I try to port the code from C++ to Go.
Answer
Use Backtracking algorithm. See original post for explanation.
package main // Swap the i-th byte and j-th byte of the string func swap(s string, i, j int) string { var result []byte for k := 0; k < len(s); k++ { if k == i { result = append(result, s[j]) } else if k == j { result = append(result, s[i]) } else { result = append(result, s[k]) } } return string(result) } // Function to find all Permutations of a given string str[i:n] // containing all distinct characters func permutations(str string, i, n int) { // base condition if i == n-1 { println(str) return } // process each character of the remaining string for j := i; j < n; j++ { // swap character at index i with current character str = swap(str, i, j) // recursion for string [i+1:n] permutations(str, i+1, n) // backtrack (restore the string to its original state) str = swap(str, i, j) } } func main() { str := "ABC" permutations(str, 0, len(str)) }
Tested on: Go Playground
References:
[3]Strings, bytes, runes and characters in Go - The Go Blog
[4]Data Structures and Algorithms Problems | Hacker News
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK