integer_partitions might be slower than it needs to be

[bovine3dom]

Hi,

I forgot to check whether anyone had implemented integer partitions in Julia and so implemented my own using an adaptation of http://jeromekelleher.net/generating-integer-partitions.html. For me, it's a lot quicker than your implementation here - https://github.com/JuliaMath/Combinatorics.jl/blob/a748259d08a360e7033880603cd089e5ea0d1a68/src/partitions.jl#L393

I haven't yet wrapped my head around iterators, and I needed all the partitions, so I stripped all that functionality out.

import Combinatorics
function partitions(n::Integer)
    a = zeros(Integer,n+1)
    k = 1
    y = n - 1
    ans = []
    while k != 0
        x = a[k] + 1
        k -= 1
        while 2x ≤ y
            a[k+1] = x
            y -= x
            k += 1
        end
        l = k + 1
        while x ≤ y
            a[k+1] = x
            a[l+1] = y
            push!(ans,a[1:k+2])
            x += 1
            y -= 1
        end
        a[k+1] = x + y
        y += x - 1
        push!(ans,a[1:k+1])
    end
    return ans
end

@time a = partitions(50);
0.358846 seconds (204.25 k allocations: 41.444 MiB, 3.88% gc time)

@time b = Combinatorics.integer_partitions(50);
5.859395 seconds (54.64 M allocations: 2.037 GiB, 18.58% gc time)

If I tidy up the code and make it into an iterator, would you be interested in a pull request?

[garrison]

See also #35. Does this code also improve the speed beyond that pull request?

[bovine3dom]

I don't know. I haven't been able to work out how to get the pull request working in Julia, so I cannot test it.

It seems that collect(partitions(...)) is much faster than integer_partitions(...) anyway, which I hadn't noticed. The benefits are much more minimal compared to that; I get only around a 50% speedup for big numbers (e.g. 80), and for small numbers it is slower.

I don't have time to investigate any further now - sorry!