Print permutations of a given string using backtracking
Permutation of a string is a way of arranging the characters in a specific order. In other words, it is a rearrangement of the characters in a string such that each arrangement is unique.
To generate all permutations of a string, one approach is to use backtracking. The algorithm for generating all permutations of a string using backtracking involves the following steps:
Fix a character at the current position.
Recursively generate all permutations for the remaining characters.
Swap the current character with the next character, and repeat step 2.
Undo the swap and continue to the next character.
This algorithm generates all possible permutations of the string by swapping characters at each position and recursively generating permutations for the remaining characters.
Code:
#include <stdio.h>
#include <string.h>
// Function to swap values at two pointers
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
// Base case: if the starting and ending indices are the same,
// we have generated a permutation, so print it
if (l == r)
printf("%s\n", a);
else
{
// For each character from the starting index to the ending index,
// swap it with the character at the starting index and generate
// permutations of the remaining substring recursively
for (i = l; i <= r; i++)
{
// Swap characters at positions l and i
swap((a + l), (a + i));
// Generate permutations of the remaining substring recursively
permute(a, l + 1, r);
// Backtrack: swap characters at positions l and i to restore
// the original string and continue with the next iteration
// of the loop, swapping the next character with the character
// at the starting index
swap((a + l), (a + i));
}
}
}
// Driver program to test above functions
int main()
{
char str[] = "ABC";
int n = strlen(str);
// Generate all permutations of the string and print them
permute(str, 0, n - 1);
return 0;
}
Output:
ABC
ACB
BAC
BCA
CBA
CAB
Explaination:
#include <stdio.h>
#include <string.h>
These are header files included in the program to provide the definitions of standard input/output functions and string manipulation functions, respectively.
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
This function takes two character pointers as parameters and swaps the values they point to using a temporary variable.
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s\n", a);
else
{
for (i = l; i <= r; i++)
{
swap((a + l), (a + i));
permute(a, l + 1, r);
swap((a + l), (a + i)); // backtrack
}
}
}
This function generates all permutations of the string by recursively swapping characters at positions l and i (starting from l) and then calling itself with the next index (l+1) until it reaches the end of the string. Once a permutation is generated, it is printed.
int main()
{
char str[] = "ABC";
int n = strlen(str);
permute(str, 0, n - 1);
return 0;
}
This is the main function that calls the permute function with the given string and its starting and ending indices. The program first calculates the length of the string using the strlen function and then passes it to the permute function. Finally, the program returns 0 to indicate successful execution.
Post a Comment