Compute all the Permutations of the String in Go

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.

What are Permutations

Permutations of a string are all possible arrangements of its characters. For example, permutations of 'abc' include 'abc', 'acb', 'bac', 'bca', 'cab', and 'cba'.

Syntax

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:])
        }
    }
}

Example 1: Computing all permutations of a string

We can create a function named permute to compute all permutations of a given string using recursion.

For example,

  1. Define a function named permute that takes two parameters: prefix of type string and str of type string.
  2. Calculate the length n of the string str.
  3. If n is 0, print the prefix (base case).
  4. Otherwise, iterate through each character in str, recursively call permute with updated prefix and str by excluding the current character.
  5. In the main function, define an input string, call permute with an empty prefix and the input string, and print the result.

Go Program

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)
}

Output

Permutations of 'abc':
abc
acb
bac
bca
cab
cba