将 n 个可变高度图像拟合为 3(相似长度)列布局 [英] fitting n variable height images into 3 (similar length) column layout
本文介绍了将 n 个可变高度图像拟合为 3(相似长度)列布局的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我希望制作一个类似于 piccsy.com 的 3 列布局.给定许多宽度相同但高度不同的图像，排序它们的算法是什么，以使列长的差异最小?最好使用 Python 或 JavaScript...
非常感谢您的帮助！
马丁
解决方案
多少张图片?
如果你限制了最大页面大小，并且有一个最小图片高度的值，你就可以计算出每页的最大图像数.在评估任何解决方案时，您都需要它.
我认为您提供的链接中有 27 张图片.
以下使用 Robin Green 之前提到的 first_fit 算法，但随后通过贪婪交换对其进行了改进.
交换例程找到离平均列高度最远的列，然后系统地寻找其中一张图片与另一列中的第一张图片之间的交换，以最小化与平均值的最大偏差.
我使用了 30 张图片的随机样本，高度在 5 到 50 个单位"之间.就我而言，收敛速度很快，并且在 first_fit 算法上得到了显着改进.
代码(Python 3.2:
def first_fit(items, bincount=3):items = sorted(items, reverse=1) # 新 - 改进了首次拟合.bins = [[] for c in range(bincount)]binsizes = [0] * bincount对于项目中的项目:minbinindex = binsizes.index(min(binsizes))bins[minbinindex].append(item)binsizes[minbinindex] += 项目平均值 = sum(binsizes)/float(bincount)maxdeviation = max(abs(average - bs) for bs in binsizes)返回箱，箱大小，平均值，最大偏差def swap1(列数，colsize，平均值，边距=0):'看看你是否可以做一个交换来平滑高度'colcount = len(列)最大偏差, i_a = max((abs(average - cs), i)对于枚举中的 i,cs(colsize))col_a = 列[i_a]for pic_a in set(col_a): # 使用 set 就好像相同的高度然后只做一次对于枚举(列)中的 i_b、col_b:if i_a != i_b: # 不同列对于集合中的 pic_b(col_b):if (abs(pic_a - pic_b) > margin): # 高度不同# 交换后的新高度new_a = colsize[i_a] - pic_a + pic_bnew_b = colsize[i_b] - pic_b + pic_a如果所有(绝对(平均 - 新)< 最大偏差对于新的 (new_a, new_b)):# 更好地交换(就地)colsize[i_a] = new_acolsize[i_b] = new_b列[i_a].remove(pic_a)列[i_a].append(pic_b)列[i_b].remove(pic_b)列[i_b].append(pic_a)maxdeviation = max(abs(average - cs)对于 colsize 中的 cs)返回真，最大偏差返回假，最大偏差def printit(列数，colsize，平均值，最大偏差):打印('列')pp(列)打印('colsize:'，colsize)打印('平均值，最大偏差:'，平均值，最大偏差)print('偏差:', [abs(average - cs) for cs in colsize])打印()如果 __name__ == '__main__':## 一些数据#导入随机#heights = [random.randint(5, 50) for i in range(30)]## 这是上面的一些内容，但已修复".从 pprint 导入 pprint 作为 pp高度 = [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]列，colsize，平均值，maxdeviation = first_fit(heights)打印(列，colsize，平均值，最大偏差)而 1:交换，maxdeviation = swap1(列，colsize，平均值，maxdeviation)打印(列，colsize，平均值，最大偏差)如果没有交换:休息#input('暂停:')输出:
列[[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]平均，最大偏差:267.0 19.0偏差:[19.0, 0.0, 19.0]列[[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]平均，最大偏差:267.0 4.0偏差:[4.0, 0.0, 4.0]列[[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]平均，最大偏差:267.0 2.0偏差:[2.0, 0.0, 2.0]列[[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]平均，最大偏差:267.0 1.0偏差:[1.0, 0.0, 1.0]列[[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]平均，最大偏差:267.0 1.0偏差:[1.0, 0.0, 1.0]好问题.
<小时>这里是我在下面的单独评论中提到的反向排序信息.
<预><代码>>>>h = 排序(高度，反向 = 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]>>>列，colsize，平均值，maxdeviation = first_fit(h)>>>打印(列，colsize，平均值，最大偏差)列[[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]平均值，最大偏差:267.0 0.0偏差:[0.0, 0.0, 0.0]<小时>
如果你有反向排序，这个额外的代码附加到上面代码的底部(在'if name == ...)，将对随机数据进行额外的试验:
用于范围(2,11)的试验:打印('
## 试用 %i' % 试用)高度 = [random.randint(5, 50) for i in range(random.randint(5, 50))]打印('图片:'，len(高度))列，colsize，平均值，maxdeviation = first_fit(heights)打印('平均值 %7.3f' % 平均值, '
maxdeviation:')打印('%5.2f%% = %6.3f' % ((maxdeviation * 100./average), maxdeviation))交换计数 = 0而最大偏差:交换，maxdeviation = swap1(列，colsize，平均值，maxdeviation)如果没有交换:休息打印('%5.2f%% = %6.3f' % ((maxdeviation * 100./average), maxdeviation))交换计数 += 1打印('交换:'，交换计数)额外的输出显示了交换的效果:
## 试玩 2图片:11平均 72.000最大偏差:9.72% = 7.000掉期:0##试验3图片:14平均 118.667最大偏差:6.46% = 7.6674.78% = 5.6673.09% = 3.6670.56% = 0.667掉期:3## 试验 4图片:46平均 470.333最大偏差:0.57% = 2.6670.35% = 1.6670.14% = 0.667掉期:2##试验5图片:40平均 388.667最大偏差:0.43% = 1.6670.17% = 0.667掉期:1##试验6图片:5平均 44.000最大偏差:4.55% = 2.000掉期:0##试炼7图片:30平均 295.000最大偏差:0.34% = 1.000掉期:0##试验8图片:43平均 413.000最大偏差:0.97% = 4.0000.73% = 3.0000.48% = 2.000掉期:2## 试验 9图片:33平均 342.000最大偏差:0.29% = 1.000掉期:0##试炼10图片:26平均 233.333最大偏差:2.29% = 5.3331.86% = 4.3331.43% = 3.3331.00% = 2.3330.57% = 1.333掉期:4I'm looking to make a 3-column layout similar to that of piccsy.com. Given a number of images of the same width but varying height, what is a algorithm to order them so that the difference in column lengths is minimal? Ideally in Python or JavaScript...
Thanks a lot for your help in advance!
Martin
解决方案
How many images?
If you limit the maximum page size, and have a value for the minimum picture height, you can calculate the maximum number of images per page. You would need this when evaluating any solution.
I think there were 27 pictures on the link you gave.
The following uses the first_fit algorithm mentioned by Robin Green earlier but then improves on this by greedy swapping.
The swapping routine finds the column that is furthest away from the average column height then systematically looks for a swap between one of its pictures and the first picture in another column that minimizes the maximum deviation from the average.
I used a random sample of 30 pictures with heights in the range five to 50 'units'. The convergenge was swift in my case and improved significantly on the first_fit algorithm.
The code (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, maxdeviation
def 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, maxdeviation
def 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: ')
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 the info on reverse-sorting mentioned in my 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 you have the reverse-sorting, this extra code appended to the bottom of the above code (in the 'if name == ...), will do extra trials on random data:
for trial in range(2,11):
print('
## 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, '
maxdeviation:')
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 extra output shows the effect of the 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
这篇关于将 n 个可变高度图像拟合为 3(相似长度)列布局的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
