Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Algorithm to fit photos into spaces on pages

by blokhead (Monsignor)
on Nov 15, 2005 at 18:52 UTC ( #508728=note: print w/ replies, xml ) Need Help??


in reply to Algorithm to fit photos into spaces on pages

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....

blokhead


Comment on Re: Algorithm to fit photos into spaces on pages
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://508728]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (19)
As of 2015-07-30 20:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (273 votes), past polls