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


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:


However, the optimum is


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]