Hello
true but no summand may appear twice, and only numbers 1 to 9 may be used.
For example, (10, 3) yields
Array[Int16[2,3,5],Int16[1,4,5],Int16[1,3,6],Int16[1,2,7]]
Regards,
-Patrick
On Monday, October 19, 2015 at 12:51:49 PM UTC+2, Jason Merrill wrote:
>
> 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
>>
>
