algorithm - fitting n variable height images into 3 (similar length) column layout -
i'm looking make 3-column layout similar of piccsy.com. given number of images of same width varying height, algorithm order them difference in column lengths minimal? ideally in python or javascript...
thanks lot in advance!
martin
how many images?
if limit maximum page size, , have value minimum picture height, can calculate maximum number of images per page. need when evaluating solution.
i think there 27 pictures on link gave.
the following uses first_fit algorithm mentioned robin green earlier improves on greedy swapping.
the swapping routine finds column furthest away average column height systematically looks swap between 1 of pictures , first picture in column minimizes maximum deviation average.
i used random sample of 30 pictures heights in range 5 50 'units'. convergenge swift in case , improved on first_fit algorithm.
the code (python 3.2:
def first_fit(items, bincount=3): items = sorted(items, reverse=1) # new - improves first fit. bins = [[] c in range(bincount)] binsizes = [0] * bincount item in items: minbinindex = binsizes.index(min(binsizes)) bins[minbinindex].append(item) binsizes[minbinindex] += item average = sum(binsizes) / float(bincount) maxdeviation = max(abs(average - bs) bs in binsizes) return bins, binsizes, average, maxdeviation def swap1(columns, colsize, average, margin=0): 'see if can swap smooth heights' colcount = len(columns) maxdeviation, i_a = max((abs(average - cs), i) i,cs in enumerate(colsize)) col_a = columns[i_a] pic_a in set(col_a): # use set if same height once i_b, col_b in enumerate(columns): if i_a != i_b: # not same column pic_b in set(col_b): if (abs(pic_a - pic_b) > margin): # not same heights # new heights if swapped new_a = colsize[i_a] - pic_a + pic_b new_b = colsize[i_b] - pic_b + pic_a if all(abs(average - new) < maxdeviation new in (new_a, new_b)): # better swap (in-place) colsize[i_a] = new_a colsize[i_b] = new_b columns[i_a].remove(pic_a) columns[i_a].append(pic_b) columns[i_b].remove(pic_b) columns[i_b].append(pic_a) maxdeviation = max(abs(average - cs) cs in colsize) return true, maxdeviation return false, maxdeviation def printit(columns, colsize, average, maxdeviation): print('columns') pp(columns) print('colsize:', colsize) print('average, maxdeviation:', average, maxdeviation) print('deviations:', [abs(average - cs) cs in colsize]) print() if __name__ == '__main__': ## data #import random #heights = [random.randint(5, 50) in range(30)] ## here's above, 'fixed'. pprint import pprint pp heights = [45, 7, 46, 34, 12, 12, 34, 19, 17, 41, 28, 9, 37, 32, 30, 44, 17, 16, 44, 7, 23, 30, 36, 5, 40, 20, 28, 42, 8, 38] columns, colsize, average, maxdeviation = first_fit(heights) printit(columns, colsize, average, maxdeviation) while 1: swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation) printit(columns, colsize, average, maxdeviation) if not swapped: break #input('paused: ') the output:
columns [[45, 12, 17, 28, 32, 17, 44, 5, 40, 8, 38], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 34, 9, 37, 44, 30, 20, 28]] colsize: [286, 267, 248] average, maxdeviation: 267.0 19.0 deviations: [19.0, 0.0, 19.0] columns [[45, 12, 17, 28, 17, 44, 5, 40, 8, 38, 9], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 34, 37, 44, 30, 20, 28, 32]] colsize: [263, 267, 271] average, maxdeviation: 267.0 4.0 deviations: [4.0, 0.0, 4.0] columns [[45, 12, 17, 17, 44, 5, 40, 8, 38, 9, 34], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 37, 44, 30, 20, 28, 32, 28]] colsize: [269, 267, 265] average, maxdeviation: 267.0 2.0 deviations: [2.0, 0.0, 2.0] columns [[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 44, 30, 20, 28, 32, 28, 40]] colsize: [266, 267, 268] average, maxdeviation: 267.0 1.0 deviations: [1.0, 0.0, 1.0] columns [[45, 12, 17, 17, 44, 5, 8, 38, 9, 34, 37], [7, 34, 12, 19, 41, 30, 16, 7, 23, 36, 42], [46, 44, 30, 20, 28, 32, 28, 40]] colsize: [266, 267, 268] average, maxdeviation: 267.0 1.0 deviations: [1.0, 0.0, 1.0] nice problem.
heres info on reverse-sorting mentioned in separate comment below.
>>> h = sorted(heights, reverse=1) >>> h [46, 45, 44, 44, 42, 41, 40, 38, 37, 36, 34, 34, 32, 30, 30, 28, 28, 23, 20, 19, 17, 17, 16, 12, 12, 9, 8, 7, 7, 5] >>> columns, colsize, average, maxdeviation = first_fit(h) >>> printit(columns, colsize, average, maxdeviation) columns [[46, 41, 40, 34, 30, 28, 19, 12, 12, 5], [45, 42, 38, 36, 30, 28, 17, 16, 8, 7], [44, 44, 37, 34, 32, 23, 20, 17, 9, 7]] colsize: [267, 267, 267] average, maxdeviation: 267.0 0.0 deviations: [0.0, 0.0, 0.0] if have reverse-sorting, code appended bottom of above code (in 'if name == ...), trials on random data:
for trial in range(2,11): print('\n## trial %i' % trial) heights = [random.randint(5, 50) in range(random.randint(5, 50))] print('pictures:',len(heights)) columns, colsize, average, maxdeviation = first_fit(heights) print('average %7.3f' % average, '\nmaxdeviation:') print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation)) swapcount = 0 while maxdeviation: swapped, maxdeviation = swap1(columns, colsize, average, maxdeviation) if not swapped: break print('%5.2f%% = %6.3f' % ((maxdeviation * 100. / average), maxdeviation)) swapcount += 1 print('swaps:', swapcount) the output shows effect of swaps:
## trial 2 pictures: 11 average 72.000 maxdeviation: 9.72% = 7.000 swaps: 0 ## trial 3 pictures: 14 average 118.667 maxdeviation: 6.46% = 7.667 4.78% = 5.667 3.09% = 3.667 0.56% = 0.667 swaps: 3 ## trial 4 pictures: 46 average 470.333 maxdeviation: 0.57% = 2.667 0.35% = 1.667 0.14% = 0.667 swaps: 2 ## trial 5 pictures: 40 average 388.667 maxdeviation: 0.43% = 1.667 0.17% = 0.667 swaps: 1 ## trial 6 pictures: 5 average 44.000 maxdeviation: 4.55% = 2.000 swaps: 0 ## trial 7 pictures: 30 average 295.000 maxdeviation: 0.34% = 1.000 swaps: 0 ## trial 8 pictures: 43 average 413.000 maxdeviation: 0.97% = 4.000 0.73% = 3.000 0.48% = 2.000 swaps: 2 ## trial 9 pictures: 33 average 342.000 maxdeviation: 0.29% = 1.000 swaps: 0 ## trial 10 pictures: 26 average 233.333 maxdeviation: 2.29% = 5.333 1.86% = 4.333 1.43% = 3.333 1.00% = 2.333 0.57% = 1.333 swaps: 4
Comments
Post a Comment