Go Program: Generate All Permutations of a Given String

This document provides a Go program to generate all permutations of a given string, along with an explanation of its structure and functionality.

Go Program

package main

import (
    "fmt"
)

// permute generates all permutations of the string s and appends them to the result.
func permute(s string, result *[]string, l int, r int) {
    if l == r {
        *result = append(*result, s)
    } else {
        for i := l; i <= r; i++ {
            // Convert string to a slice of runes to manipulate characters
            chars := []rune(s)
            // Swap characters at positions l and i
            chars[l], chars[i] = chars[i], chars[l]
            // Recursively permute the remaining characters
            permute(string(chars), result, l+1, r)
            // Backtrack to restore the original string
            chars[l], chars[i] = chars[i], chars[l]
        }
    }
}

func main() {
    str := "ABC" // Change this to any string for permutation
    var result []string
    permute(str, &result, 0, len(str)-1)
    fmt.Println("Permutations:")
    for _, perm := range result {
        fmt.Println(perm)
    }
}
    

Program Structure and Explanation

The Go program is designed to generate and display all possible permutations of a given string. Here’s a detailed explanation of its structure:

• Package Import: The program imports the fmt package for formatted I/O operations.
• Permute Function:
  • Parameters:
    • s: The string for which permutations are to be generated.
    • result: A pointer to a slice of strings that will hold all the permutations.
    • l: The starting index of the substring to be permuted.
    • r: The ending index of the substring to be permuted.
  • Functionality:
    • If l == r, the current permutation (i.e., the string s) is added to the result slice.
    • Otherwise, the function iterates over the substring, swapping each character at index l with characters at indices from l to r.
    • It then recursively calls itself to generate permutations of the remaining substring.
    • After recursive calls, it backtracks by swapping the characters back to their original positions.
• Main Function:
  • Defines the input string str for which permutations are to be generated.
  • Calls the permute function with the initial parameters.
  • Prints all generated permutations.

How to Use

1. Copy the Go program into a file named main.go.

2. Open a terminal and navigate to the directory containing main.go.

3. Run the command go run main.go to execute the program and see the permutations of the string.

Customization

To generate permutations of a different string, modify the value of the str variable in the main function.

Explanation:

1. Program: The Go code snippet generates all permutations of a given string. It uses recursion and backtracking to achieve this.
2. permute Function: This function performs the core permutation logic by recursively generating permutations and appending them to the result slice. It uses character swapping and backtracking.
3. main Function: Sets the input string, initializes the result slice, and calls the permute function. It then prints all permutations.
4. Usage Instructions: Provides steps to run the program and customize the input string.