Search and Matching algorithm

Question

I am trying to come up with an algorithm to do the following:

I have total 12 cells that I need to fill until program stops. I have 3 rows and each row has 4 columns.

As an example, let me illustrate this as in airplane. So you have 3 rows and each row has 4 columns and you have window/aisle seats. Each row will have a window seat, aisle seat, aisle seat and window seat (|WA AW| Just like seat arrangement in airplane). At each iteration (different set of passengers), there would be some number of passengers (between 1 and 12) and I need to seat them closest together possible (Seat together). And I do this for next group (each iteration) until program stops (It will stop when I am done with every group).

For example, I have 3 passengers (A,B,and C) and A wants to seat in Window, B wants to seat in Aisle and C wants to seat in Window. Assuming that all the seats (all 12) are available, I could place them like |A# BC| or |CB #A| and mark the seats dirty (so I don’t pick same seats again for next passengers). And I do this for next group (iteration). I am not sure if this right forum, but if somebody can advise me how I should accomplish, I would really appreciate it.
Thanks.

Answer 1

If it's really just 12 cells, and the group sizes are known in advance, then dynamic programming is likely to be a good fit. Compute for each set of occupied seats (2^12) and each k (0 <= k <= 12) whether the first k groups can be placed appropriately to occupy exactly that set of seats. (As an optimization, k is determined by the size of the set.) At the end, work backwards: if I place the last group here, can I fit the other groups in the seats remaining? Et cetera.

Answer 2

If the input comes in order, and assuming the number of seats is always up to 12, there are only 2^12 ways the seats can be taken at each state (set of passengers). You can use this to cut down the number of states for a brute force/memoization solution.

Pseudo code:

IsSeatingPossible( mask, passengers ) =
    if ( no more passengers ) return true
    return IsSeatingPossible =
        new_mask = mask + brute force on passenger constraints
        if any IsSeatingPossible( new_mask, 
                      passengers - just processed passengers )

More explanation:

The mask is basically an array of 12 booleans, stating whether seat_i is taken for each i (you can convert the 2D (x,y) -> 1D (x) easily). Then you iterate over the possibilities. A complete seating is possible if, for this passenger set (A_1, A_2, .., A_k) each has a seat, and the rest of the passengers has seats.

So the mask that is passed in, in English, are the seats that are taken. So let's say you seat (A_1, A_2, .., A_k) in seats (x_1, x_2, .., x_k). There are a number of subsets where the passengers can sit in - bounded by N choose k, which in this case is small. This is the part you brute force on. Given a particular (x_1, x_2, .., x_k), this seating is possible if (x_1, x_2, .., x_k) has no overlap with the current mask (no conflicting seats, essentially), and that it is possible to process the rest of the passenger requests, given that the new mask, which is just the set addition of the current mask and (x_1, x_2, .., x_k). (The new sets of seats which are taken.)

This might or might not be fast enough. The neat thing is noticing that other than noting which seats are taken, and what passengers were processed, the solution the same for a certain subproblem. Therefore you can speed this up trivially by using memoization. This yields a O(N 2^N) space solution.

The mask is best implemented using a bitmask, especially for N = 12, hence the name. For the passenger request list, you probably need to just keep track of which index.

Answer 3

This is an instance of the Knapsack problem type, with previously known solutions.