StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First, you don't have a well-defined optimization problem yet. If you want to maximized the minimum distance between two items of the same type, that's well defined. If you want to maximize the minimum distance between two A's and between two B's and ... and between two Z's, then that's not well defined. How would you compare two solutions: </p> <ol> <li>A's are at least 4 apart, B's at least 4 apart, and C's at least 2 apart </li> <li>A's at least 3 apart, B's at least 3 apart, and C's at least 4 apart </li> </ol> <p>You need a well-defined measure of "good" (or, more accurately, "better"). I'll assume for now that the measure is: <strong><em>maximize the minimum distance between any two of the same item</em></strong>.</p> <p>Here's an algorithm that achieves a minimum distance of <code>ceiling(N/n(A))</code> where <code>N</code> is the total number of items and <code>n(A)</code> is the number of items of instance <code>A</code>, assuming that <code>A</code> is the most numerous.</p> <ul> <li>Order the item types <code>A1, A2, ... , Ak</code> where <code>n(Ai) >= n(A{i+1})</code>.</li> <li>Initialize the list <code>L</code> to be empty.</li> <li>For <code>j</code> from <code>k</code> to <code>1</code>, distribute items of type <code>Ak</code> as uniformly as possible in <code>L</code>.</li> </ul> <p>Example: Given the distribution in the question, the algorithm produces:</p> <pre><code>F E, F D, E, D, F D, C, E, D, C, F B, D, C, E, B, D, C, F, B A, B, D, A, C, E, A, B, D, A, C, F, A, B </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload