Recursively Print All Permutations of a String (Javascript)

Recursively print all permutations of a string (Javascript)

Let's write a function that returns all permutations of a string as an array. As you don't want any global variables, returning the permutations is crucial.

  function permut(string) {
  if (string.length < 2) return string; // This is our break condition

  var permutations = []; // This array will hold our permutations
  for (var i = 0; i < string.length; i++) {
    var char = string[i];

    // Cause we don't want any duplicates:
    if (string.indexOf(char) != i) // if char was used already
      continue; // skip it this time

    var remainingString = string.slice(0, i) + string.slice(i + 1, string.length); //Note: you can concat Strings via '+' in JS

    for (var subPermutation of permut(remainingString))
      permutations.push(char + subPermutation)
  }
  return permutations;
}

To print them, just iterate over the array afterwards:

 var myString = "xyz";
 permutations = permut(myString);
 for (permutation of permutations)
   print(permutation) //Use the output method of your choice

Hope I could help you with your question.

All permutations of a given string - complexity

There exists O(n!) permutations of a string of length n.

In generating each string in the permutation, you are doing O(n) operation by having a for loop of O(string.length) = O(n)

It might not be obvious why there's n!, but you are recursively calling permutation(..) function with remaining string, so the string length will be n * (n - 1) * (n - 2) * (n - 3) * ... * 1.

Thus, the time complexity of your algorithm is O(n * n!).

Other popular known solutions (swap-based, which is similar to yours, and next-permutation-based) have the same time complexity.

Finding all permutations of array elements as concatenated strings

Heap's algorithm can be used to generate all permutations (without repetitions) of array elements, you can then use those permutations with array.join("") to convert them to strings. This works for arrays of any size and any type:

Here is a quick javascript implementation:

// some global variable to store the results
var result = []

// currentSize should be invoked with the array size
function permutation(arr, currentSize) {
    if (currentSize == 1) { // recursion base-case (end)
        result.push(arr.join(""));
        return;
    }
    
    for (let i = 0; i < currentSize; i++){
        permutation(arr, currentSize - 1);
        if (currentSize % 2 == 1) {
            let temp = arr[0];
            arr[0] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        } else {
            let temp = arr[i];
            arr[i] = arr[currentSize - 1];
            arr[currentSize - 1] = temp;
        }
    }
}

let array = ["1","2","3","4"];
permutation(array, array.length);

console.log(result);
// use result here

Keep in mind that this is very computationally expensive, with complexity of O(n!).

Permutations in JavaScript?

If you notice, the code actually splits the chars into an array prior to do any permutation, so you simply remove the join and split operation

var permArr = [],  usedChars = [];
function permute(input) {  var i, ch;  for (i = 0; i < input.length; i++) {    ch = input.splice(i, 1)[0];    usedChars.push(ch);    if (input.length == 0) {      permArr.push(usedChars.slice());    }    permute(input);    input.splice(i, 0, ch);    usedChars.pop();  }  return permArr};

document.write(JSON.stringify(permute([5, 3, 7, 1])));

Generating all permutations of a given string

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction to Programming in Java)

Generating all permutations of elements in a single array

This simplistic approach uses bitmasks, so it will only work for a relatively small number of words.

var array = ["apple", "banana", "lemon", "mango"];
var result = [];for (var n = 0; n < 1 << array.length; n++) { var i, a = []; for (i = 0; i < array.length; i++) if ((n & (1 << i)) == 0) a.push(array[i]); for (i = 0; i < array.length; i++) if ((n & (1 << i)) != 0) a.push("not " + array[i]); result.push(a.join(" "));}
console.dir(result.join("\n"));

Permutations without recursive function call

Here is a simple solution to compute the nth permutation of a string:

function string_nth_permutation(str, n) {
    var len = str.length, i, f, res;

    for (f = i = 1; i <= len; i++)
        f *= i;

    if (n >= 0 && n < f) {
        for (res = ""; len > 0; len--) {
            f /= len;
            i = Math.floor(n / f);
            n %= f;
            res += str.charAt(i);
            str = str.substring(0, i) + str.substring(i + 1);
        }
    }
    return res;
}

The algorithm follows these simple steps:

• first compute f = len!, there are factorial(len) total permutations of a set of len different elements.
• as the first element, divide the permutation number by (len-1)! and chose the element at the resulting offset. There are (len-1)! different permutations that have any given element as their first element.
• remove the chosen element from the set and use the remainder of the division as the permutation number to keep going.
• perform these steps with the rest of the set, whose length is reduced by one.

This algorithm is very simple and has interesting properties:

• It computes the n-th permutation directly.
• If the set is ordered, the permutations are generated in lexicographical order.
• It works even if set elements cannot be compared to one another, such as objects, arrays, functions...
• Permutation number 0 is the set in the order given.
• Permutation number factorial(a.length)-1 is the last one: the set a in reverse order.
• Permutations outside this range are returned as undefined.

It can easily be converted to handle a set stored as an array:

function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}

clarification:

• f is first computed as factorial(len).
• For each step, f is divided by len, giving exacty the previous factorial.
• n divided by this new value of f gives the slot number among the len slots that have the same initial element. Javascript does not have integral division, we could use (n / f) ... 0) to convert the result of the division to its integral part but it introduces a limitation to sets of 12 elements. Math.floor(n / f) allows for sets of up to 18 elements. We could also use (n - n % f) / f, probably more efficient too.
• n must be reduced to the permutation number within this slot, that is the remainder of the division n / f.

We could use i differently in the second loop, storing the division remainder, avoiding Math.floor() and the extra % operator. Here is an alternative for this loop that may be even less readable:

        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            i = n % (f /= len);
            res.push(b.splice((n - i) / f, 1)[0]);
            n = i;
        }

---

Related Topics