Instead of minimize the linear difference of partition, we might want to minimize the standard deviation, or basically any convex function, and still do it in the same time bound.
One can reduce this problem to find a k-edge path of minimum weight on a complete DAG. The naive algorithm will run in O(kn^2), but we can improve the running time to O(kn) by realize the weight on this DAG has the Monge property. This is very practical to implement.
I posed it as a problem on daily haskell exercise http://dailyhaskellexercise.tumblr.com/post/58060450750/the-....
In this application, k is very large. n is just a constant multiple of k. We can use a theoretically better algorithm that takes n2^O(sqrt(log n loglog n)) time. (this is almost O(n^(3/2))). I doubt it will ever be implemented with speed comparible to the O(kn) solution. See http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/sdarticle_...
I shall post a solution tomorrow since I'm currently touring NYC with my gf...
Edit: after reading the problem statement, yes, I can.
I imagine the algorithm to cater to both is much harder, because you wouldn't be able to treat each row in isolation, can it actually be solved to a good standard?
If you want to avoid the bias you have to try something else: e.g. reorder the images, overlap them, convert to square format…
I haven't touched this code in almost 6 years now, so don't expect too much :)
For each row, it tries 3-10 images, sums their aspect ratios, divides the total row width by the sum to get a candidate height, then picks the height that's closest to the average of the existing rows.
To make things look a bit nicer, it rejects candidate rows with the same number of images as the last row.
I might release the code on Github if I can make it modular enough. Currently it depends on jQuery but that's really only for element creation.
¹ http://mattandsophiegetmarried.com, I'm the guy with the waistcoat, purple cravat and massive grin.
Congrats on the wedding though.
The photos didn't appear correctly aligned though -- some 70-100px "whitespace" at the right edge of the screen. And resizing the screen removed all content.
edit: I'm using Firefox v22 on Xubuntu.
However if you then resize the window it seems to make all the images disappear (?)
I might be wrong here but I think the background is just the picture, although scaled and has got many filters on it.
What they got right this time is adding the shadow around the image making it easy to distinguish from the background, and blurring it so heavily that none of the detail is distracting.
Very nicely done.
In the past month or two, though, it's gotten damn responsive (for me at least). Give it another shot if you haven't used it recently.
Still, looks nice.
It seems more a marketing ploy to get attention to the great service chromatic.io is providing?
Actually, Chromatic tries to read the EXIF "DateTimeOriginal" information to sort the photos and falls back to the "LastModifiedDate" if the former doesn't work.
It's a good start, but when the window is shrunk, the result isn't as impressive.
The inability to read left to right on columnar data makes this really hard.
This particular algorithm seems to mix up the order of the photos in order to best fit them on a line, so it can hardly be said to show chronological order.
Question: will you ever implement profiles or permanent galleries?
FF 22 on Windows 8
Just to add some negativeness to the generaly positive comments here.
Doesn't really seem like a huge issue since there are multiple ways to accomplish the objective, though I suppose a small "X" could be added if you wanted a visual cue.
I've done stuff like this in the past, if you want something that works: https://github.com/ionelmc/jquery-gp-gallery