Pathologically Eclectic Rubbish Lister  
PerlMonks 
Re: Algorithm to fit photos into spaces on pagesby blokhead (Monsignor) 
on Nov 15, 2005 at 18:52 UTC ( #508728=note: print w/replies, xml )  Need Help?? 
I'm still not sure about an efficient (polynomialtime) algorithm for your original question ( P.S. This does beg the questions of how can one determine if a selection of layouts could deal with every possible selection of photos,I'm in a formallanguages frame of mind right now, and this question is easily answerable using regular languages & automata. If your layouts are, say, {pll,lp,pp}, then the possible photo sequences you can represent are exactly those sequences which match /^(plllppp)*$/. If you want to know whether this allows you to get all possible photo sequences, then you are asking whether /^(plllppp)*$/ is equivalent to /^[pl]*$/. This is called the "regex universality" problem (does a given regex match all strings?), and it is PSPACEcomplete in the general case. But for reasonable sized examples, you can check this by building a DFA from the regex, complementing it, and checking to see if it accepts any strings. I even happen to know of an upcoming Perl project that would make these regular expression & automata operations very easy (which happens to be why I'm in the formallanguage frame of mind to begin with) {nudge nudge wink wink}. and similarly, what is the smallest possible selection of layouts that are similarly "complete"? I don't need to know the answer, but it is intriguing!Well, the smallest is {p,l} of course ;) To make the problem more interesting, if you are given a set of layouts (say, {pll,lp,pp} again), can you make this set smaller without losing expressivity? What you can do is calculate the minimal generating set of /^(plllppp)*$/. This can also be done through some manipulation of the automata for the associated language.
Of course, this only address the question of whether or not you can represent a sequence of photos in a given basis of layouts. It does not address the optimality of the layouts according to your criteria ( blokhead
In Section
Seekers of Perl Wisdom

