Algorithm to order array

Question

Take for example this input array:

[2,7,1,4,9]

For this input, I need to produce an array of total 23 elements which contains two elements of 2, seven elements of 7, one element of 1, four elements of 4 and nine elements of 9. Example of output array:

[2,2,7,7,7,7,7,7,7,1,4,4,4,4,9,...]

However, this array needs to be ordered in the way that minimizes the number of same elements appearing next to each other. The example of such array would be something like this:

[7,2,9,4,9,1,7,...]

The primary goal is to minimize the number of the same adjacent elements.

Secondary goal is to distribute elements unbiased across resulting array if possible.

Any pseudo code or C#, java, ... would be helpful.

Answer 1

This can be seen as a traveling salesman problem:

• each element is a node of your graph, labled with it's number
• there are edges between each pair of nodes
• the "distance" of getting from one node to another is 0 if the lables have different numbers, and 1 if the numbers are equal

Now you are looking for a route through this graph minimizing the total distance. Google for

           traveling salesman <your_favorite_programming_language>

and you will find tons of example implementations with heuristic or brute-force approaches.

Answer 2

The resulting array only really needs to separate the largest elements, any smaller element will be trivially separated by the larger elements. So if we have 9, 7, 4, and 2:

999999999
9797979797979799
97 97 97 97 97 97 97 94 9

And now it's easy, because there are always enough spaces to insert smaller numbers (starting at the left)

974 974 974 972 972 97 97 94 9