Characters set permutations with repetitions

Question

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
 })
 })
 .flatten()
 .value()
}
function solution(space, len) {
 return _.chain(
 _(len - 1).range()
 )
 .reduce(
 function(acc, next) {
 acc.push(
 multStr(
 _.last(
 acc
 ),
 space
 )
 )
 return acc
 },
 [space.split('')]
 )
 .flatten()
 .value()
}
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'
])

• elclanrs: Is the output of solution('ab', 3)? or solution('abc', 3) as expected? I'm not sure...
• kharandziuk: what do you mean?) I don't understand the question:)
• elclanrs: 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.
• kharandziuk: yep, you are right. There is a bug. I'll fix it and return to you
• kharandziuk: fixed. please check

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'
]
*/

• kharandziuk: 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
• elclanrs: @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.
• kharandziuk: do you know some nice explanation about monads?
• elclanrs: This one looks good "Functors, Applicatives, And Monads In Pictures"
• elclanrs: 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.