Dave's Free Press: Journal

violence, pornography, and rude words for the web generation


Recent posts


Recently commented posts


Journals what I read

geeky politics rant silly religion meta music perl weird drinking culture london language transport sport olympics hacking media maths web photography etiquette spam amazon film bastards books bryar holidays palm telecoms cars travel yapc bbc clothes rsnapshot phone whisky security home radio lolcats deafness environment curry art work privacy iphone linux unix go business engineering kindle gps economics latin anglo-saxon money bramble cars environment electronics
Tue, 13 May 2008

Compact tag clouds

I've decided that using different sized text for the tag cloud works better than using different colours, but it has the drawback of eating a lot of screen space. I need to find an algorithm to pack the text in more efficiently so that it doesn't waste so much vertical space.

Actually, I already have an algorithm to do it in my head. Unfortunately it's, umm, rather inefficient. In fact I think it's O(N!) which would be fine if I only had 10 tags, but I have 52 so far, and am still occasionally adding tags.

52! is roughly 8e69. That's 8 followed by 69 zeroes. 69, dude!

Of course, this is a variant on the rectangular packing problem, which is itself a variant of the knapsack problem, which is NP-complete, so I'm going to have to come up with a heuristic that will return a reasonable (but not optimal) solution quickly.

I've decided that the best heuristic is to ask for pointers to code that other people have written that will do the job for me :-)

My constraints are that I need to fit an arbitrary number of rectangles of arbitrary size into a rectangle of fixed width but whose height can vary as necessary, with minimum wasted space. And I'd prefer a perl or javascript solution.

Use both sides of the paper. No conferring. You may begin now.

Posted at 23:44 by David Cantrell
keywords: geeky | meta
Permalink | 0 Comments

Sorry, this post is too old for you to comment on it.