This Go program demonstrates how to generate all permutations of a given string. The algorithm uses a backtracking technique to generate each possible permutation of the string.

Program Code

package main

import (
	"fmt"
	"strings"
)

// function to swap elements at indices i and j in the slice
func swap(arr []rune, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

// backtracking function to generate permutations
func permute(arr []rune, l, r int, result *[]string) {
	// base case: if l == r, then print the permutation
	if l == r {
		*result = append(*result, string(arr))
		return
	}

	// recursive case: generate all permutations by swapping each element
	for i := l; i <= r; i++ {
		// swap the current element with itself and the remaining elements
		swap(arr, l, i)
		// recursive call to generate permutations of the remaining string
		permute(arr, l+1, r, result)
		// backtrack to revert the swap
		swap(arr, l, i)
	}
}

func main() {
	// Input string
	str := "ABC"
	// Convert the string to a slice of runes (characters)
	arr := []rune(str)
	var result []string
	
	// Generate all permutations
	permute(arr, 0, len(arr)-1, &result)
	
	// Output the result
	fmt.Println("All permutations of the string:", str)
	for _, perm := range result {
		fmt.Println(perm)
	}
}

Explanation

Here is an overview of the key components of the program:

• swap function: This helper function swaps two elements in a slice. It takes a slice of runes (which represents the string), and two indices i and j, and swaps the characters at those positions.
• permute function: This is a recursive function that generates permutations using backtracking. It takes the following parameters:
  • arr: The slice of characters (runes) to permute.
  • l: The starting index of the substring.
  • r: The ending index of the substring.
  • result: A pointer to a slice of strings where permutations will be stored.

  The function generates permutations by recursively swapping elements, generating all possible orderings of the characters in the slice.

• backtracking: After generating a permutation, the function backtracks by undoing the previous swap, restoring the string to its original state. This is critical for generating all valid permutations without skipping any.
• main function: The main function sets up the input string, converts it to a rune slice, and calls the permute function to generate all permutations. The result is then printed to the console.

Example Output

For the input string ABC, the output would be:

All permutations of the string: ABC
ABC
ACB
BAC
BCA
CAB
CBA

This program works by systematically generating and printing all permutations of the input string. The approach ensures that no permutation is missed and each one is unique.