in reply to Algorithm to fit photos into spaces on pages
I'm still not sure about an efficient (polynomialtime) algorithm for your original question (minimizingmaximizing the number of distinct layouts used in representing a sequence of photos), but I can address your postscript:
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 (fewestmaximum number of distinct layouts used). This is where it gets a little harder....
