C Program: Generate All Permutations of a Given String

This C program generates all permutations of a given string using recursion.

Program Code

#include 
#include 

// Function to swap two characters
void swap(char *x, char *y) {
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

// Recursive function to generate permutations
void permute(char *str, int l, int r) {
    int i;
    if (l == r)
        printf("%s\n", str);
    else {
        for (i = l; i <= r; i++) {
            swap((str + l), (str + i));
            permute(str, l + 1, r);
            swap((str + l), (str + i)); // backtrack
        }
    }
}

int main() {
    char str[] = "ABC"; // Input string
    int n = strlen(str);
    printf("All permutations of the string are:\n");
    permute(str, 0, n - 1);
    return 0;
}
    

Explanation

• swap: This function swaps two characters in the string. It takes two pointers as parameters and exchanges the characters they point to.
• permute: This is a recursive function that generates all permutations of the given string.
  • If the current position l is equal to the end position r, the function prints the permutation of the string.
  • Otherwise, it loops through the characters, swapping each character with the current position l, recursively calling itself with the next position, and then swapping the characters back (backtracking).
• main: This function initializes the string to be permuted and calculates its length. It then calls the permute function to generate and print all permutations.

How It Works

The program starts by calling the permute function with the initial positions of the string. The function recursively generates permutations by swapping characters and exploring all possibilities. The backtracking step ensures that the function returns to the previous state before trying the next permutation.

Example Output

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

Explanation:

• swap Function: This function swaps two characters in the string. It’s used to generate permutations by rearranging characters.
• permute Function: This is the core recursive function that generates permutations. It prints the permutation when the current position equals the end of the string and uses recursion to generate permutations for other positions.
• main Function: Initializes the input string and calls the permute function to start the permutation process.

The program generates all permutations of the input string and prints them. The example output shows all permutations for the string "ABC".