Skip to content

Instantly share code, notes, and snippets.

@athap
Created February 27, 2016 21:53
Show Gist options
  • Save athap/0f2d2b1c84a8c03fadd9 to your computer and use it in GitHub Desktop.
Save athap/0f2d2b1c84a8c03fadd9 to your computer and use it in GitHub Desktop.
Golang: Print all permutation of a string
package main
import "fmt"
/*
Return all permutations of a string
Example,
Find all perm of abc:
We will find all perms of the given string based on all perms of its substring
To find all perms of abc, we need to find all perms of bc, and then add a to those perms
To find all perms of bc, we need to find all perms of c, and add b to those perms
To find all perms of c, well we know that is only c
Now we can find all perms of bc, insert c at every available space in b
bc --> bc, cb
Now we need to add a to all perms of bc
abc, bac, bca (insert a in bc) -- acb, cab, cba (insert a in cb)
*/
func main() {
fmt.Printf("All perms are - %v", getPerms("abc"))
}
func getPerms(str string) []string {
// base case, for one char, all perms are [char]
if len(str) == 1 {
return []string{str}
}
current := str[0:1] // current char
remStr := str[1:] // remaining string
perms := getPerms(remStr) // get perms for remaining string
allPerms := make([]string, 0) // array to hold all perms of the string based on perms of substring
// for every perm in the perms of substring
for _, perm := range perms {
// add current char at every possible position
for i := 0; i <= len(perm); i++ {
newPerm := insertAt(i, current, perm)
allPerms = append(allPerms, newPerm)
}
}
return allPerms
}
// Insert a char in a word
func insertAt(i int, char string, perm string) string {
start := perm[0:i]
end := perm[i:len(perm)]
return start + char + end
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment