permutations in Javascript

Question

I'm trying to write a function in Javascript that can return the number of permutations, and also show all the permutations of a string (suppose that non of the character is repeated) using recursive methods. I've seen a lot using for loop, but is there a way that I can obtain the same outcome without using it?

For the number of permutations, here is my attempt without using for loop

var permutation = function (s) {

    var fac = function (t) {
        if (t === 0) return 1;
        return t*fac(t-1);
    };

    return fac(s.length);
};

It works well, but I don't know how to continue with the list of permutations. Thanks for the help!

I think it's wise to avoid expanding the stack with each call of the function `fac`. It can lead to stackoverflow (no pun intended). — Nahiyan, Apr 02 '20 at 05:43
recursive programming is okay, but i think a solution using a while or a for loop would be better — John Krakov, Apr 02 '20 at 05:44
Recursion is okay, but recursing with an ever-increasing stack isn't. — Nahiyan, Apr 02 '20 at 05:46
You can look at the permutation function in [*Javascript Permutations magic trick*](https://stackoverflow.com/questions/42071199/javascript-permutations-magic-trick) and replace the *for* loop with *forEach* over the array of characters. — RobG, Apr 02 '20 at 07:01
Does this answer your question? [understanding better a solution for finding permutations of a string - javascript](https://stackoverflow.com/questions/53306200/understanding-better-a-solution-for-finding-permutations-of-a-string-javascrip) — Leo, Apr 02 '20 at 07:22
https://stackoverflow.com/questions/53306200/understanding-better-a-solution-for-finding-permutations-of-a-string-javascrip — Leo, Apr 02 '20 at 07:22
your permutation func is wrong, if `s = 'aaaabbccc'`, you will have less permutations than `frac(s.length)`, the idea is you need something like `const count = { a:4, b:2, c:3 };` and `result = 9! / (4!*2!*3!)` — Foxeye.Rinx, Apr 02 '20 at 08:12
@Foxeye.Rinx—the OP says "*suppose that none of the character is repeated*". — RobG, Apr 02 '20 at 13:13

QuentinUK · Answer 1 · 2020-05-17T23:57:11.070

Here's a function to do permutations in JavaScript without loops.

Use it like so:

let stra = [..."string"].sort(); // first sort your items in an array

while(nextPermutation(stra)) console.log(stra); // keep going until false

function nextPermutation(array, first = 0, last = array.length-1) {
  if(first>=last){
    return false;
  }
  let i = last;
  function reverse(i, j){
    if(i>=j) return;
    [array[j], array[i]] = [array[i], array[j]];
    reverse(++i, --j);
  }
  return (function _(){
    const i1 = i;
    if(array[--i]<array[i1]){
      let i2 = last+1;
      (function decrement(){
        if(array[i] >= array[--i2]) decrement();
      })();
      [array[i], array[i2]] = [array[i2], array[i]];
      reverse(i1, last);
      return true;
    }
    if(i===first){
      reverse(first, last);
      return false;
    }
    return _();
  })();
}

Which line has the `for` loop ? As for the `while` loop, that is only in the example usage of the `nextPermutation` function. There is no loop in the `nextPermutation` function by the way. — QuentinUK, Sep 22 '22 at 00:32

Scott Sauyet · Answer 2 · 2020-04-02T20:21:32.327

This version uses a fairly simple recursion:

const without = (n) => (xs) => 
  [... xs .slice (0, n), ... xs .slice (n + 1)]

const permutations = (xs) =>
  xs .length == 0
    ? []
  : xs .length == 1
    ? [[xs[0]]]
  : // else
    xs .flatMap ((x, i) => permutations (without (i) (xs)) .map (p => [x, ...p]))

const stringPermutations = (s) => { 
  return permutations (s .split ('')) .map (ss => ss .join (''))
}


console .log (
  stringPermutations ('abcd')
)

.as-console-wrapper {min-height: 100% !important; top: 0}

There is a helper function, without, which returns a copy of an array without the given index. For instance, without (2) (['a', 'b', 'c', 'd', 'e', 'f']) yields ['a', 'b', 'd', 'e', 'f']. This is only used once inside our main function and could be easily inlined, but I find it easier to read as is.

stringPermutations merely changes the string into an array of single-character strings, calls permutations and then joins the resulting arrays back into strings.

The important part is permutations. It has two base cases: when the input array is empty, it returns an empty array. When it has only a single value, it returns an array containing an array containing that value. In all other cases, it selects each element in turn for the first element, removing it from the list and recursively calling permutations with the remaining list for the subsequent positions.

couldn't let this answer go without up-votes... beautiful work, Scott — Mulan, Apr 02 '20 at 20:01
Thank, umm @Thankyou. Good to see you back around these parts. I was quite surprised not to easily find a recursive JS permutations answer already. But I didn't look too hard. — Scott Sauyet, Apr 02 '20 at 20:18

permutations in Javascript

2 Answers2

Linked