Permutations

Mark as Completed

Lesson

Write a function in JavaScript to find all possible permutations of a given string. Explain the difference between permutations and combinations and the use cases for each.

Example:

Input: "123"
Output: ["123", "132", "213", "231", "312", "321"]

Walkthrough

Permutations are a way of selecting and arranging items from a collection where order matters. Combinations, on the other hand, are a way of selecting items from a collection where order does not matter. In this question, we will focus on finding all possible permutations of a given string.

To find all possible permutations of a given string, we will use the backtracking technique. The idea is to fix one character at a time and recursively find all possible permutations of the remaining characters. We will start by creating a function called findPermutations
that takes in a string as input and returns an array of all possible permutations.

function findPermutations(str) {
  let result = []; // initialize an empty array to store permutations

  // base case for recursion
  if (str.length === 1) {
    result.push(str);
    return result;
  }

  // loop through each character of the string
  for (let i = 0; i < str.length; i++) {
    let firstChar = str[i];
    let remainingChars = str.substring(0, i) + str.substring(i + 1);
    let innerPermutations = findPermutations(remainingChars);

    // loop through inner permutations and add firstChar to each permutation
    for (let j = 0; j < innerPermutations.length; j++) {
      result.push(firstChar + innerPermutations[j]);
    }
  }

  return result;
}

In the findPermutations
function, we first initialize an empty array called result
to store all possible permutations. Then, we check the base case for recursion, which is when the length of the string is 1. In this case, we simply add the string to the result
array and return it.If the length of the string is greater than 1, we loop through each character of the string using a for
loop. For each character, we fix it as the first character and find all possible permutations of the remaining characters using recursion. We store these permutations in a variable called innerPermutations
.Finally, we loop through each permutation in innerPermutations
and add the first character to the beginning of each permutation. We push these new permutations to the result
array and return it.The time complexity of this solution is O(nn!) because for each character in the string, we have to recursively call the findPermutations
function on a smaller substring. Since there are n characters in the string, we have n levels of recursion. For each level of recursion, we have to loop through n-1 characters to find all possible permutations of the remaining characters. This gives us a time complexity of n * (n-1) * (n-2) * ... * 1, which is n!. The space complexity of this solution is also O(nn!) because we have to store all possible permutations in an array.

Difference between permutations and combinations:

Permutations and combinations are two different ways of selecting items from a collection. Permutations take into account the order in which the items are selected, while combinations do not.

This difference is important in many applications. For example, if we have a lock with three digits, we can generate all possible permutations of the digits to try to unlock the lock. However, if we only need to know which three digits were used, and not the order in which they were used, we only need to generate the combinations.

Another example is when dealing with sets of items. In a set, the order of the items does not matter. Therefore, if we want to count how many subsets of size k are in a set of size n, we would use combinations. If we want to count how many ways there are to choose k items from a set of n, where order matters, we would use permutations.

Previous Lesson Next Lesson