I recently started learning PHP, a language I had never caught up to but that recently became a requirement of my job.
For a start project, just to give myself something meaningful to write in it, I am writing some logic that places items into bins - some examples might include calculating all the ways you could pack N items into M boxes, to try and find the most optimum use of space in your limited set of boxes.
As part of this work, I need a way to figure out all the ways you could divide up those N items between the boxes. For example, if you have 5 things and 2 boxes, you could put all 5 in one, 4 in one and 1 in the other, etc.
In searching around I found the concept of partitions of an integer, which is all the ways you can sum that integer from other positive integers. Just what I was looking for!
But, in looking for an already-written version of this algorithm in PHP, I came up short. Maybe there are some, but I didn’t turn them up in some light searching.
I did find an implementation in Perl though, which looks nice and small and easy.
Being a complete n00b at PHP, and not having written Perl in years, the translation took me a few hours, but it is pretty straightforward:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
Same caveat as the Perl implementation - there is no error handling here. Also, I am sure I am overdoing the two checks that insure the array is not empty or null - I am still getting use to PHP’s undef, null, and checks (for example, the difference between == and ===). So I am sure some of you PHP gurus could make this shorter and cleaner using better syntax. It works though, with example usage like:
1 2 3 4 5 |
|
Hope you find this useful.