w3resource

JavaScript: Generate all permutations of a string

JavaScript fundamental (ES6 Syntax): Exercise-136 with Solution

String Permutations (With Duplicates)

Write a JavaScript program to generate all permutations of a string (contains duplicates).

  • Use recursion.
  • For each letter in the given string, create all the partial permutations for the rest of its letters.
  • Use Array.prototype.map() to combine the letter with each partial permutation.
  • Use Array.prototype.reduce() to combine all permutations in one array.
  • Base cases are for String.prototype.length equal to 2 or 1.
  • WARNING: The execution time increases exponentially with each character. Anything more than 8 to 10 characters will cause your environment to hang as it tries to solve all the different combinations.

Sample Solution:

JavaScript Code:

//#Source https://bit.ly/2neWfJ2

// Define the 'stringPermutations' function.
const stringPermutations = str => {
  // Base case: If the length of the string is less than or equal to 2, return permutations accordingly.
  if (str.length <= 2) {
    return str.length === 2 ? [str, str[1] + str[0]] : [str];
  }

  // For longer strings, recursively generate permutations.
  return str.split('').reduce((acc, letter, i) => {
    const remainingChars = str.slice(0, i) + str.slice(i + 1); // Remove the current letter from the string.
    const permutations = stringPermutations(remainingChars); // Recursively generate permutations for the remaining characters.
    // For each permutation, concatenate the current letter and add it to the accumulator.
    return acc.concat(permutations.map(val => letter + val));
  }, []);
};

// Test the 'stringPermutations' function with different strings.
console.log(stringPermutations('abc'));  
console.log(stringPermutations('*$*'));

Output:

["abc","acb","bac","bca","cab","cba"]
["*$*","**$","$**","$**","**$","*$*"]

Visual Presentation:

JavaScript Fundamental: Generate all permutations of a string.

Flowchart:

flowchart: Generate all permutations of a string

Live Demo:

See the Pen javascript-basic-exercise-136-1 by w3resource (@w3resource) on CodePen.


For more Practice: Solve these Related Problems:

  • Write a JavaScript program that generates all unique permutations of a string that may contain duplicate characters.
  • Write a JavaScript function that recursively produces permutations for a given string while filtering out duplicates.
  • Write a JavaScript program that uses backtracking to list all distinct arrangements of the characters in a string.

Go to:


PREV : Sum of Powers in Range.
NEXT : Stable Sort Array.

Improve this sample solution and post your code through Disqus

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.