{"id":550,"date":"2025-11-21T08:53:32","date_gmt":"2025-11-21T03:23:32","guid":{"rendered":"https:\/\/codexplained.in\/?p=550"},"modified":"2025-11-21T08:53:32","modified_gmt":"2025-11-21T03:23:32","slug":"generate-permutations-of-a-string","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=550","title":{"rendered":"Generate Permutations of a String"},"content":{"rendered":"
\n#include <stdio.h>\n#include <string.h>\n\n\/\/ Function to swap two characters in a string\nvoid swap(char* x, char* y) \n{\n    char temp;\n    temp = *x;\n    *x = *y;\n    *y = temp;\n}\n\n\/\/ Function to generate permutations of the string\nvoid permute(char* str, int left, int right) \n{\n    \/\/ Base case: if left index is equal to right index, we print the permutation\n    if (left == right) \n{\n        printf("%s\\n", str);\n    }\n else \n{\n        \/\/ Recursively swapping characters to generate permutations\n        for (int i = left; i <= right; i++) {\n            swap((str + left), (str + i));  \/\/ Swap the current character\n            permute(str, left + 1, right);  \/\/ Recurse for the next character\n            swap((str + left), (str + i));  \/\/ Backtrack (swap the characters back)\n        }\n    }\n}\n\nint main() {\n    char str[] = "ABC";  \/\/ The string to permute\n    int n = strlen(str);  \/\/ Calculate the length of the string\n    permute(str, 0, n - 1);  \/\/ Call the permutation function\n    return 0;\n}\n\n\n<\/pre><\/div>\n\n\n
explaination<\/strong> :-<\/p>\n\n\n\n
1) Swap Function:<\/p>\n\n\n\n
=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.<\/p>\n\n\n\n
2) Permute Function:<\/p>\n\n\n\n
=This function generates permutations of the string by recursively swapping characters.
=The function has three parameters:
=str: <\/strong>The string whose permutations are to be generated.
=left:<\/strong> The starting index (initially 0).
=right: <\/strong>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.<\/p>\n\n\n\n
3) Main Function:<\/p>\n\n\n\n
=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”).<\/p>\n\n\n\n
Output<\/strong> :-<\/p>\n\n\n\n
=When the above program is executed, it will generate and print all permutations of the string “ABC”. The output will be:<\/p>\n\n\n
\nABC\nACB\nBAC\nBCA\nCAB\nCBA\n<\/pre><\/div>\n\n\n
<\/p>\n\n\n\n
How the Output is Generated<\/strong> :-<\/p>\n\n\n\n
1)<\/strong>The function starts with “ABC” and then swaps:
‘A’ with ‘A’ \u2192 Recursion continues with “ABC”.
‘A’ with ‘B’ \u2192 Recursion continues with “BAC”.
‘A’ with ‘C’ \u2192 Recursion continues with “CBA”.
2)<\/strong>For each swap, further recursive calls explore all possibilities, and once a permutation is complete, it is printed.
3)<\/strong>After exploring all possibilities starting from ‘A’, the function backtracks and explores permutations starting with ‘B’ and ‘C’ similarly.<\/p>\n\n\n\n
:- This recursive method ensures that all permutations are generated without duplicates.<\/p>\n\n\n\n
<\/p>\n