Матрица поиска для всех прямоугольников заданных размеров (выберите блоки сидений)

Эта проблема гораздо лучше решается за пределами mysql, на другом языке. Другими словами, у вас есть матрица сидений, некоторые из которых заняты (серые):

и вы хотите найти все прямоугольники заданных размеров , скажем 3×5. Вы можете сделать это очень эффективно с помощью двухпроходного линейного алгоритма O(n) времени (n – количество мест):

1) в первом проходе , по колонкам, снизу вверх и для каждого места, обозначьте количество следующих мест, доступных до этого:

повторить, пока:

2) во втором проходе , идите по строкам и найдите по меньшей мере 5 последовательных чисел, больших или равных 3:

так, наконец, вы получите:

который дает решение: эти числовые последовательности (зеленые области) являются верхними краями двух возможных прямоугольников 3×5 свободных мест.

Алгоритм может быть легко усилен, например, для получения всех прямоугольников с максимальной площадью. Или же он может быть использован для поиска любых сплошных областей (не только прямоугольной формы) из N мест – просто во время второго прохода искать непрерывную последовательность чисел, суммируемых по крайней мере до N.

Из вашего описания это не проблема базы данных, а алгоритмическая проблема. Я предлагаю схему черепицы, возможно, квадранту или кривую заполнения пробела. Возможно, пространственный индекс в MySQL также поможет вам решить вашу проблему. Si подразделяет 2d-плоскость на 4 плитки.

Я пришел сюда, чтобы найти решение 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 

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

Я бы просто написал запрос для каждой строки и объединил его с помощью UNION если вы можете программно создать свой запрос, а затем просто использовать один и тот же запрос X раз, просто добавляйте их вместе с UNION .

Из руководства по mysql

UNION используется для объединения результата из нескольких операторов SELECT в единый результирующий набор.

Вот простой подход. Это может быть недостаточно быстро для ваших нужд, но это место для начала.

Давайте упростим проблему и рассмотрим таблицу с именем seat имеющую столбцы row , col и taken . Первые два являются целыми числами, другие – логическими. Мы хотим найти значения row и col ограниченные прямоугольниками определенного размера, в которых taken универсальное значение false. Мы попробуем запрос, который перемещает прямоугольник и записывает сумму taken значений внутри. Прямоугольники, которые мы хотим, будут иметь сумму нуля.

Скажем так, мы ищем 2×2 открытых места. Вот запрос.

 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 обозначают верхний левый угол открытого блока. Один из последних причуд заключается в том, что вы захотите отфильтровать верхние левые углы, которые вырезают слишком близко к правым или нижним краям сидения, потому что это искусственно уменьшит их сумму (проверенный прямоугольник обрезается по краям сидения). В случае блоков 2×2 это означает row < max(row) и col < max(col) .

Теперь, если вы найдете 15 соседних мест, вы ищете прямоугольники 15×1, 1×15, 3×5 и 5×3. Вы можете сделать вышеупомянутый запрос в хранимую процедуру, которая принимает параметры ширины и высоты прямоугольника, а затем назовите ее с этими размерами, пока не найдете совпадение.

Во-первых, я собираюсь предположить, что большинство мест можно сопоставить (даже если они приближены) к квадратной сетке, т.е. где места не странно настроены или странно смещены. Таким образом, каждое сиденье может иметь до восьми мест вокруг него.

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

По сути, я смогу создать «график места» и прохожу его в соответствии с потребностями в опросе. Затем вы можете создавать запросы для получения определенных фигур или блоков.

Сетка 3×3 будет состоять из выбора открытого места, где также будут открыты сразу связанные сиденья во всех направлениях. Да, это будет восемь JOINS, но попробуйте и оптимизируйте позже.

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

Блок 1×15 будет запросом для выбора открытого места, где вы присоединитесь к 14 глубинам вдоль EastID или WestID.

Возможно, вы можете обобщать и генерировать запросы программно.

PS: В зависимости от того, какой движок вы используете, вы можете иметь встроенные пространственные возможности.

Удачи.