The code bellow generates all the permutation(with repetitions) for given character set. Is there any better(simpler, more performant) way to do that?

var assert = require('chai').assert
var _ = require('underscore')

var multStr = function(left, rigth) {
  return _.chain(left).map(function(el) {
    return _(rigth).map(function(chr) {
      return el + chr

function solution(space, len) {
  return _.chain(
      _(len - 1).range()
      function(acc, next) {
          return acc

assert.deepEqual(multStr(['ab'], 'ab'), ['aba', 'abb'])
assert.deepEqual(solution('abc', 1), ['a', 'b', 'c'])
assert.deepEqual(solution('a', 2), ['a', 'aa'])
assert.deepEqual(solution('ab', 2), ['a', 'b', 'aa', 'ab', 'ba', 'bb'])
assert.deepEqual(solution('abc', 3), [ 'a', 'b', 'c',
  'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc',
  'aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc',
  'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc',
  'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc'
  • \$\begingroup\$ Is the output of solution('ab', 3)? or solution('abc', 3) as expected? I'm not sure... \$\endgroup\$
    – elclanrs
    Mar 7, 2016 at 18:37
  • \$\begingroup\$ what do you mean?) I don't understand the question:) \$\endgroup\$ Mar 7, 2016 at 21:49
  • 1
    \$\begingroup\$ If you run your code with solution('abc', 3), do you get the result you expect? I would expect the following dpaste.com/2E3NZNZ, but perhaps I'm misunderstanding. \$\endgroup\$
    – elclanrs
    Mar 7, 2016 at 22:22
  • \$\begingroup\$ yep, you are right. There is a bug. I'll fix it and return to you \$\endgroup\$ Mar 7, 2016 at 22:32
  • \$\begingroup\$ fixed. please check \$\endgroup\$ Mar 7, 2016 at 22:37

1 Answer 1


I think the code and the approach look good overall. I have just a few comments:

1) The indentation makes it a bit hard to read. A line like:

acc.push(multStr(_.last(acc), space))

Reads better than across many lines in my opinion.

2) You may consider using concat instead of push:

return acc.concat(multStr(_.last(acc), space))

You trade a bit of performance for it though as concat creates a new array.

3) The most notable problem I see with your code is that it is not very reusable. It only works for strings, while the idea and implementation certainly apply to arrays too. We can think of a string as an array of characters, so abstracting for arrays makes the code more reusable, since we can then do the string one trivially with str.split('').

This leads to the name of the function multStr; it is too specific, and hungarian notation means you are probably over-specifying its functionality, it ought to be more abstract.

Intuitively you wrote code that is more abstract than it seems. I find the Haskell equivalent to your code quite elegant and concise, almost by accident:

[1..3] >>= \n -> replicateM n "ab"

The concept at hand is very general: lists are monads.

We can replicate this in JavaScript easily with lodash. We need flatMap, and range:

var {flatMap, range} = require('lodash')

Next we can loosely translate the Haskell implementations of replicateM and sequence to build combinations:

function combinations(n, xs) {
  return flatMap(range(1, n + 1), m => replicateM(m, xs))

function replicateM(n, x) {
  return sequence(Array(n).fill(x))

function sequence(ms) {
  return ms.reduce((ma, mb) => {
    return flatMap(ma, a => mb.map(b => a.concat(b)))
  }, [[]])

Now this is already more general, we pass an array of characters and get an array of arrays of characters that represent all the possible combinations of n length.

To make it work for your case you only need to split then join:

combinations(3, 'ab'.split('')).map(cs => cs.join(''))
[ 'a', 'b',
  'aa', 'ab', 'ba', 'bb',
  'aaa', 'aab', 'aba', 'abb',
  'baa', 'bab', 'bba', 'bbb'
  • \$\begingroup\$ Nice answer! I'll try an return to you. only one note. It's much better to use something meaningful like acc, next instead of ma, mb \$\endgroup\$ Mar 9, 2016 at 8:01
  • \$\begingroup\$ @kharandziuk, I used ma as a convention for "monad of a" because sequence applies to any monad, I just narrowed it down for arrays here. But you are right, perhaps acc and next make more sense in this particular context. \$\endgroup\$
    – elclanrs
    Mar 9, 2016 at 14:58
  • \$\begingroup\$ do you know some nice explanation about monads? \$\endgroup\$ Mar 9, 2016 at 16:21
  • 1
    \$\begingroup\$ This one looks good "Functors, Applicatives, And Monads In Pictures" \$\endgroup\$
    – elclanrs
    Mar 9, 2016 at 16:37
  • 1
    \$\begingroup\$ Generally to get some intuition whenever you see this structure ma.flatMap(a => mb.map(b => f(a, b))) you have something monadic. You can see in your multStr function ma.map(a => mb.map(b => a + b)).flatten() is basically the same pattern so it tells me that it is more general than it seems. Learning some Haskell would help in any case if you want to learn about it more in-depth. \$\endgroup\$
    – elclanrs
    Mar 9, 2016 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.