Моя ситуация
- у меня есть N прямоугольников
- Все прямоугольники имеют одинаковую форму (например, 2 дюйма в ширину и 1 дюйм в высоту). Давайте обозначим этот размер как Sw и Sh для ширины и высоты
- Я хочу расположить эти прямоугольники в сетке таким образом, чтобы канавки полностью располагались сверху и рядом друг с другом - как показано в электронной таблице
- Что мне нужно, так это: Учитывая N, Sw и Sh, каково количество строк (R) и столбцов (C), в которых эти стеки были бы собраны в максимально квадратное расположение
- Понятно, что R & C может предоставить больше ячеек, чем необходимо (например, если N = 15, Sw = 1, Sh = 1, то R = 4, C = 4, что дает 16 «слотов» для 15 прямоугольников - что все в порядке.
- Если Sw = Sh, тогда моих скромных математических навыков достаточно - когда их прямоугольники имеют различную ширину и высоту - честно говоря, это вне меня.
Некоторые заметки
- Да, я прочитал этот вопрос: Сложив прямоугольники, чтобы занять как можно меньше места и нет, это не помогло. И это не тот же вопрос. Этот вопрос касается прямоугольников, которые могут быть разных размеров, в этом вопросе прямоугольники имеют одинаковый размер
- Да, я искал на wolfram.com и т. Д., И мне не повезло
- У меня нет сильных математических знаний, поэтому способ, которым я формулирую эту проблему, сам по себе может помешать мне найти ответ - я пробовал связанные поиски, связанные с разбиением на листы, анализом, разложением, и не имел никакого успеха там либо
Некоторые примеры
the * indicates the edges of the rects
the | indicates that a cell is "filled-in"
Notice that not all R*C cells are filled in, but only and exactly N cells
IF N=1, Sw=2, Sh=1 THEN R=1, C=1
********
*||||||*
********
IF N=2, Sw=2, Sh=1 THEN R=2, C=1
********
*||||||*
********
*||||||*
********
IF N=3, Sw=2, Sh=1 THEN R=2, C=2
***************
*||||||* *
***************
*||||||*||||||*
***************
IF N=4, Sw=2, Sh=1 THEN R=2, C=2
***************
*||||||*||||||*
***************
*||||||*||||||*
***************
IF N=5, Sw=2, Sh=1 THEN R=3, C=2
***************
*||||||* *
***************
*||||||*||||||*
***************
*||||||*||||||*
***************
Реализация завтрашнего ответа Aaronof
# Implementation of AaronofTomorrow's answer
# implemented in python 2.6
# reasonable output
# works in constant time
import math
def f( N, Sw, Sh ) :
cols = math.sqrt( float(N) * float(Sh) / float(Sw) )
cols = round(cols)
rows = float(N) / float(cols)
rows = math.ceil(rows)
return (int(cols),int(rows))
Еще одна реализация, вдохновленная ответом Уилла (Обновлено 2008-12-08) - это та, которую я наконец-то использовал
# Another implementation inspired by Will's answer
# implemented in python 2.6
# reasonable output - a bit better in yielding more squarelike grids
# works in time proportional to number of rects
#
# strategy used it to try incrementaly adding a rect.
# if the resulting rect requires more space then two
# possibilities are checked - adding a new row or adding a new col
# the one with the best aspect ratio (1:1) will be chosen
def g( N, Sw, Sh ) :
slope = float(Sh)/float(Sw)
cols = 1
rows = 1
for i in xrange( N ) :
num_to_fit =i+1
allocated_cells= cols* rows
if ( num_to_fit <= allocated_cells ) :
pass # do nothing
else :
hc,wc = float(Sh * rows), float(Sw * (cols+1))
hr,wr = float(Sh * (rows+1)), float(Sw * cols)
thetac = math.atan( hc/wc)
thetar = math.atan( hr/wr)
alpha = math.pi/4.0
difr = abs(alpha-thetar)
difc = abs(alpha-thetac)
if ( difr < difc ) :
rows = rows +1
else:
cols = cols + 1
return (cols,rows)