установка n изображений с переменной высотой на 3 (аналогичная длина) компоновки столбцов

Я ищу, чтобы сделать трехколоночный макет, подобный таковому piccsy.com . Учитывая количество изображений с одинаковой шириной, но различной высоты, какой алгоритм их упорядочивает, чтобы разница в длинах столбцов была минимальной? Идеально в Python или JavaScript …

Большое спасибо за вашу помощь заранее!

Мартин

Сколько изображений?

Если вы ограничиваете максимальный размер страницы и имеете значение минимальной высоты изображения, вы можете рассчитать максимальное количество изображений на странице. Это необходимо при оценке любого решения.

Я думаю, что 27 ссылок на ссылку вы дали.

Следующее использует алгоритм first_fit, упомянутый Робин Грин раньше, но затем улучшает это путем жадной замены.

Процедура подкачки находит столбец, который наиболее удален от средней высоты столбца, а затем систематически ищет своп между одним из его изображений и первым изображением в другом столбце, который минимизирует максимальное отклонение от среднего.

Я использовал случайную выборку из 30 изображений с высотами в диапазоне от пяти до 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, 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: ') 

Выход:

 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] 

Хорошая проблема.


Вот информация об обратной сортировке, упомянутая в моем отдельном комментарии ниже.

 >>> 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 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 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 

Это проблема минимизации автономной проблемы, которая, как я думаю, эквивалентна многопроцессорной задаче планирования. Вместо заданий у вас есть изображения, а вместо продолжительности работы у вас есть высоты изображения, но это точно такая же проблема. (Тот факт, что он включает в себя пространство вместо времени, не имеет значения.) Таким образом, любой алгоритм, который (приблизительно) решает любой из них, будет делать.

Вот алгоритм (называемый First Fit Decreasing ), который обеспечит вам очень компактное устройство в разумные сроки. Там может быть лучший алгоритм, но это смехотворно просто.

  1. Сортируйте изображения по порядку от самых высоких до самых коротких.
  2. Возьмите первое изображение и поместите его в самый короткий столбец. (Если несколько столбцов имеют одинаковую высоту (и кратчайший), выберите любой из них.)
  3. Повторите шаг 2, пока изображения не останутся.

Когда вы закончите, вы можете перегруппировать элементы в каждом столбце, но вы выбираете, если вам не нравится самый высокий к кратчайшему.

Вот один из них:

  // Create initial solution  // Calculate "error", ie maximum height difference // after running FFD err = (maximum_height - minimum_height) minerr = err // Run simple greedy optimization and random search repeat for a number of steps: // eg 1000 steps  if : swap a and b err = (maximum_height - minimum_height) if (err < minerr):  // X else: swap two random images from two columns err = (maximum_height - minimum_height)  
Давайте будем гением компьютера.