Sunday, 27 September 2015

nt.number theory - Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?

Given a set of distances S, choose N unique points P on a number line such that the distances between the N points occur in S as much as possible. That is, maximize the occurence in S of the distances between the N points.



For example:



S = {2, 4}, N = 4



One answer would be P = {2, 4, 6, 8}, since the distances between the points P are 2, 2, 2, 2, 4, 4, 6. Only 6 is not in S.



or



S = {7, 13, 14, 22}
N = 4501



answer ???



I'm not looking for an exact answer (although an exact answer wouldn't hurt) but rather I am trying to avoid reinventing the wheel (fun though it may be). What mathematical tools could I use to avoid bruteforcing the possible values of P. How should how would you approach this problem?

No comments:

Post a Comment