A greedy implementation of unsort

Today I finally moved on from playing around with measuring the 'spread' of a list and instead got down to the nitty-gritty of trying to spread out a given list.

My first (and so far, only) approach was to be greedy. Essentially, I start with nothing, then gradually add elements one at a time, with each element being placed in the position that maximises the spread of the current list.

So, for example, if I wanted to apply the method to the list [2,2,2,3,4], the algorithm proceeds as follows:

[]
[2]
[2,2]
[2,2,2]
[2,2,3,2]
[2,4,2,3,2]

Greedy algorithms are usually a nice quick way to get a reasonable approximation to the optimal solution, but they often fall foul of finding a locally optimal solution rather than the globally optimal solution.

My next little task is to do a bit of investigation to find cases where this happens as there are very likely to be some.

In terms of strategy, I'm thinking of taking a list, finding all permutations of it, finding the global optimal solution by analysing each and every permutation and then comparing the 'spread' of that solution with that obtained via the greedy algorithm.

With enough time and patience, something will likely fall out! And then there is an interesting case to experiment on, in order to find an even better algorithm that does indeed find the global optimum, ideally without enumerating all possible solutions.

[Image credit: Julie Falk]