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: nr

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

0

0