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

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

预先感谢，需要更多信息，请询问！

Answer 1

这个问题在 mysql 之外用另一种语言可以更好地解决。换句话说，您有一个座位矩阵，其中一些已被占用（灰色座位）：

和您想要找到给定尺寸的所有矩形，例如 3x5。您可以通过两次线性O(n)时间算法（n是座位数）非常有效地完成此操作：

第一次通过1），按列从下到上，对于每个座位，表示到此为止可用的连续座位数：

重复，直到：

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

所以，最后，您得到：

<图片src="https://i.sstatic.net/pddAx.gif" alt="在此处输入图像描述">

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

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

Answer 2

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

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

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

Answer 5

如果您可以以编程方式创建查询，我只需为每一行编写一个查询并使用 UNION 组合它，然后只需使用相同的查询 X 次，只需继续将它们附加到 UNION代码>.

来自 mysql 手册

UNION 用于合并多个 SELECT 语句的结果
到单个结果集中。

Answer 6

这是一个简单的方法。它可能不够快，无法满足您的需求，但它是一个起点。

让我们简化问题并考虑一个名为 seat 的表，其中包含 row、col 和 taken 列。前两个是整数，另一个是布尔值。我们希望找到限制在特定大小矩形内的 row 和 col 值，其中 taken 普遍为 false。我们将尝试一个查询，该查询移动一个矩形并记录其中所取值的总和。我们想要的矩形的总和为零。

假设我们正在寻找 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 <最大（列）。

现在，在查找 15 个相邻座位的情况下，您正在寻找 15x1、1x15、3x5 和 5x3 的矩形。您可以将上述查询放入一个采用矩形宽度和高度参数的存储过程中，然后使用这些尺寸调用它，直到找到匹配项。

Answer 7

首先，我假设大多数场地都可以映射（即使是近似的）到方形网格，即。座位的设置并不奇怪，也没有奇怪的偏移。因此，每个座位周围最多可以有八个座位。

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

本质上，我将能够创建一个“座位图”并根据查询的需要遍历它。然后，您可以创建查询来获取某些形状或块。

3x3 网格将包括选择一个开放座位，其中所有方向上直接链接的座位也都是开放的。是的，这将是八个 JOINS，但请尝试一下并稍后优化。

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 个深度。

您也许可以以编程方式概括和生成查询。

PS：根据您使用的引擎，您可能具有内置的空间功能。

祝你好运。