Search matrix for all rectangles of given sizes (select seat blocks)

Question

All,

I tried to figure out how to choose 15 tickets in one block of seats.

EDIT : the problem is how to find all the rectangles of the given sizes (for example, 3x5) free spaces?

My table is below, and the query selects 4 consecutive seats (or 15 or something else), which is fine ...

But what I want to do is select 15 places, they can be divided into several lines, i.e. 3 x 5, but I would like them to be locked together.

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

those. they would be 3 rows in front of each other. row of 9 places from 10 to 25, row of 8 places from 10 to 25, row of 7 places from 10 to 25.

It may also be necessary to consider whether the seat block has a different number of seats, i.e. the corner block may have an arc to have more seats in the back than in the front.

Any manual in the form of ehnaceing SQL or some algorithm or some PHP code. I waved my brain for most of the week.

 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; 

My date request is one that returns combinations of blocks from X places.

 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 

Thank you in advance, you need more information, please just ask!

Answer 1

This problem is much better solved outside of mysql, in another language. In other words, you have a seat matrix, some of which are occupied (gray):

and you want to find all the rectangles of the given sizes , say 3x5. You can do this very efficiently using the two-pass linear O(n) time algorithm (n is the number of places):

1) in the first pass , go through the columns, from bottom to top and for each place, indicate the number of available places in a row before that:

repeat until:

2) in the second pass , go through the lines and find at least 5 consecutive numbers greater than or equal to 3:

so finally you get:

which gives a solution: these numerical sequences (green areas) are the top edges of two possible rectangles 3x5 free spaces.

The algorithm can be easily expanded to, for example, get all the rectangles with the maximum area. Or, it can be used to search for any continuous areas (not only rectangular) from N places - just during the second pass, look for a continuous sequence of numbers that can be summed up to at least N.

Answer 2

From your description, this is not a database problem, but an algorithmic problem. I suggest a tile layout, possibly a quadrant or a space-filling curve. Perhaps the spatial index in MySQL will also help you solve your problem. Si divides the 2d plane into 4 tiles.

Answer 3

I came here to find a Python solution. Here is mine that returns all positions:

 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) 

Output:

 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 NNNNNNNN sssssss NN sssssss NNNNNNNN */ // 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

I would just write a query for each row and combine it with UNION , if you can programmatically create your query, and then just use the same query X number of times just add them with UNION .

From mysql manual

UNION is used to combine the result of several SELECT statements into a single result set.

Answer 6

Firstly, I’m going to assume that most places can be compared (even if they are close) to a square grid, i.e. where places are not strangely tuned or strangely shifted. Thus, each place can have up to eight places around it.

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

Essentially, I can create a “place schedule” and go through it according to the needs of the survey. Then you can create queries to get specific forms or blocks.

The 3x3 grid will consist of a choice of open space, where the immediately connected seats will also be open in all directions. Yes, it will be eight JOINS, but try and optimize later.

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

A 1x15 block will be a request to select an open spot where you will join the 14 depths along EastID or WestID.

Perhaps you can generalize and generate queries programmatically.

PS: Depending on which engine you use, you may have built-in spatial capabilities.

Good luck.

Answer 7

Here is a simple approach. It may not be fast enough for your needs, but this is the place to start.

Let's simplify the task and consider a table named seat with the columns row , col and taken . The first two are integers, the others are logical. We want to find the row and col values ​​bounded by rectangles of a certain size, in which taken is generally accepted. We will try a query that moves the rectangle and writes the sum of the values taken inside. The rectangles we want will have a sum of zero.

Let's say we are looking for 2x2 blocks of open spaces. Here is the request.

 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 

Just filter the output of this query, where count = 0 . The row and col values ​​indicate the upper left corner of the open block. One of the latest quirks is that you will want to filter out the upper left corners that are cut too close to the right or lower edges of the seat, because this artificially reduces their sum (the checked rectangle is cropped around the edges of the seat). For 2x2 blocks, this means row < max(row) and col < max(col) .

Now that you find 15 neighboring places, you are looking for rectangles 15x1, 1x15, 3x5 and 5x3. You can make the above request in a stored procedure that takes the width and height of the rectangle, and then name it with these sizes until you find a match.