When greediness fails

Today I spent some time looking for cases where my greedy algorithm for finding the optimal 'spread' of a list fails.

Well, I found some! :)

This little beauty

[8, 5, 5, 5, 7, 7, 4, 4]

should return something like this

[4, 5, 7, 8, 5, 4, 7, 5]

but instead returns something like this

[5, 4, 7, 5, 8, 4, 7, 5]

which is close to optimal but not quite.

Most unfortunate.

I've spent a little bit of time tweaking the algorithm in order to try and put the list in a helpful order to begin with but nothing seems to be working just yet.

For example, consider if our current state is

[5,7,5,7,5]

which can be checked and is as good as we can get.

When we then add in a 4, the greedy algorithm places it like so:

[5,7,5,4,7,5]

However, the optimum is

[5,7,5,4,5,7]

Notice that the final 5 and 7 have flipped. This is typical of a greedy algorithm - assuming all the other elements in the list are fixed it puts the new element in the right place, overlooking the fact that there is a better solution if we mixed everything up a bit.

For now I need to have a think of what the best way to overcome this might be.

Maybe a rethink of the scoring of 'spread' is in order since both the greedy and 'optimal' solutions are actually reasonable.

[Image credit: Emily Horne]