Is there any pre-built method for finding all permutations of a given string in JavaScript?

Question

I'm a newbie to the JavaScript world. As the title mentions, I want to know whether there is any pre-built method in JavaScript to find all possible permutations of a given string.

For example, given the input:

the

Desired output:

the
teh
eht
eth
het
hte

Answer 1

//string permutation

function permutation(start, string) {

    //base case
    if ( string.length == 1 ) {
        return [ start + string ];
    } else {

        var returnResult = [];
        for (var i=0; i < string.length; i++) {
            var result = permutation (string[i], string.substr(0, i) + string.substr(i+1));
            for (var j=0; j<result.length; j++) {
                returnResult.push(start + result[j]);
            }
        }

        return returnResult;
    }
}

permutation('','123') will return

["123", "132", "213", "231", "312", "321"]

Answer 2

function permutations(str){
  if (str.length === 1) {
      return str;
 }
  var permut = [];
  for (var i=0; i<str.length; i++){
      var s = str[0];
      var _new =  permutations(str.slice(1, str.length));
      for(var j=0; j<_new.length; j++) {
          permut.push(s + _new[j]);
      }
      str = str.substr(1, str.length -1) + s;
  }
  return permut;
}

permutations('the');
//output returns:[ 'the', 'teh', 'het', 'hte', 'eth', 'eht' ]

Answer 3

This is similar but finds all anagrams/permutations from an array of words. I had this question in an interview. Given an array of words ['cat', 'dog', 'tac', 'god', 'act'], return an array with all the anagrams grouped together. Makes sure the anagrams are unique.

var arr = ['cat', 'dog', 'tac', 'god', 'act'];

var allAnagrams = function(arr) {
    var anagrams = {};
    arr.forEach(function(str) {
        var recurse = function(ana, str) {
            if (str === '') 
                anagrams[ana] = 1;
            for (var i = 0; i < str.length; i++)
                recurse(ana + str[i], str.slice(0, i) + str.slice(i + 1));
        };
        recurse('', str);
    });
    return Object.keys(anagrams);
}

console.log(allAnagrams(arr));
//["cat", "cta", "act", "atc", "tca", "tac", "dog", "dgo", "odg", "ogd", "gdo", "god"]

Answer 4

No pre-built, but writing such function is possible.. here is one relatively simple way using two functions:

function FindAllPermutations(str, index, buffer) {
    if (typeof str == "string")
        str = str.split("");
    if (typeof index == "undefined")
        index = 0;
    if (typeof buffer == "undefined")
        buffer = [];
    if (index >= str.length)
        return buffer;
    for (var i = index; i < str.length; i++)
        buffer.push(ToggleLetters(str, index, i));
    return FindAllPermutations(str, index + 1, buffer);
}

function ToggleLetters(str, index1, index2) {
    if (index1 != index2) {
        var temp = str[index1];
        str[index1] = str[index2];
        str[index2] = temp;
    }
    return str.join("");
}

Usage:

var arrAllPermutations = FindAllPermutations("the");

Live test case: http://jsfiddle.net/yahavbr/X79vz/1/

This is just basic implementation, it won't remove duplicates and has no optimization. However for small strings you won't have any problem, add time measure like in the above test case and see what's your reasonable limit.

Answer 5

Assuming a large string to search, you could use a regular expression

to examine a set of possibles that first matches the letters and the total number of letters,

and return the matches that use the same letter set as the pattern.

//(case-insensitive)

function lettersets(str, pat){
    var A= [], M, tem,
    rx= RegExp('\\b(['+pat+']{'+pat.length+'})\\b', 'gi'),
    pattern= pat.toLowerCase().split('').sort().join('');
    while((M= rx.exec(str))!= null){
        tem= M[1].toLowerCase().split('').sort();
        if(tem.join('')=== pattern) A.push(M[1]);
    };
    return A;
}

lettersets(s, 'the').sort();

Answer 6

function swap(a, b, str) {
  if (a == b)
    str = str;

  else {
    str = str.split("");
    var temp = str[a];
    str[a] = str[b];
    str[b] = temp;
    str = str.join("");
  }
}

function anagram(a1, b1, ar) {
  if (a1 == b1)
    document.write(ar + "<br/>");

  else
    for (i = a1; i < b1; i++) {
      swap(a1, b1, ar);
      anagram((a1) ++, b1, ar);
      swap(a1, b1, ar);
    }
}

Answer 7

Well there isnt any built in function in js(i dont believe it to be in any coding language)......and anyways this is the fully functioning program, it omits any repetitions and also displays the number of permutations.....

var n=0;
var counter=0;
var storarr=new Array();

function swap(a,b,str) {        //swaps the terms str[a] and str[b] and returns the final str
        str = str.split("");
        var temp = str[a];
        str[a] = str[b];
        str[b] = temp;
        return str.join("");
}

function anagram(_a,_b,ar) {        //actual function which produces the anagrams
    if(_a == _b) {
    storarr[n]=ar;
    n++;
    counter++;
    }
    else {
        for(var i= _a;i<= _b;i++) {
            ar=swap(_a,i,ar);
            anagram(_a+1,_b,ar);
            ar=swap(_a,i,ar);
        }
    }
}

function factorial(a) {         //return a!
    var x=1;
    for(var i=1;i<=a;i++)
    x=x*i;
    return x;
}

var strl=prompt("Enter String:","");
var l=strl.length;
anagram(0,l-1,strl);
storarr.sort();             //sorts the storarr alphabetically
var storlen=storarr.length;
var cai=0;
var counterarr = new Array();
strl.split("");

for(var i=0;i<l;i=i+c) {        //determines the number of times a term is repeating
    var c=1;
    for(var j=i+1;j<l;j++) {
        if(strl[i]==strl[j])
            c++;    
    }
    counterarr[cai]=c;
    cai++;
}

var yellow=1;

for(var i=0;i<counterarr.length;i++) {      //multiplies the terms of the counter array
    yellow=yellow*factorial(counterarr[i]);
}

counter=counter/yellow;
document.write("Count : " + counter + "<br />");

for(var i=0;i<storlen;i=i+yellow) {     //prints the non-flagged terms in storarr
    document.write(storarr[i] + "<br />");
}

strl.join("");

Answer 8

<pre>
<script>

var count = 0;
var duplicate = false;

function FindAllPermutations(str, index) {
    for (var i = index; i < str.length; i++) {
        var newstr;

        if (index == i) newstr = str;
            else newstr = SwapLetters(str, index, i);

        if (!duplicate) {
            count++;
            document.write(newstr + "\n");
            if (i == index) duplicate = true;
        } else if (i != index) duplicate = false;

        FindAllPermutations(newstr, index + 1);
      }
  }

function SwapLetters(str, index1, index2) {
    if (index1 == index2) return str;
    str = str.split("");
    var temp = str[index1];
    str[index1] = str[index2];
    str[index2] = temp;
    return str.join("");
}

FindAllPermutations("ABCD", 0); // will output all 24 permutations with no duplicates
document.write("Count: " + count);

</script>