Can ES6 natively encode permutations over Set in functional paradigm?

Question

I would like to create permutations over Set(0..n) in Javascript.

I am struggling with Array methods: some of them like map return a new array that could be further modified, others like forEach does not. To encode permutations, I could do it only with enhancing Array prototype:

Object.defineProperty(Array.prototype, "chain", {
  value: function(method, arg) {
    this[method].call(this, arg);
    return this;
  }
});

Object.defineProperty(Array.prototype, "value", {
  value: value => value // to value value ;-)
});

Only then I was able to encode permutations:

let perm = (n) =>
  n==0 ? [[0]] :
  perm(n-1).reduce((acc, cur) =>
    cur.chain("forEach", (_, i) =>
      acc.chain("push", [...cur.slice(0,i), n, ...cur.slice(i)])
    ).value(acc).chain("push", [...cur,n])
  ,[])

Test:

console.log(perm(2));

So is it feasible in ES6 (without adding to Array prototype) to encode permutations over Set (or any Array-like object) in pure functional way?

I don't want to rape Javascript (like jQuery did back then) to force it some non-native paradigm, but I'd like to fully understand its potential on the functional field.

If you want a Set, why are you using an Array? You specified ES 6... — Jared Smith, May 03 '20 at 18:22
@JaredSmith because Array has much more useful methods. If there is a way to use Set here, I would love to see. — Jan Turoň, May 03 '20 at 18:25
@Bergi `chain` calls array method and returns the array object, so you can chain another method to the result. That was because I did not see that I can use `concat` for the same effect, as you nicely demonstrated in your answer. — Jan Turoň, May 04 '20 at 05:31
But still it seems it would have been easier to write `….reduce((acc, cur) => { cur.forEach((_, i) => acc.push(…)); accc.push(…); return acc; }, [])`? — Bergi, May 04 '20 at 07:02
@Bergi yes, I just wanted to keep the functional purity (i.e. without explicit return keyword). — Jan Turoň, May 04 '20 at 08:44
instead of your `chain` function, you could use comma `,` operator — revolver, Dec 15 '20 at 13:58

score 3 · Accepted Answer · answered May 03 '20 at 21:43

No ES6 needed at all. You should not use forEach or push if you want to program in a functional style - and hiding them in a chain method so that you can write expressions with useful return values doesn't help.

Instead, all you want are map and concat:

let perm = (n) =>
  n==0 ? [[0]] :
  perm(n-1).reduce((acc, cur) =>
    acc.concat(cur.map((_, i) =>
      [...cur.slice(0,i), n, ...cur.slice(i)]
    ), [[...cur,n]])
  , [])

Of course you could also replace the concat call by array spread syntax if you're inclined.

…or actually `flatMap`, like in [this solution](https://stackoverflow.com/a/30551462/1048572) — Bergi, Jul 21 '22 at 21:50

Can ES6 natively encode permutations over Set in functional paradigm?

1 Answers1