Sorting a string in array, making it sparsely populated

Question

For example, say I have string like:

duck duck duck duck goose goose goose dog 

And I want it to be as sparsely populated as possible, say in this case

duck goose duck goose dog duck goose duck

What sort of algorithm would you recommend? Snippets of code or general pointers would be useful, languages welcome Python, C++ and extra kudos if you have a way to do it in bash.

Answer 1

I would sort the array by number of duplicates, starting from the most duplicated element, spread those elements as far apart as possible

in your example, duck is duplicated 4 times, so duck will be put in position n*8/4 for n from 0 to 3 inclusive.

Then put the next most repeated one (goose) in positions n*8/3 + 1 for n from 0 to 2 inclusive, If something is already placed there, just put it in the next empty spot. etc etc