Algorithm to separate items of the same type

Question

I have a list of elements, each one identified with a type, I need to reorder the list to maximize the minimum distance between elements of the same type.

The set is small (10 to 30 items), so performance is not really important.

There's no limit about the quantity of items per type or quantity of types, the data can be considered random.

For example, if I have a list of:

• 5 items of A
• 3 items of B
• 2 items of C
• 2 items of D
• 1 item of E
• 1 item of F

I would like to produce something like: A, B, C, A, D, F, B, A, E, C, A, D, B, A

• A has at least 2 items between occurences
• B has at least 4 items between occurences
• C has 6 items between occurences
• D has 6 items between occurences

Is there an algorithm to achieve this?

-Update-

After exchanging some comments, I came to a definition of a secondary goal:

• main goal: maximize the minimum distance between elements of the same type, considering only the type(s) with less distance.
• secondary goal: maximize the minimum distance between elements on every type. IE: if a combination increases the minimum distance of a certain type without decreasing other, then choose it.

-Update 2-

About the answers. There were a lot of useful answers, although none is a solution for both goals, specially the second one which is tricky.

Some thoughts about the answers:

• PengOne: Sounds good, although it doesn't provide a concrete implementation, and not always leads to the best result according to the second goal.
• Evgeny Kluev: Provides a concrete implementation to the main goal, but it doesn't lead to the best result according to the secondary goal.
• tobias_k: I liked the random approach, it doesn't always lead to the best result, but it's a good approximation and cost effective.

I tried a combination of Evgeny Kluev, backtracking, and tobias_k formula, but it needed too much time to get the result.

Finally, at least for my problem, I considered tobias_k to be the most adequate algorithm, for its simplicity and good results in a timely fashion. Probably, it could be improved using Simulated annealing.

Answer 1

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