title: Get the position of points on a line segment with constraints
body: <p>I am designing a layout engine for ZenUML. One requirement (after simplification) is this:</p>
  <ol>
  <li>There a line segment;</li>
  <li>There are n (n &lt; 100, it can be reduced to n &lt; 30 if that makes difference in performance) points on this line segment, the order is fixed; (e.g. P1 ~ Pn)</li>
  <li>There are known minimum distances between <strong>some</strong> points; (e.g. m_d(P2,P4)=500)</li>
  <li>The length of the line segment should be as small as possible;</li>
  <li>(nice to have) The gaps between neighbour points should be as even as possible (measured by standard deviation^, and must not violate 1~4).</li>
  <li>(newly added) it must give result in no longer than 1s for 30 points in worst case (more or less constraints).</li>
  </ol>
  <p>^ <code>standard deviation</code> is used as a best alternative that I can precisely describe with my limited math knowledge. However as Roman and David pointed out, there is more appealing result in some cases that does not satisfy lowest <code>standard deviation</code>. See <a href="https://stackoverflow.com/questions/71041722/get-the-position-of-points-on-a-line-segment-with-constraints?noredirect=1#comment125673232_71084118">this comment</a></p>
  <blockquote>
  <p>A sister questions is asked at <a href="https://math.stackexchange.com/q/4377433">https://math.stackexchange.com/q/4377433</a>. It is the same problem described with math language (matrix).</p>
  </blockquote>
  <p>For example, for a line segment that has 4 points on it (P1 ~ P4).</p>
  <p>m_d(P1, P3) = 200, m_d(P1, P4) = 900.</p>
  <ul>
  <li>a. One solution would be P1 = 0, P2 = 0, P3 = 200, P4 = 900.</li>
  <li>b. A better solution would be P1 = 0, P2 = 100, P3 = 200, P4 = 900. (put P3 at the middle)</li>
  <li>c. A even better solution would be P1 = 0, P2 = 300, P3 = 600, P4 = 900. (evenly distribute P2 and P3).</li>
  </ul>
  <p>Some background of this problem. Have a look at the following diagram.</p>
  <ul>
  <li>We need to create a layout for all the lifelines (vertical lines). #1, #2</li>
  <li>The gap between those line are decided by the length of messages. #3</li>
  <li>We need to make sure the total width of the diagram is small (to save space when there are many participants). #4</li>
  <li>In this diagram, B should be moved to closer to C. #5
  <a href="https://i.stack.imgur.com/oenMM.png" rel="noreferrer"><img src="https://i.stack.imgur.com/oenMM.png" alt="enter image description here" /></a></li>
  </ul>
  <p>I have implemented the following which satisfies constraints #1~#4. Can some please help with constraint #5? It can be partially met (like b in the example) or fully met (like c in the example). We can use <code>standard deviation</code> to measure the quality of the solution.
  <strong>Updated</strong>: thanks to Roman Svistunov, the base implementation to get non-optimal position is dramatically simplified.</p>
  <pre><code>// Known minimum distance is stored in a matrix
  // e.g.
  //    m = [
  //      [0, 100, 0, 900],
  //      [0, 0,   0, 0],
  //      [0, 0,   0, 0],
  //      [0, 0,   0, 0],
  //    ]
  
  let f = function (n: number, m: Array&lt;Array&lt;number&gt;&gt;): number {
    let array = Array(n).fill(0);
    for (let i = 0; i &lt; n; i++) {
      array[i] = f(i, m) + m[i][n];
    }
    return Math.max(0, ...array);
  }
  </code></pre>