Dave's Free Press: Journal
http://www.cantrell.org.uk/david/journal
violence, pornography, and rude words for the web generationen-usZ Compact tag clouds
http://www.cantrell.org.uk/david/journal/id/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.<p>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.<p>52! is roughly 8e69. That's 8 followed by 69 zeroes. 69, dude!<p>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.<p>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 :-)<p>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.<p>Use both sides of the paper. No conferring. You may begin now. 2008-05-13T23:44:09Z