Designing a different kind of tag cloud.

Question

Rather than having a bunch of links that are all different sizes, I want all of my tags to be the same size. However, my goal is to minimize the amount of space required to make the cloud, aka minimizing the number of lines used.

Take this example:

Looks like any normal tag cloud. However, look at all that extra space around the 'roughdiamond' tag, which could be filled in by other tags like 'stone' down near the bottom, which could effectively eliminate an entire extra line from the cloud.

How would I go about getting the words to fill in whatever space possible above them before starting a new line? I'm not talking about reorganizing them to find the absolute minimum number of lines required. If I was going through the list in the image, 'pendant', 'howlite', and 'igrice' would go to line 1 filling it up, 'roughdiamond' would go to line 2 because line 1 is full, 'tourmaline' would go to line 3 because it can't fit on lines 1 or 2, same with 'emberald', but 'pearl' would go to line 2 because it can fit there since there is extra space. I figure there would probably be some way of doing this in CSS that would simply cause the links to collapse into any fillable space it can fit in to.

Answer 1

You could try putting them in a div that is the exact height of the text, then floating them all over the place?

Answer 2

I doubt this is possible in CSS since this requires specific computations to rearrange the words optimally.

The general problem of taking up the least amount of lines possible is similar to the knapsack problem. I don't think the problem you mention is much easier.

Why not minimize the line count if possible? If you don't have a very large amount of words you could solve a special case of this problem in PHP and actually minimize the number of lines.

The problem you are actually looking to tackle is the 2 dimensional bin packing problem with bins of equal size and items of variable size.

As mentioned in this answer to a question about bin packing, sorting your items from largest to smallest and then fitting smaller words in between the large ones will usually result in a fairly good approximation. You will have to try it out with the types of words you'll be using to find out whether this will work for you (his approach may result in many small words grouped at the bottom of your cloud).

Answer 3

This is not an optimal solution but will probably (most of the time) be way better than a random one and way faster than a optimal one: display each tag by string length width in descending order.

This will give you a arrangement that will be at max, 14% worse than the optimal solution.

EDIT: Also works if you sort tags by strlen width in ascending order.