Generate Permutations of a String

#include <stdio.h>
#include <string.h>

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

// Function to generate permutations of the string
void permute(char* str, int left, int right) 
{
    // Base case: if left index is equal to right index, we print the permutation
    if (left == right) 
{
        printf("%s\n", str);
    }
 else 
{
        // Recursively swapping characters to generate permutations
        for (int i = left; i <= right; i++) {
            swap((str + left), (str + i));  // Swap the current character
            permute(str, left + 1, right);  // Recurse for the next character
            swap((str + left), (str + i));  // Backtrack (swap the characters back)
        }
    }
}

int main() {
    char str[] = "ABC";  // The string to permute
    int n = strlen(str);  // Calculate the length of the string
    permute(str, 0, n - 1);  // Call the permutation function
    return 0;
}

explaination :-

1) Swap Function:

=The swap() function is a utility function used to exchange two characters within the string. It takes two pointers (x and y) and swaps the characters they point to.

2) Permute Function:

=This function generates permutations of the string by recursively swapping characters.
=The function has three parameters:
=str: The string whose permutations are to be generated.
=left: The starting index (initially 0).
=right: The ending index (length of the string – 1).
=The base case is when left == right. At this point, we have reached a specific permutation, so it is printed.
=If left != right, a loop is used to generate all possible permutations by:
=Swapping the current character with each of the subsequent characters.
=Recursing for the remaining substring.
=Backtracking (i.e., swapping the characters back to their original positions) to explore other possibilities.

3) Main Function:

=We initialize the string str with the characters “ABC” that we want to permute.
=The strlen() function calculates the length of the string.
=The permute() function is called with the string, starting index 0, and ending index n-1 (which is 2 for the string “ABC”).

Output :-

=When the above program is executed, it will generate and print all permutations of the string “ABC”. The output will be:

ABC
ACB
BAC
BCA
CAB
CBA

How the Output is Generated :-

1)The function starts with “ABC” and then swaps:
‘A’ with ‘A’ → Recursion continues with “ABC”.
‘A’ with ‘B’ → Recursion continues with “BAC”.
‘A’ with ‘C’ → Recursion continues with “CBA”.
2)For each swap, further recursive calls explore all possibilities, and once a permutation is complete, it is printed.
3)After exploring all possibilities starting from ‘A’, the function backtracks and explores permutations starting with ‘B’ and ‘C’ similarly.

:- This recursive method ensures that all permutations are generated without duplicates.