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.