[Haskell-beginners] Partition a number or optimize

[Ertugrul Söylemez]

> Now i wrote a crude parts function to do this
>
> nparts 0 = []
> nparts n = [n] : [x:xs | x <- [1..n`div`2], xs <- nparts(n - x)]
>
> which is a bad bad example of recursion coz it’s slow!

It's not the recursion that makes it slow, but its asymptotic runtime,
which is O(2^n).  This one might run slightly faster:

    intParts :: Integer -> [[Integer]]
    intParts n = do
        x <- [1..n]
        let r = n - x
        if r > 0
          then map (x :) (intParts (n - x))
          else [[x]]

Verify that this function takes a lot of time for an argument as small
as 20, because it finds 2^19 partitionings.  You need to eliminate
candidates early.  For example if you know that you only need
2-partitionings, then there is no need at all for the recursion and you
can get away with O(n).  Alternatively you can eliminate certain
partitions by changing the third line.

    x <- [2..n]

This finds partitions of at least 2.  Or introduce a stop-early
condition.


Greets,
Ertugrul
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150427/e5ae1589/attachment.sig>