-1

So let me describe the problem of my project Module:

I have a room of capacity 50.

10 rows 5 columns.

I have 6 different flavors available, and an unlimited amount of elements for each flavor.

I need to make a seating Plan so that no one of same flavor sits nearby (front - back - diagonal).

What are the best Sets of algorithm I can use to solve this problem?

And if possible please describe the steps of the algorithm.

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158
Shrijan Tiwari
  • 673
  • 6
  • 17
  • 1
    Need more information about the input: How many of each flavour are you given? Is there guaranteed to be a solution for the given input? – ryanpattison Apr 21 '15 at 21:31
  • You don't define "best" here, but I assume your goal is to minimize the number of flavors adjacent to each other? – Mooing Duck Apr 21 '15 at 21:43
  • Since you tagged this as a genetic-algorithm ... http://stackoverflow.com/questions/1538235/what-are-good-examples-of-genetic-algorithms-genetic-programming-solutions/1591577#1591577 – Adrian McCarthy Apr 21 '15 at 21:56
  • I think this is a _terrible_ problem for a genetic algorithm :/ That tag should be removed, not sure why it's here. – Mooing Duck Apr 21 '15 at 22:05
  • Are there unlimited amounts of each flavor? Or are there a specific amount of each that total to 50? – Mooing Duck Apr 21 '15 at 23:00
  • It sounds like a bin-packing problem. The examples discussed in the OptaPlanner user guide might be useful: http://docs.jboss.org/optaplanner/release/6.2.0.Final/optaplanner-docs/html_single/index.html#quickStart – Steve Apr 22 '15 at 07:31
  • I have unlimited supply of the flavors ... – Shrijan Tiwari Apr 22 '15 at 14:52

3 Answers3

1

Algorithm

For this specific example, you can just use greedy algorithm. Iterate over rows and columns and at each seat set any flavor that doesn't clash with already seated flavors.

Proof

xxxxxxxxxx
xxxxxxxxxx
xxxo......
..........
..........

x - already seated
o - currently seating
. - empty

Lets say we iterate in row by row, left to right fashion. When we are making new seating, this place has at most 4 already seated neighbors (look at the image above). As we have 6 flavors, there will always exist one, which is different to all others. As this is true for every seating we make, we can fill all 50 spaces.

Generalisation

For general values, this problem might be rather tricky, I dare to claim even NP-hard.

Neithrik
  • 2,002
  • 2
  • 20
  • 33
  • 1
    I thought of this as well, but there's a problem. When placing the last seat(s), it's actually fairly likely that they will conflict. This occurs even when you prioritize flavors with more "elements" remaining. – Mooing Duck Apr 21 '15 at 22:02
  • That should not happen. You should always have 3 choices for last seat. – Neithrik Apr 21 '15 at 22:52
  • It appears that half the answers are assuming an unlimited amount of each flavor, and you seat 50. If this is true, you're right. The other half are assuming there are 50 elements to be seated, divided amongst 6 flavors. If this is true, you're wrong. OP is unclear as to which of these is accurate, so I removed my downvote. – Mooing Duck Apr 21 '15 at 23:03
  • But 50 is not divisible by 6, so I thought that can't be the case. – Neithrik Apr 22 '15 at 09:03
  • divisibility is irrelevant. It could be there's six flavors A, B, C, D, E, and F. And there is 30 A, 12 Bs, 4 Cs, 3 Ds, and a single E. OTOH OP has clarified that your interpretation was indeed the correct one. So +1. – Mooing Duck Apr 22 '15 at 16:28
1

A good set of algorithms are graph coloring, specifically vertex coloring algorithms. You need to think of the chairs as vertices with edges to all neighboring chairs.

st.eve
  • 114
  • 1
  • 4
  • 1
    This doesn't sound like graph colouring. Seating people implies you don't get to choose *what* people must get a seat, and instead there is a limited supply of different "flavours". If any number of each flavour is available then it is a trivial graph colouring problem (seat odd rows as ABABA and even rows as CDCDC). – ryanpattison Apr 21 '15 at 22:48
  • The requirements did not say anything on limited quantities for each flavor. The requirement was just for a seating plan where two flavors were not adjacent (horizontally, vertically, or diagonally). In this case I think the graph coloring is more appropriate (just my opinion though). – Gentian Kasa Apr 22 '15 at 07:16
1

The given problem is a Constraint Satisfaction Problem. In particular (using the terminology used here):

  1. The set of variables X is made of the seats (in your case we have 50 seats correspond to a set of 50 variables, one for each seat)
  2. The sets of domain values D is a set of 50 domains (1 for each variable), each of which contains a set of 6 values (the 6 different flavours).
  3. The set of constraints is made up like this C1 := (X[0,0] != X[0,1]); C2 := (X[0,0] != X[1,0]); C3 := (X[0,0] != X[1,1]) and so on.

Personally I would suggest to use Forward Checking in order to reduce complexity.

The resulting algorithm (a simplified version without rollback of the assignment as it's unnecessary for this specific problem) would look something like this:

initialize_domains_for_each_variable;   // set the 6 available flavours

for(int i = 0; i < 10; i++){
    for(int j = 0; j < 5; j++){
        seats[i,j].flavour = seats[i,j].possible_flavours[0];
        // look ahead and eliminate possible conflicts
        remove_this_flavour_from_surrounding_seats_possible_flavours;
    }
}

Doing it like this will ensure that no conflict arises because you'll have at least 2 available flavours for each seat. We visit the seats from left to right and from top to bottom so for each seat we have to check which assignment does not conflict with the previously completed assignments. In the general case we will have:

seat[i,j].available_flavours = available_flavours - seat[i-1,j+1].flavour - seat[i-1,j].flavour - seat[i-1,j-1].flavour - seat[i,j-1].flavour

that has 2 items. In the borders of the matrix you will have more available flavours because the items it can conflict with are 2 (in the case of a left border), 3 (in the case of a right border not in the first row), or 1 (in the case of the top right element, the right border of the first row).

Be aware that using the above algorithm will only use 5 flavours (the bare minimum). If you have the necessity of using 6 flavours you will have to adapt the algorithm.

Gentian Kasa
  • 776
  • 6
  • 10