Catalan problem (Chap 2) - inefficient use of permutations

[gurvesh]

Hi. Many thanks for the book! I'm really grateful for this.

On this particular example, the following code is quite inefficient (uses >1GB memory and takes >1.5 secs for n=5) - even on the 2nd pass after compilation. It also fails (insufficient memory etc) pretty quickly as n increases.

omega = unique(permutations([zeros(Int,n);ones(Int,n)])) 

Something better would be to use the combinations function instead to get (2n,n) places, and populate them with 1s etc. The following runs easily 2 orders of magnitude faster (on the 2nd pass once compiled):

function seqToPath(seq, n)
    path = zeros(Int8, 2n)
    [path[i] = 1 for i in seq]
    return path
end

X = combinations(1:2n, n) |> collect
omega = map(s -> seqToPath(s, n), X)

This takes < 0.04s for n=5, and <5MB memory. This code finishes in <0.2s for n=10 as well.

[yoninazarathy]

Thanks for the comment. These comments are very welcomed and can be read by those that dive into the details. The book's source code does not attempt to always be the most efficient code. We agree that your suggestion is an improvement and may incorporate in future versions.