Algorithm to separate items of the same type

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:

1. A’s are at least 4 apart, B’s at least 4 apart, and C’s at least 2 apart
2. A’s at least 3 apart, B’s at least 3 apart, and C’s at least 4 apart

You need a well-defined measure of “good” (or, more accurately, “better”). I’ll assume for now that the measure is: maximize the minimum distance between any two of the same item.

Here’s an algorithm that achieves a minimum distance of ceiling(N/n(A)) where N is the total number of items and n(A) is the number of items of instance A, assuming that A is the most numerous.

• Order the item types A1, A2, ... , Ak where n(Ai) >= n(A{i+1}).
• Initialize the list L to be empty.
• For j from k to 1, distribute items of type Ak as uniformly as possible in L.

Example: Given the distribution in the question, the algorithm produces:

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