Examples of Print all Permutations of Given String
1. Using Backtracking
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time.
- This code initializes an empty array to store the permutations and defines a recursive function called permute to generate permutations.
- In the permute function, it swaps characters within the string to rearrange them, explores all possible permutations, and backtracks to explore other combinations.
- The process continues until it reaches a base case where a complete permutation is added to the result array. Finally, the code prints all generated permutations.
Example: Here is the practical implementation of the above method.
function generatePermutations(str) {
const permutations = [];
function permute(str, left, right) {
if (left == right) {
permutations.push(str);
} else {
for (let i = left; i <= right; i++) {
str = swap(str, left, i);
permute(str, left + 1, right);
str = swap(str, left, i);
}
}
}
function swap(a, i, j) {
const charArray = a.split("");
const temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return charArray.join("");
}
permute(str, 0, str.length - 1);
return permutations;
}
const str = "ABC";
const permutations = generatePermutations(str);
console.log("Permutations:");
console.log(...permutations);
Output
Permutations: ABC ACB BAC BCA CBA CAB
2. Using Iteration
The idea is to generate sorted permutations of the String. It uses the concept of lexicographically next greater permutation.
- findCeil function finds the index of the smallest character in the string str which is greater than first and occurs in the range [l, h].
- generateNextPermutation function generates the next lexicographically greater permutation of the input string str using the same logic as the original code sortedPermutations function repeatedly generates and prints the next permutation until there are no more permutations to generate.
Example: Here is the practical implementation of the above method.
function generatePermutations(inputString) {
const uniquePermutations = [];
function
generateUniquePermutations(arr, currentIndex) {
if (currentIndex === arr.length - 1) {
uniquePermutations.push(arr.join(""));
} else {
for (let i = currentIndex;
i < arr.length; i++) {
[arr[currentIndex], arr[i]] =
[arr[i], arr[currentIndex]];
generateUniquePermutations(
[...arr], currentIndex + 1);
}
}
}
generateUniquePermutations(inputString.split(""), 0);
return uniquePermutations;
}
const inputString = "CABC";
const uniquePermutations =
generatePermutations(inputString);
for (let i = 0;
i < uniquePermutations.length; i++) {
console.log(uniquePermutations[i]);
}
Output
CABC CACB CBAC CBCA CCAB CCBA ACBC ACCB ABCC ABCC ACCB ACBC BCAC BCCA BACC BACC BCCA BCAC CCAB CCBA CACB CABC CBCA CBAC
3. Using Heap’s Algorithm
Heap’s algorithm is an efficient method for generating all permutations of a string.
- First, we define a function that takes an array and two indices as arguments and swaps the elements at those indices in the array.
- Create a function that recursively generates permutations. If the length of the string is 1, print the permutation. Otherwise, iterate over each character and recursively generate permutations with the remaining characters.
- Initialize an array representation of the string. Call the permute function with the original string and its length. iterate over each character and recursively call the permute function with a reduced length and a swapped array to generate permutations.
Example: Here is the practical implementation of the above method.
function swap(strArr, i, j) {
const temp = strArr[i];
strArr[i] = strArr[j];
strArr[j] = temp;
}
function permute(str, n = str.length, strArr = str.split('')) {
if (n === 1) {
console.log(strArr.join(''));
} else {
for (let i = 0; i < n; i++) {
permute(str, n - 1, strArr);
if (n % 2 === 0) {
swap(strArr, i, n - 1);
} else {
swap(strArr, 0, n - 1);
}
}
}
}
const str = 'abcd';
permute(str);
Output
abcd bacd cabd acbd bcad cbad dbca bdca cdba dcba bcda cbda dacb adcb cdab dcab acdb cadb dabc adbc bdac dbac abdc badc
4: Using Iterative Method with Factorial Count
- Define a function
generatePermutations
that takes a stringstr
as input. - Initialize an empty array
permutations
to store all permutations. - Define a factorial function
factorial
to calculate the factorial of a given number. - Calculate the total number of permutations
totalPermutations
using the factorial of the string length. - Iterate from 0 to
totalPermutations
.- Initialize an empty string
currentPermutation
to store the current permutation. - Initialize a variable
temp
to store the current iteration index. - Split the input string
str
into an array of charactersavailableChars
. - Iterate backwards through the characters of the input string:
- Calculate the index of the next character in the permutation using
temp % (j + 1)
, wherej
is the current index. - Update
temp
toMath.floor(temp / (j + 1))
. - Append the character at the calculated index to
currentPermutation
. - Remove the character at the calculated index from
availableChars
.
- Calculate the index of the next character in the permutation using
- Push the generated permutation
currentPermutation
to thepermutations
array.
- Initialize an empty string
- Return the array of
permutations
.
Example:
function generatePermutations(str) {
const permutations = [];
const factorial = n => n <= 1 ? 1 : n * factorial(n - 1);
const len = str.length;
const totalPermutations = factorial(len);
for (let i = 0; i < totalPermutations; i++) {
let currentPermutation = '';
let temp = i;
const availableChars = str.split('');
for (let j = len - 1; j >= 0; j--) {
const index = temp % (j + 1);
temp = Math.floor(temp / (j + 1));
currentPermutation += availableChars[index];
availableChars.splice(index, 1);
}
permutations.push(currentPermutation);
}
return permutations;
}
const str = "ABC";
const permutations = generatePermutations(str);
console.log("Permutations:");
console.log(...permutations);
Output
Permutations: ABC BAC CAB ACB BCA CBA
JavaScript Program to Print all Permutations of Given String
In this article, we will see how to write a program that prints all permutations of a given string. Permutation refers to each of several possible ways in which a set or number of things can be ordered or arranged. There are N! permutations for a string of length N.
Examples:
Input: S = “XY”
Output: “XY”, “YX”