Algorithm to fit photos into spaces on pagesby SmugX (Beadle)
|on Nov 15, 2005 at 17:15 UTC||Need Help??|
SmugX has asked for the
wisdom of the Perl Monks concerning the following question:
An interesting-sounding (to me!) problem has landed on my desk.
I have a number of photographs, each of which are either of landscape or portrait orientation. The order of these photos is important, and is for the purposes of the excercise fixed.
I also have a number of potential page layouts (or templates), each of which contain one or more spaces for photos; the spaces are either landscape or portrait in nature. (e.g. layout 1 may contain one "Landscape" ,layout 2 "Portrait then Portrait", layout 3 "Landscape then Portrait then Portrait" etc.)
I need to find a combination of page layouts that holds the photos in their correct order, which each photo fitting into a space with matching orientation.
There are a couple of additional contraints; the number of layouts that can be in the solution is fixed, because I must produce a book containing exactly X layouts. Also, I want to minimise the re-use of layouts where possible, and I definitely don't want to use the same layout consecutively unless absolutely necessary.
My first thought was this sounded like a tree-type problem, so I knocked up the following code using a simple recursive algorithm. My scoring algorithm is a little arbitrary at the moment, but should suffice for testing. (Also of note is my short-cut assumption that the score will never get better as subsequent pages are added.)
The good news is the code appears to work. However, the problem is that as more potential page layouts are added, the time taken increases vastly. I gave the program 40 possible layouts and 40 images, and ... well, let's just say it's still running. :-)
So, I now need to figure out ways to improve the speed of this program. (For the record, whilst a good solution is required, the best-possible solution isn't really necessary.)
Can anyone suggest a better methodology, either by changing my existing code, or perhaps by using one of the many Algorithm:: modules on CPAN, virtually all of which very quickly go right over my head as soon as I start to read the documentation? :-)
Any help will be greatly appreciated.
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, 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!