Uniform integer divider

Question

Hi, The problem looks like this, You have to draw N px width line as a M uniform dashes.

If for example N=13 and M=5 you our dash will have 2 px width and we will have 3 px error.

We can do better, we can draw dashes with following widths: 3, 3, 3, 2, 2 . But we can do even better the dashes can have following widths: 3, 2, 3, 2, 3 .

If I have a list a = ( 3, 3, 3, 2, 2 ) how can I find such list that the distance 'D' between all pairs in the list will be maximum?

In this example D(a) = 0 + 0 + 1 + 0 = 1. For list b = ( 3, 2, 3, 2, 3 ), D(b) = 1+1+1+1 = 4.

What is the fastest/simplest method?

Answer 1

Something inspired by Bresenham's algorithm should do the trick. Believe me, you don't want to maximize D over all permutations of your set. This problem is overly complex (complexity is O(n!), so unless n is very small, this won't work)

Answer 2

The simplest method I know of ? Using floating point numbers...

In Python:

def pace(D,M): return [round(float(D) / M * i) for i in range(1,M+1)]

I have already seen this somewhere here I think.