Uniform integer divisor

Question

The problem is this: you have to draw the line width N px as an M-dash.

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

We can do better, we can draw a dash with the following widths: 3, 3, 3, 2, 2. But we can do even better so that the dash can have the following width: 3, 2, 3, 2, 3.

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

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

What is the fastest / easiest method?

Answer 1

The easiest way I know about? Using floating point numbers ...

In Python:

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

I already saw it somewhere here, I think.

Answer 2

Something inspired by Breshenem 's algorithm should do the trick. Believe me, you do not want to maximize D over all permutations of your set. This problem is too complicated (complexity is O (n!), Therefore, if n is very small, this will not work)