Program Code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void generatePermutations(std::string str, int l, int r) {
    // Base case: if left index equals right index, we have a permutation
    if (l == r) {
        std::cout << str << std::endl;
    } else {
        // Generate permutations by swapping each character
        for (int i = l; i <= r; i++) {
            std::swap(str[l], str[i]); // Swap current character with the first character
            generatePermutations(str, l + 1, r); // Recursively call for the next character
            std::swap(str[l], str[i]); // Backtrack to restore the original string
        }
    }
}

int main() {
    std::string str;
    std::cout << "Enter a string: ";
    std::cin << str;
    std::cout << "All permutations of the string are:" << std::endl;
    generatePermutations(str, 0, str.length() - 1);
    return 0;
}
    

Explanation of the Program Structure

This C++ program generates all possible permutations of a given string using a recursive approach.

Components:

1. Includes: The program includes essential headers:
   • <iostream> for input and output operations.
   • <string> for string manipulation.
   • <vector> and <algorithm> for handling collections and algorithms like swap.
2. generatePermutations Function: This function is responsible for generating permutations.
   • It takes three parameters: the string str, the left index l, and the right index r.
   • The base case checks if l is equal to r. If true, it means a permutation is formed and it prints the string.
   • In the loop, it swaps characters, recursively calls itself to generate further permutations, and then backtracks by swapping the characters back to their original position.
3. main Function: The entry point of the program.
   • It prompts the user for a string and reads the input.
   • It then calls the generatePermutations function to start generating permutations.

How to Compile and Run the Program

To compile and run this program, follow these steps:

1. Open a terminal or command prompt.
2. Navigate to the directory where the code is saved.
3. Compile the program using: g++ -o permutations permutations.cpp
4. Run the executable: ./permutations
5. Enter a string when prompted to see all its permutations.

Conclusion

This program effectively demonstrates the use of recursion and backtracking to generate permutations of a string. It can be further optimized or modified to handle cases such as duplicate characters in the string.