JuliaMath / JuliaMath/Combinatorics.jl
integer_partitions might be slower than it needs to be
- 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.