If I'm reading correctly, it looks like decompose is intended to give all
partitions of val into num summands.
Julia actually has this function as part of Base:
julia> collect(Vector{Int}, partitions(10, 3))
8-element Array{Array{Int64,1},1}:
[8,1,1]
[7,2,1]
[6,3,1]
[5,4,1]
[6,2,2]
[5,3,2]
[4,4,2]
[4,3,3]
partitions actually returns an iterator, so if you can process the
partitions 1-by-1, you don't actually have to store them all at once.
You can see how it's implemented here:
https://github.com/JuliaLang/julia/blob/8396c9f5c9a3483e35f5e1f9ef63d4c6b3f45b04/base/combinatorics.jl#L307-L369
On Sunday, October 18, 2015 at 9:49:45 PM UTC-4, Patrick Useldinger wrote:
>
> Hi everybody,
>
> I am currently benchmarking languages to write a kakuro solver in. I am
> not really familiar with Julia but ported the small algorithm I had written
> in Lisp and PyPy to Julia nevertheless. Unfortunately Julia's performance
> is really bad and I'm reaching out to the community to find out whether
> it's due to my coding or not.
>
> Here's the code in Julia:
>
> function decompose(val, num)
> function sub(num, tot, res, pos, allres)
> if val==tot && num==0
> union(allres, res)
> elseif tot<val && num>0 && !isempty(pos)
> sub(num-1, tot+pos[1], union(copy(res),pos[1]), pos[2:end], sub(num,
> tot, res, pos[2:end], allres))
> else
> allres
> end
> end
> sub(num, 0, Int16[], 1:(max(num, 10))-1, Array[])
> end
>
> for i in 1:45
> for j in 2:20
> res = decompose(i, j)
> end
> end
>
> It takes roughly 13.4 seconds on my computer.
>
> The equivalent Python code
>
> def decompose(val, num):
> def sub(num, tot, res, pos, allres):
> if tot == val and num == 0:
> return allres+res
> elif tot < val and num != 0 and pos:
> return sub(num-1, tot+pos[0], res+[pos[0]], pos[1:], sub(num,
> tot, res, pos[1:], allres))
> else:
> return allres
> return sub(num, 0, [], range(1, max(num, 10)), [])
>
>
> if __name__ == "__main__":
> for i in range(1, 46):
> for j in range(2,21):
> res = decompose(i,j)
>
> is 1.4 seconds and the Lisp
>
> defun decompose (val num)
> (labels ((sub (num tot res pos allres)
> (cond
> ((and (= tot val) (zerop num)) (cons (reverse res) allres))
> ((and (< tot val) (not (zerop num)) (not (null pos)))
> (sub (1- num) (+ tot (car pos)) (cons (car pos) res) (cdr
> pos)
> (sub num tot res (cdr pos) allres)))
> (t allres))))
> (reverse (sub num 0 nil (loop for i from 1 below (max num 10) collect
> i) nil))))
>
> (time
> (loop for val from 1 below 46 do
> (loop for num from 2 below 21 do
> (let ((res (decompose val num)))))))
>
> is 0.5 seconds.
>
> Any hints to make the Julia code perform better?
>
> Regards,
> -Patrick
>
