Combinatorics problem, room configurations

Say I have a bunch of hotel rooms, suitable for 1,2 or 3 persons.

A group of 4 persons would like to book and I want to present them with all the possible configurations, since different configurations have different prices.

Possible combinations include:

• 4 * 1 person roo开发者_如何学JAVAm
• 2 * 2 person room
• 1 * 3 person room + 1 * 1 person room
• etcetera, etcetera

How would I go about calculating the different groupings?

An added complexity is that some of these persons may be children, which should always be combined with adults in a room. I figured I should just calculate all combinations and filter out the ones who don't satisfy this constraint.

Any hints, tips or pointers?

The way the problem is phrased suggests that the number of room types is small, and so is the largest required group size.

With this in mind, I'd use depth-first search with memoization. In Python:

@memoized
def search(n, room_types):
  ret = set()
  for t in room_types:
    if t >= n:
      ret.add((t,))
    else:
      for cfg in search(n - t, room_types):
        if sum(cfg) >= n:
          ret.add(cfg)
        else:
          ret.add(tuple(sorted(list(cfg) + [t])))
  return ret

print sorted(search(4, (1, 2, 3)))

This produces:

[(1, 1, 1, 1), (1, 1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

@memoized comes from here.