I have encountered the following problem studying some practical applications of scheduling systems.
Given a set of symbol types s1...sn with associated frequencies of occurrence f1..fn, distribute the f1+...+fn symbols in a cyclic sequence such that uniformity in the distribution of each symbol type is maximized. Uniformity could be measured in several ways, a simple one would be to sum the squares of the distances (measured in intermediate symbols) of each symbol to the next symbol of the same type, for all symbol types. We would try to minimize this amount.
For example, if we have s1=a, s2=b, f1=f2=2, we would have a measure of uniformity for the sequence abab of 4 (remember that we are dealing with cyclic sequences), while for aabb we would have a measure of 8. It is easy to see that the first solution is optimal.
The approach seems simple and general enough to have been dealt with before, but I am finding it very difficult to relate it to other known problems. Does anyone have any suggestions?
Thank you very much,
Daniel.