将n个可变高度图像拟合到3个（相似长度）列布局中

将n个可变高度图像拟合到3个（相似长度）列布局中

多少张图片？

如果限制最大页面尺寸，并具有最小图片高度的值，则可以计算每页的最大图像数。评估任何解决方案时都需要此。

我认为您提供的链接上有27张图片。

下面的代码使用了Robin Green前面提到的first_fit算法，但随后通过贪婪的交换对其进行了改进。

交换例程找到距离平均列高最远的列，然后系统地查找其图片之一与另一列中的第一张图片之间的交换，以最大程度地减少与平均值的最大偏差。

我随机抽取了30张图片，高度在5到50个“单位”之间。在我的情况下，收敛很快，并且在first_fit算法上得到了显着改善。

代码（Python 3.2：

def first_fit(items, bincount=3):    items = sorted(items, reverse=1) # New - improves first fit.    bins     = [[] for c in range(bincount)]    binsizes = [0] * bincount    for 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) for bs in binsizes)    return bins, binsizes, average, maxdeviationdef swap1(columns, colsize, average, margin=0):    'See if you can do a swap to smooth the heights'    colcount = len(columns)    maxdeviation, i_a = max((abs(average - cs), i)        for i,cs in enumerate(colsize))    col_a = columns[i_a]    for pic_a in set(col_a): # use set as if same height then only do once        for i_b, col_b in enumerate(columns): if i_a != i_b: # Not same column     for 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         for new in (new_a, new_b)):      # Better to 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)   for cs in colsize)      return True, maxdeviation    return False, maxdeviationdef printit(columns, colsize, average, maxdeviation):    print('columns')    pp(columns)    print('colsize:', colsize)    print('average, maxdeviation:', average, maxdeviation)    print('deviations:', [abs(average - cs) for cs in colsize])    print()if __name__ == '__main__':    ## Some data    #import random    #heights = [random.randint(5, 50) for i in range(30)]    ## Here's some from the above, but 'fixed'.    from pprint import pprint as 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: ')

输出：

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.0deviations: [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.0deviations: [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.0deviations: [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.0deviations: [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.0deviations: [1.0, 0.0, 1.0]

好问题。

---

这是我在下面的单独评论中提到的有关反向排序的信息。

>>> 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.0deviations: [0.0, 0.0, 0.0]

---

如果您进行了反向排序，则将上述额外代码附加到上述代码的底部（在’if name == …中），将对随机数据进行额外的试验：

for trial in range(2,11):    print('n## Trial %i' % trial)    heights = [random.randint(5, 50) for i 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)

额外的输出显示了交换的效果：

## Trial 2Pictures: 11average  72.000 maxdeviation: 9.72% =  7.000swaps: 0## Trial 3Pictures: 14average 118.667 maxdeviation: 6.46% =  7.667 4.78% =  5.667 3.09% =  3.667 0.56% =  0.667swaps: 3## Trial 4Pictures: 46average 470.333 maxdeviation: 0.57% =  2.667 0.35% =  1.667 0.14% =  0.667swaps: 2## Trial 5Pictures: 40average 388.667 maxdeviation: 0.43% =  1.667 0.17% =  0.667swaps: 1## Trial 6Pictures: 5average  44.000 maxdeviation: 4.55% =  2.000swaps: 0## Trial 7Pictures: 30average 295.000 maxdeviation: 0.34% =  1.000swaps: 0## Trial 8Pictures: 43average 413.000 maxdeviation: 0.97% =  4.000 0.73% =  3.000 0.48% =  2.000swaps: 2## Trial 9Pictures: 33average 342.000 maxdeviation: 0.29% =  1.000swaps: 0## Trial 10Pictures: 26average 233.333 maxdeviation: 2.29% =  5.333 1.86% =  4.333 1.43% =  3.333 1.00% =  2.333 0.57% =  1.333swaps: 4