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

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
BACD
BCDA
BDCA
BDAC
CBDA
CABD
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 :