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

Ответ 1

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

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

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

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

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

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

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

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

Ответ 2

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

Ответ 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

Ответ 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 :) 

Ответ 5

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

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

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

Ответ 6

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

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 будет запросом, чтобы выбрать открытое место, где вы присоединитесь к 14 глубинам вдоль EastID или WestID.

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

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

Удачи.

Ответ 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. Вы можете сделать вышеуказанный запрос в хранимой процедуре, которая принимает параметры ширины и высоты прямоугольника, а затем назовите ее с этими размерами, пока не найдете совпадение.