..

Seating for a wedding

In two weeks I will be getting married and my future wife and I are scrambling to make the final arrangements for the big day. Part of this involves figuring out the seating for the wedding. We have 115 people to sit and each table fits up to 8 people. Of course we wanted to sit families together, even if it meant having more than the minimum number of tables necessary. We needed to determine how many tables were needed and how many would sit at each table. For example, if we chose 15 tables a couple of seating options would be

6 6 7 8 8 8 8 8 8 8 8 8 8 8 8

and

6 7 7 7 8 8 8 8 8 8 8 8 8 8 8

The total of both those options equals 115.

We wanted to see what our options were and I quickly realized we had a permutation problem. But why struggle through this menial task when it is more suitable for a machine? I took this opportunity and turned to Common Lisp to compute the answers.

I decided to make use of the Common Lisp Screamer library which provides constraint programming for Common Lisp. The code to compute the permutations for 15 tables is as follows:

(defparameter *number-of-people* 115)
(defparameter *maximum-number-of-people-per-table* 8)
(defparameter *minimum-number-of-people-per-table* 6)

(defmacro screamer-create-list-of-ints (num)
  `(list ,@(loop for i from 1 to num collect
		 '(screamer:an-integer-between *minimum-number-of-people-per-table*
		   *maximum-number-of-people-per-table*))))

(screamer:all-values
		   (let* ((vars (screamer-create-list-of-ints 15)))
		     (screamer:assert! (screamer:applyv #'<= vars))
		     (screamer:assert! (screamer:=v *number-of-people*
		                                    (screamer:applyv #'+ vars)))
		     vars))

The macro to create the variables was necessary because for some reason using a loop at execution time to create the variables hung the program.

After creating a list of integer variables, we make a couple of assertions. The first is that the list should be in ascending order. The second is that the sum of the list should equal the number of people attending our wedding, 115 in this case. The screamer function “all-values” will execute the code until all solutions are found.

The results are as follows:

 15 tables:

 6 6 7 8 8 8 8 8 8 8 8 8 8 8 8
 6 7 7 7 8 8 8 8 8 8 8 8 8 8 8
 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8

 16 tables:

 6 6 6 6 6 6 7 8 8 8 8 8 8 8 8 8
 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8
 6 6 6 6 7 7 7 7 7 8 8 8 8 8 8 8
 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8
 6 6 7 7 7 7 7 7 7 7 7 8 8 8 8 8
 6 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8
 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8

 17 tables:

 6 6 6 6 6 6 6 6 6 6 7 8 8 8 8 8 8
 6 6 6 6 6 6 6 6 6 7 7 7 8 8 8 8 8
 6 6 6 6 6 6 6 6 7 7 7 7 7 8 8 8 8
 6 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8
 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 8 8
 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 8
 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7

 18 tables:

 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 8 8 8
 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 8 8
 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 8
 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7