寻找给定尺寸的所有矩形（选择座位块）：搜索矩阵

Question

大家好，

我一直在尝试找出如何在一个座位块中选择15张票。

编辑：问题是 - 如何查找给定尺寸（例如3x5）的所有空闲座位的矩形区域？

下面是我的表格，查询选择了4个连续座位（或15个或其他），这很好...

但我想要做的是选择15个座位，它们可能分散在多行上，即3 x 5，但我希望它们被连在一起，即在同一个块里。

row 9 ..(some seats)..[5 seats]..(some seats)..
row 8 ..(some seats)..[5 seats]..(some seats)..
row 7 ..(some seats)..[5 seats]..(some seats)..

也就是说，它们将成为3排位于彼此前面。第9排的座位是从10到25，第8排的座位是从10到25，第7排的座位是从10到25。

还需要考虑一下，如果一个座位块有不同数量的座位，例如，一个角落的座位块可能弯曲，后面的座位比前面的座位多。

关于SQL语句、算法或PHP代码等方面的任何指导都可以。我已经绞尽了脑汁，大部分时间都在思考这个问题。

CREATE TABLE `seats` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `event_id` int(11) DEFAULT NULL,
  `performance` int(11) DEFAULT NULL,
  `block` int(11) DEFAULT NULL,
  `row` int(11) DEFAULT NULL,
  `seat` int(11) DEFAULT NULL,
  `status` int(10) DEFAULT 1,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

到目前为止我的查询返回X个座位的块的组合。

SELECT    a.event_id, a.performance, a.block,
          a.row, a.seat AS start_seat,
          a.seat + (4 - 1) AS end_seat,
          4 AS requested_seats,
          a.id AS start_allocation_id
FROM      seats a
          LEFT JOIN seats b ON
              a.event_id = b.event_id AND
              a.performance = b.performance AND
              a.block = b.block AND
              a.row = b.row AND
              a.seat < b.seat AND
              b.seat < a.seat + 4 AND
              b.status = 1
WHERE     a.status = 1 AND
          a.event_id = 1
GROUP BY  a.seat
HAVING COUNT(b.seat) + 1 = 4
ORDER BY performance

提前致谢，如需更多信息，请随时提问！

- Brian

---

我不确定我理解您正在尝试做什么以及情况...但是对于将可用座位的掩码（例如IP子网掩码）应用于一行，怎么样？ 例如，00011111000，所有的1都是可用的。 - Dor

Brian，你是在尝试找到所有3x5的空座位矩形块吗？是这样吗？ - Tomas

我发布了一个答案 - 这是你想要的吗？ - Tomas

你可以修改这个单次线性解决方案，以便在找到所需大小的矩形后立即停止。 - jfs

Answer 1

这个问题最好在MySQL外部用另一种语言来解决。换句话说，你有一个座位矩阵，其中一些是被占用的（灰色的）：

并且你想要找到给定尺寸（比如3x5）的所有矩形。你可以通过两次线性的O(n)时间算法（n为座位数）来非常高效地完成这个操作： 1) 在第一次遍历中，按列从下往上进行，并为每个座位指定到该座位连续可用的座位数:

重复以上步骤，直到:

2) 在第二次遍历中，按行进行，并查找至少5个大于或等于3的连续数字：

最终得到：

这产生了解决方案：这些数字序列（绿色区域）是2个可能的3x5空座位矩形的顶部边缘。

算法可以很容易地改进，例如获取所有面积最大的矩形。或者，它可以用于查找N个座位的任何连续区域（不仅限于矩形形状）- 只需在第二次遍历期间查找连续的数字序列，其总和至少为N即可。

- Tomas

---

非常好，考虑到朴素解决方案（尝试每个边界框）至少为O(nm)，其中m是块的大小。但是，您如何找到7个人的座位块呢？ - Nick Johnson

@Nick，简单来说——在第二次遍历中，只需查找数字序列的总和至少为7。您可以添加一个条件，例如“不超过两行”，因此在这种情况下，每个数字> 2仅计为2。 - Tomas

项目被遗憾地放弃了...但是它本来会是一个优雅的解决方案。 - Brian

Answer 2

从您的描述来看，这不是一个数据库问题，而是一个算法问题。我建议使用平铺模式，可能是四叉树或空间填充曲线。也许在MySQL中使用空间索引可以帮助您解决问题。空间索引将2D平面细分为4个瓷砖。

- Micromega

---

非常感谢您提供的信息... 很好的信息值得调查，正如您所知道的那样，由于其复杂性（和非常繁忙），可能需要一些时间来验证结果！在此期间我已经点赞了。 - Brian

我认为在数据库中这样做不是一个好主意。场馆足够小，很可能更快、更高效地将其加载到内存中并在那里执行操作，而不是进行磁盘操作。 - Nick Johnson

这一切都太过复杂了。有一个非常简单的O(N)解决方案，请查看我的帖子。 - Tomas

Answer 3

我来这里寻找Python解决方案。这是我的解决方案，它返回所有位置：

import numpy

s = '''0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0'''

area = 15
nrows = 6
ncols = 11
skip = 1

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if a[r][c] == skip:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            if (dh+1)*minw == area:
                print(
                    'area', area, 'row', r, 'col', c,
                    'height', dh+1, 'width', minw)

输出：

area 15 row 4 col 8 height 3 width 5
area 15 row 5 col 10 height 3 width 5

- tommy.carstensen

Answer 4

    $nr_tickets = 15; // or whatever


// build an array of different configurations:
// since you always want people as close to eachother as possible this is a suggestion:

$configurations = array();
for($columns=1; $columns<=$nr_tickets; $columns++)
{
    $BLOCK = array();
    $remainder = $nr_tickets % $columns;
    // $nr_tickets - $remainder = greatest number divisible exactly by $i (columns) which is the number of rows you want.
    $rows = (($nr_ticket-$odd) / $i);
    //$configurations[$columns] = $rows // make a rectangle configuration or $columns x $rows with $remainder tickets left.
    $BLOCK[] = array_fill(0, $columns, array_fill(0, $rows, X); // multidimensional array
    for($a=0; $a<$odd; $a++)
    {

        // each of the remainder seats need to be 'stuck on to the block/rectangle of seats you already have, this can be done in
        // ($rows + $columns * 2) - $a ways for each of the consecutive non-assigned tickets
        /*
            lets say you have a block of 2x7 (s) with 1 (N) possible ticket left 
                   N  N  N  N  N  N  N  
            N  s  s  s  s  s  s  s  N 
            N  s  s  s  s  s  s  s  N   
               N  N  N  N  N  N  N 
        */
        // so basically we can add a ticket to each of the rows and for each of those configurations we need to add $a more
        // this may be simpler with a recursive function call that adds $a more for each 1 ticket you add here to a row or a column. 
    }


}



// now you can go select all different permutations of settings from the database and select one you like :) 

- Garuda

---

只是一个“草稿”，但你可以理解我的意思。 - Garuda

已经有人写过类似这样的代码了 - 块可能是弯曲或梯形状的，前面的座位比后面的座位少。 - Brian

Answer 5

首先，我假设大多数场馆都可以映射到一个正方形网格上（即使是近似的），例如座位布置不奇怪或者偏移。因此，每个座位周围最多可能有八个座位。

CREATE TABLE Seat {
   SeatID int,
   Status int,
   ...
   NorthID int,
   NorthWestID int,
   WestID int,
   ...
   NorthEastID int
}

基本上，我将能够创建一个“座位图”，并根据查询需求进行遍历。然后，您可以创建查询以获取特定的形状或块。

一个3x3的网格将包括选择一个开放的座位，其中所有方向上的直接链接座位也都是开放的。是的，这将涉及到八个连接操作，但先试用一下，之后再进行优化。

SELECT * FROM Seat x
INNER JOIN Seat n ON x.NorthID = n.SeatID
INNER JOIN Seat nw ON x.NorthWestID = n.SeatID
...

一个1x15的块将是一个查询，用于选择一个开放的座位，您可以在EastID或WestID上加入14个深度。

您可能可以概括并通过编程生成这些查询。

附注：根据您使用的引擎，您可能具有内置的空间能力。

祝你好运。

- alphadogg

Answer 6

如果您可以以编程方式创建查询，则只需为每行编写一个查询并使用UNION将它们组合起来，然后只需使用相同的查询X次即可，只需使用UNION将它们附加在一起。

来自mysql手册

UNION用于将多个SELECT语句的结果组合成单个结果集。

- Ali

---

已经完成了这个，对于概念验证来说还不错 - 但如果你要处理数百或数千个预订请求，这是不可行的 :) - Brian

Answer 7

这里有一个简单的方法。它可能不够快，但是可以作为一个起点。

让我们简化问题，考虑一个名为seat的表，它有row、col和taken三列。前两个是整数，另一个是布尔值。我们想要找到row和col的值，这些值被限制在某些大小的矩形中，其中taken是普遍为假的。我们将尝试一个查询，移动一个矩形并记录其中taken值的总和。我们想要的矩形将具有零的总和。

我们只需要说我们正在寻找2x2个开放座位的块。以下是查询。

SELECT row, col,
       (select sum(taken) from seat as s2
               where s2.row >= s1.row and s2.row < s1.row + 2
                 and s2.col >= s1.col and s2.col < s1.col + 2) as count
       FROM seat as s1

只需过滤此查询的输出，其中 count = 0。 row 和 col 将指定开放块的左上角。最后一个怪癖是，您将希望过滤掉靠近座位右侧或底部边缘的左上角，因为这会人为地降低它们的总和（测试的矩形被剪切到座位的边缘）。对于2x2块，这意味着 row < max(row) 和 col < max(col)。

现在，在查找15个相邻座位的情况下，您要寻找15x1、1x15、3x5和5x3的矩形。您可以将上述查询转换为一个存储过程，该存储过程接受矩形宽度和高度参数，然后使用这些大小调用它，直到找到匹配项。

- Joe Nelson