the partition problem in action

Yesterday I visited Agecroft Hall, one of the niftiest places I’ve been in Richmond. A large number of people showed up for the 2pm manor tour (there were about 20 people), and one of the tour guides struggled to partition us into two equally-sized tour groups without splitting up any of the families/groups. I was so excited to see the partition problem in action that I almost said something really nerdy (I didn’t).

The tour guide partitioned us into two rather lopsided groups. Although the partition problem is NP-complete, it shouldn’t have been all that tough to optimally solve the Agecroft Hall instance of 20 people. I enjoyed the tour anyway.

[Partition problem instance = set of integers. Can S be partitioned into two subsets such that the sum of the numbers in the first subset equals the sum of the numbers in the second subset?]