JuliaMath / JuliaMath/Combinatorics.jl

integer_partitions might be slower than it needs to be

Open
#54 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
230
Forks
62
PR merge metrics
No merged PRs in 30d

Description

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.

``` Julia
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?

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.