C Program
#include <stdio.h>
#include <string.h>
void swap(char *a, char *b) {
char temp = *a;
*a = *b;
*b = temp;
}
void permute(char *str, int left, int right) {
if (left == right) {
printf("%s\n", str);
return;
}
for (int i = left; i <= right; i++) {
swap(&str[left], &str[i]);
permute(str, left + 1, right);
swap(&str[left], &str[i]); // backtrack
}
}
int main() {
char str[] = "abc";
int n = strlen(str);
permute(str, 0, n - 1);
return 0;
}C Output
abc acb bac bca cba cab
C++ Program
#include <iostream>
#include <string>
using namespace std;
void swapChar(char &a, char &b) {
char temp = a;
a = b;
b = temp;
}
void permute(string &str, int left, int right) {
if (left == right) {
cout << str << endl;
return;
}
for (int i = left; i <= right; i++) {
swapChar(str[left], str[i]);
permute(str, left + 1, right);
swapChar(str[left], str[i]); // backtrack
}
}
int main() {
string str = "abc";
permute(str, 0, str.size() - 1);
return 0;
}C++ Output
abc acb bac bca cba cab
JAVA Program
public class Main {
static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void permute(char[] arr, int left, int right) {
if (left == right) {
System.out.println(new String(arr));
return;
}
for (int i = left; i <= right; i++) {
swap(arr, left, i);
permute(arr, left + 1, right);
swap(arr, left, i); // backtrack
}
}
public static void main(String[] args) {
String str = "abc";
permute(str.toCharArray(), 0, str.length() - 1);
}
}JAVA Output
abc acb bac bca cba cab
Python Program
def permute(s, left, right):
if left == right:
print("".join(s))
return
for i in range(left, right + 1):
s[left], s[i] = s[i], s[left]
permute(s, left + 1, right)
s[left], s[i] = s[i], s[left] # backtrack
s = list("abc")
permute(s, 0, len(s) - 1)Python Output
abc acb bac bca cba cab
Explanation
Example
For the string "abc", permutations are every possible arrangement of its characters: "abc", "acb", "bac", "bca", "cba", "cab". Recursion produces them by swapping characters and keeping one position fixed at a time, and then allowing the remainder of the string to be permuted. After a position has been fixed, recursion moves on to the next position until all possible arrangements have been printed.
Real-Life Analogy
Consider seating three friends — Alice, Bob, and Charlie — around a table. You initially set who is sitting in the first seat, then you set who is sitting in the second seat, and lastly the third seat fills up by default. After doing that, you attempt another configuration by rearranging people. That's precisely what permutation generation does: it tries out all possible seating configurations.
Why It Matters
Permutations are crucial to problem-solving when order is crucial. This is used in cryptography (attempting all possible key orders), scheduling (sequence of tasks), games (randomizing moves), and test generation (all possible input sequences). Recursion with backtracking is the most intuitive means of systematically trying out each possibility without omission or duplication.
This exercise educates us on how to use recursion and backtracking together. Recursion divides the problem into smaller subproblems (sorting positions one at a time), and backtracking is done so that we retain the original order after every recursive step in order to explore new arrangements without interference from the last swaps. The novice learns that recursion is not repetition; it's guided exploration with efficient state handling.
Use in Interviews and Projects
Interviewers frequently ask permutation problems to test whether you can merge swapping and recursion with logic. They might also include spin-offs such as skipping duplicates or computing permutations in lexicographic order. In actual projects, permutations are useful in testing algorithms, simulating situations, and solving puzzles like the traveling salesman problem.
SEO-Friendly Closing
All string permutations using recursion in C, C++, Java, and Python is a core programming skill required to master backtracking and venturing into ordered arrangement explorations. Having knowledge of how to place fixed positions, swap values, and recover original positions gives programmers the capability to solve challenging ordering issues in competitive programming, interview problems, and cryptographic key generation, scheduling, and simulation in real-world applications. This method does not only make your understanding of recursion more profound but also enhances problem-solving skills on various programming languages.
Social Plugin