JavaScript String Permutation Program with nice explanation

JavaScript String Permutation Program
💡 Let’s understand first What is Permutation in math?
Selection of subsets is called a permutation when the order of selection matters, a combination when order is not a factor.
In simple words:When the order doesn't matter, it is a Combination.
Permutation is When the order does matter.
💡 Permutations with Repetition
If repetition is allowed, then it is easy to calculate, When a thing has n different types, we have n choices each time.
and the formula is: n
r
If we have 6 numbers (0,1,2,3,4,5) and we have to choose 3 of them so we can do: 6 * 6 * 6
💡 Permutations without Repetition
Here if one number is selected we can not select that again, which means we have to reduce the number of available choices each time.The formula is: !n
If we have 6 numbers (0,1,2,3,4,5) and we have to choose 3 of them so we can do: 6 * 5 * 4
You can read more here about Permutation and Combination.
https://www.mathsisfun.com/combinatorics/combinations-permutations.html
💡 Now see Flow Chart and how it is flowing.
You can see numbering from 1 to 19 on each box
in the above flow diagram. Our Algorithm will flow same as these numbers
. You can clearly understand with a diagram which block will execute after which block by this numbering.
findPermutation('ABC') swap count: 1 swap A with A => ABC swap count: 2 swap B with B => ABC *Output* -> ABC swap count: 3 backTracking Go to parent element => ABC swap count: 4 swap B with C => ACB *Output* -> ACB swap count: 5 backTracking Go to parent element => ABC swap count: 6 backTracking Go to parent element => ABC swap count: 7 swap A with B => BAC swap count: 8 swap A with A => BAC *Output* -> BAC swap count: 9 backTracking Go to parent element => BAC swap count: 10 swap A with C => BCA *Output* -> BCA swap count: 11 backTracking Go to parent element => BAC swap count: 12 backTracking Go to parent element => ABC swap count: 13 swap A with C => CBA swap count: 14 swap B with B => CBA *Output* -> CBA swap count: 15 backTracking Go to parent element => CBA swap count: 16 swap B with A => CAB *Output* -> CAB swap count: 17 backTracking Go to parent element => CBA swap count: 18 backTracking Go to parent element => ABC undefined
………………………..
JavaScript Program
You can remove console.log in final program. This is just for testing purpose.
//https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ /** * @param {} str - This is string input * @param {} i - This is first index * @param {} j - This is second index * @param {} check - This is just for Debugging purpose, you can omit this in final code */ /** * LOGIC ***** * First Convert string input into array using spread operator * If string is 'ABC' > array will be ['A', 'B', 'C'] * Create a temp variable and put array first index element into this: temp = arr[i]; * Now in first index element, save second index element: arr[i] = arr[j]; * Put temp variable into array second index element: arr[j] = temp; */ function swap(str, i, j) { let temp; let arr = [...str]; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; console.count('swap count') return arr.join(""); } /** * @param {} str - This is string input * @param {} startIndex - This is start Index: initially it is 0 * @param {} endIndex - This is end Index: Initially it is string input length - 1 */ /** * LOGIC ********* * 1. If startIndex and endIndex becomes equal then print string, means now function reached to the final depth * In Else part run a for loop with startIndex to endIndex and do i++ * Now call swap function * Call permutate function * Again call swap function : this is for backtracking. * */ permutate = (str, startIndex, endIndex) => { if (startIndex === endIndex) { // Print string when startIndex and endIndex are same means we have reached to last depth of cycle. console.log('*Output* ->', str); } else { for (var i = startIndex; i <= endIndex; i++) { //startIndex is fixed for each inner iteration means we have fixed one character and will swap that with other characters str = swap(str, startIndex, i); console.log('swap', str[i], ' with ', str[startIndex], ' => ', str); //now call permutate function for startIndex + 1. permutate(str, startIndex + 1, endIndex); // Call swap again. We have to revert swapped string into its parent one. (called backtracking) str = swap(str, startIndex, i); console.log('backTracking Go to parent element => ', str); } } }; /** * @param {} inputStr - This is input string * * This is main function which we have to call * Call another private function permutate() with 3 parameters. * permutate(inputStr, 0, len - 1); - first is string, second is 0 and third is string length - 1 * */ findPermutation = (inputStr) => { let len = inputStr.length; permutate(inputStr, 0, len - 1); };
*****Run program****** findPermutation('ABC') ABC ACB BAC BCA CBA CAB
**Run Program ****** There will be 24 permutation of this string 'ABCD'. and that is 4! 4! = 4 * 3 * 2 * 1 = 24 findPermutation('ABCD') ABCD ABDC ACBD ACDB ADCB ADBC BACD BADC BCAD BCDA BDCA BDAC CBAD CBDA CABD CADB CDAB CDBA DBCA DBAC DCBA DCAB DACB DABC
Time Complexity:Â
O (time to print one permutation * total number of permutations)
O(n*n!)
Note that there are n! permutations and it requires O(n) time to print a permutation.
💡 JavaScript Interview Questions and Answers :
https://www.jsmount.com/javascript-interview-questions-answers-for-experienced-part-1/
JavaScript String Permutation Program
One thought on “JavaScript String Permutation Program with nice explanation”