I'm still not sure about an efficient (polynomial-time) 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 formal-languages 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 /^(pll|lp|pp)*$/.
If you want to know whether this allows you to get all possible photo sequences, then you are asking whether /^(pll|lp|pp)*$/ is equivalent to /^[pl]*$/. This is called the "regex universality" problem (does a given regex match all strings?), and it is PSPACE-complete 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 formal-language 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 /^(pll|lp|pp)*$/. 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....
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Outside of code tags, you may need to use entities for some characters:
| |
For: |
|
Use: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
|
|
