15

全て、

私は、1つの座席ブロック内でたとえば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

よろしくお願いします。詳細が必要な場合は、お問い合わせください。

4

7 に答える 7

14

この問題は、別の言語で mysql の外で解決する方がはるかに優れています。言い換えれば、座席のマトリックスがあり、そのうちのいくつかは占有されています (灰色の座席):

ここに画像の説明を入力

そして、指定された寸法、たとえば 3x5のすべての長方形を見つけたいとします。これは、2 パス線形O(n)時間アルゴリズム (n は座席数)によって非常に効率的に行うことができます。

1) 最初のパスでは、列ごとに下から上に移動し、各座席について、この座席までに使用可能な連続した座席数を示します。

ここに画像の説明を入力

まで繰り返します:

ここに画像の説明を入力

2) 2 番目のパスで、行ごとに移動し、3 以上の連続する数字を少なくとも 5 つ探します。

ここに画像の説明を入力

したがって、最終的に次のようになります。

ここに画像の説明を入力

これらの数字列 (緑色の領域) は、3x5 の自由席の 2 つの可能な長方形の上端です。

このアルゴリズムは、たとえば、すべての長方形を最大面積で取得するように簡単に拡張できます。または、N 席の連続した領域 (長方形だけでなく) を見つけるために使用することもできます。2 回目のパスで、合計が少なくとも N になる連続した数列を探します。

于 2011-09-08T19:07:51.683 に答える
3

あなたの説明から、これはデータベースの問題ではなく、アルゴリズムの問​​題です。四分木または空間充填曲線のタイリングスキーマをお勧めします。おそらく、MySQLの空間インデックスは、問題の解決にも役立つでしょう。siは、2D平面を4つのタイルに分割します。

于 2011-08-07T07:10:23.283 に答える
1

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
于 2015-05-24T00:12:54.030 に答える
0

これが簡単なアプローチです。ニーズに対して十分な速度ではないかもしれませんが、開始する場所です。

seat問題を単純化し、列row、col、およびを持つテーブルを考えてみましょうtaken。最初の 2 つは整数で、もう 1 つはブール値です。普遍的に偽である特定のサイズの長方形の値rowと制約を見つけたいと考えています。四角形を移動し、その中の値の合計を記録するクエリを試してみましょう。必要な長方形の合計はゼロになります。coltakentaken

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、開いているブロックの左上隅を示します。最後の癖の 1 つは、座席の右端または下端に近づきすぎている左上隅を除外することです。これは、それらの合計が人為的に減少するためです (テストされた長方形は座席の端に対してクリップされます)。2x2 ブロックの場合、これは と を意味row < max(row)しcol < max(col)ます。

15 の隣接する座席を見つける場合、15x1、1x15、3x5、および 5x3 の長方形を探します。上記のクエリを、四角形の幅と高さのパラメーターを受け取るストアド プロシージャにし、一致するサイズが見つかるまでそれらのサイズで呼び出すことができます。

于 2011-08-14T04:39:44.083 に答える
0 
    $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 :)
于 2011-08-09T22:05:31.013 に答える
0

行ごとにクエリをUNION作成し、プログラムでクエリを作成できる場合はそれを組み合わせてから、同じクエリを X 回使用して、それらを追加し続けますUNION。

mysqlのマニュアルより

UNION は、複数の SELECT ステートメントの結果を 1 つの結果セットに結合するために使用されます。

于 2011-08-11T06:12:05.297 に答える
0

まず、ほとんどの会場は (たとえ概算であっても) 正方形のグリッドにマッピングできると仮定します。座席が奇妙にセットアップされたり、奇妙にオフセットされたりしていない場所。そのため、各座席の周りに最大 8 席まで配置できます。

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

基本的に、「シート グラフ」を作成し、クエリのニーズに応じてそれを実行できるようになります。次に、クエリを作成して特定の形状またはブロックを取得できます。

3x3 グリッドは、すべての方向に直接リンクされた座席も開いているオープン シートを選択することで構成されます。はい、8 つの 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: 使用しているエンジンによっては、空間機能が組み込まれている場合があります。

幸運を。

于 2011-08-14T03:54:14.317 に答える