Partition a list!

Question

In this challenge, you need to partition a list, where partitions have a max size, a min size, and a preferred size. I'll be using the notation (min,pref,max) to indicate the sizes in this challenge.

For those unfamiliar with partitioning, the following list has been partitioned into parts of 3:
[0..9] -> [[0,1,2],[3,4,5],[6,7,8]]

When the list is not evenly divisible, you need the partitions to be as close to the preferred size as possible: [0..10], (2,4,5) -> [[0,1,2,3],[4,5,6],[7,8,9]]. This partitioning is preferable to [[0,1,2,3],[4,5,6,7],[8,9]], even though the latter has more of the preferred length. Formally, we need to minimize the sum of (partitionLength-preferredSize)^2 for each partition.

The order of the partition lengths does not matter: For [0..5], (2,3,3), either [[0,1,2],[3,4]] or [[0,1],[2,3,4]] works. If no partition is possible, return an empty array: [0..7], (4,4,5) -> [].

You can assume that 1<=min<=pref<=max, and that the array passed to you is a non-empty array of integers. The array will always be the first argument. You can accept min, max, and pref in any order and as a tuple or as separate arguments.

Your program must run under a couple of seconds. Basically, iterating through every possible partition size within the bounds is not allowed.

Test cases:

[1], (1,3,4)         -> [[1]]
[100], (1,2,3)       -> [[100]]
[1,2], (1,1,2)       -> [[1],[2]]
[1,2], (1,2,2)       -> [[1,2]]
[1,2], (1,3,3)       -> [[1,2]]
[1,2,3], (1,2,3)     -> [[1,2],[3]] or [[1,2,3]]
[1,2,3,4], (1,3,4)   -> [[1,2,3,4]]
[1,2,3,4,5], (3,3,4) -> []
[1,2,3,4,5], (2,2,2) -> []
[1,2,3,4,5], (3,3,5) -> [[1,2,3,4,5]]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49], (2,6,6) -> [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24],[25,26,27,28,29],[30,31,32,33,34],[35,36,37,38,39],[40,41,42,43,44],[45,46,47,48,49]]

This is a code-golf, so aim for as few bytes as possible in your favorite language!

Answer 1

Haskell, 152

_%0=[]
s%k|(a,b)<-splitAt(div(z s)k)s=a:b%(k-1)
z=length
f s n p x=snd$minimum$(z s*p^2,[]):[(sum[(z x-p)^2|x<-s%k],s%k)|k<-[-div(-z s)x..div(z s)n]]

In any partition, if there are two lists which have lengths that differ by two or more, it will always be beneficial to shrink the bigger list and enlarge the smaller list. therefore, we only need to consider partitions with only two list sizes, which simplifies the computation.

the program then runs on all the possible amounts of lists in the partition. given the amount of lists in the partition, the score is uniquely determined. the program computes a fitting partition, and its score.

then it finds the overall minimum, and returns it.

Usage: input like f [1,2,3,4,5] 1 3 4 (f is the function that solves the challenge)

Although it is possible to computing the best option completely numerically and only then partitioning the list accordingly, it took too many bytes. however, my last version of this approach is:

_%0=[]
s%k|(a,b)<-splitAt(div(length s)k)s=a:b%(k-1)
f s n p x|l<-length s=(s%)$snd$minimum$(l*p^2,0):[(k*j^2+mod l k*(1-2*j),k)|k<-[1..div l n],k*x>=l,j<-[p-div l k]]

Answer 2

CJam, 70

q~:S;_,[0L]a{_S2=e<),S0=>f{[__S1=-_*\]@@-j.+}[esL]a+:e<}j1={/(\e_}/;]p

Try it online

The code finds an optimal sequence of partition sizes based on the list size, using dynamic programming (via memoized recursion), then goes ahead and partitions the list.