[Haskell-beginners] Partition a number or optimize

[Animesh Saxena]

I have the following function to optimize

myfunction = max(p `div` c + p `mod` c)
Here p is an array of numbers
and c is also an array of numbers

I need to find c’s which minimize the value of my function. for example if p = [1,10000]. c = 2,8 or c = 1,9 or c=5,5
number of c is length of p which is 2 (in this case). Sum of c is given as a constraint, so for example if sum is 10, then c’s can be 2,8 or 1,9 or 5,5 or 4,6 or…..etc etc. Length of c will be equal to length of p array. Hope the problem statement is clear

In haskell terms it will be,

let my_min  p c = foldl1 max $ zipWith (\p c -> (p `div` c) + (p `mod` c)) p c
One way is to use various combinations of c using integer partitioning.

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!

*Main> nparts 5
[[5],[1,4],[1,1,3],[1,1,1,2],[1,1,1,1,1],[1,2,2],[1,2,1,1],[2,3],[2,1,2],[2,1,1,1]]

I can then filter this with length of p and get the required options of c

I can then call the function “ my_min” with this list (simple map application)

Problem is if i do 
*Main> filter (\x->length x == 2) $ nparts 100
[[1,99]

and it hangs…for a lot of time….so time constraint?

Any other approaches to this problem to make the partitions speedier. I know it’s an optimization problem…but all non linear optizers will use floats…and fail to converge…this is an integer optimizing problem.

Any ideas??



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150427/53f157cd/attachment.html>