0

我的情况

  • 我有 N 个矩形
  • 矩形都具有相同的形状（例如 2 英寸宽 x 1 英寸高） - 让我们将此尺寸称为 Sw 和 Sh 的宽度和高度
  • 我想将这些矩形放置在网格中，使矩形完全位于顶部并彼此相邻 - 就像您在电子表格中看到的一样
  • 我需要的是：给定 N、Sw 和 Sh，将这些矩形堆叠成可能的最方形排列的行数 (R) 和列数 (C) 是多少
  • 可以理解的是，R & C 可能提供比需要更多的单元格（例如，如果 N=15,Sw=1,Sh=1 则 R=4,C=4 为 15 个矩形产生 16 个“槽” - 这是可以的。
  • 如果 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


***************
*||||||*      *
***************
*||||||*||||||*
***************
*||||||*||||||*
***************

AaronofTomorrow's answer的实现

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

受 Will 的回答启发的另一个实现（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)
4

4 回答 4

2

基于 Will Dean 的回答，找到他的公式的导数（关于 nCols）：

-N*Sh / nCols + Sw

然后将其设置为 0 并求解 nCols，得到：

nCols = sqrt(N * Sh / Sw)

四舍五入，你应该有最佳的列数：

cols = round(sqrt(N * Sh / Sw))
rows = ceil(N / cols)

于 2008-12-04T10:13:53.510 回答
1

我想你会发现“最方形”是通往“最圆形”的一步，这是圆周（周长）最小的点。

你的周长是 2*nRows*Sh + 2*nCols Sw。您知道 nRows nCols >= N，我认为在下面将其简化为 nRows*nCols = N 就可以了。

如果不尝试它，我认为您可以有用地尝试找到函数的（最小）：

N/nCols*Sh + nCols*Sw

不知道这是否可行，但它使我可以将工作日的开始时间推迟 5 分钟，所以这不是一个致命的损失。

于 2008-12-04T09:12:03.433 回答
0

如果矩形的数量不受限制，则需要找到 Sw 和 Sh 的 LCD（最小公分母）。然后你可以将它除以 Sw 和 Sh 以找到水平和垂直计数。

既然是有限的，那就不一样了。我是否正确理解您必须用完所有矩形并且结果也必须是矩形？我会假设是这样。

在这种情况下，您对于如何排列矩形并没有太多选择。只有那么多整数对在相乘时给出 N。

在您的情况下，我会尝试找到所有可能的整数对（使用简单的 FOR 循环）并查看哪一个最接近正方形。在 FOR 循环中注意，您只需要检查 sqrt(N)，因为之后您找到的每个整数对都与您已经找到的相同，只是相反。

于 2008-12-04T09:03:02.077 回答
0

首先，特殊情况的真正正方形矩形或维度为零的矩形。

否则，为了解释的简单，迭代地构建它：

    添加一个新行，直到高度大于宽度
    添加一个新列，直到宽度大于高度

在代码中可能如下所示：

    // 放置第一个图块作为初始化
    int 瓦片 = num_tiles - 1；
    整数行 = 1；
    整数列 = 1；
    整数宽度 = sx;
    int 高度 = sy;

    诠释我=1；// 只是因为我们好奇我们有多少次迭代

    // 构建近正方形
    而（瓷砖> 0）{
        而（（瓷砖> 0）
        && ((宽度 + sx) <= (高度 + sy))) {
            // 添加一列
            瓷砖-=行；
            列++；
            宽度 += sx;
        我++；
        }
        而（（瓷砖> 0）
        && ((height + sy) < (width + sx))) {
            // 添加一行
            瓷砖-=列；
            行++；
            高度 += sy;
        我++；
        }
    }

    // 完毕
    printf("%d = %d (%dx%d) = %dx%d (%dx%d) in %d\n",
    num_tiles,tiles,sx,sy,rows,columns,width,height,i);

和一些结果：

100 = -5 (10x20) = 7x15 (150x140) 在 21
1000 = -12 (10x20) = 22x46 (460x440) 在 67
10000000 = -1628 (10x20) = 2236x4473 (44730x44720) 在 6708
200 = 0 (7x13) = 10x20 (140x130) 在 29
2000 = -13 (7x13) = 33x61 (427x429) 在 93
9376 中的 20000000 = -3790 (7x13) = 3282x6095 (42665x42666)
400 = -14 (17x13) = 23x18 (306x299) 在 40
4000 = -15 (17x13) = 73x55 (935x949) 在 127
40000000 = -192 (17x13) = 7232x5531 (94027x94016) 在 12762

最坏情况 O(n)，对于非常薄的矩形或少量矩形。但是在一般情况下 O(sqrt(n)) ？

于 2008-12-04T09:44:56.830 回答