Calculating all possible combinations of people in hotel rooms

Viewed 229

Given I have the following combination of people wanting to stay in a hotel;

  • 3 Adults
  • 6 Children

How can I work out all of the different combinations of rooms that could be selected based on the above, where a child cannot be alone in a room and all people must be used? (Note: this is in a PHP application).

For example, the above could be broken down like;

  • 1 room with everyone in
  • 2 rooms with;
    • 1 adult 6 children
    • 1 adult 0 children
  • 2 rooms with;
    • 1 adult 5 children
    • 1 adult 1 child
  • etc...

Ideally this should result in a data structure along the lines of;

[
    // Room combination
    [
        // Individual Room
        [
            'adults' => 3,
            'children' => 6
        ]
    ],
    [
        [
            'adults' => 2,
            'children' => 5
        ],
        [
            'adults' => 1,
            'children' => 0
        ]
    ]
]

I have the following code that handles adults however I cannot think how to introduce the concept of children into this.

public function partition($left, $last = 1, $ar = [], &$partitions = [])
    {
        if ($left == 0) {
            array_push($partitions, $ar);
        }

        for ($n = $last; $n <= $left; $n++) {
            $b = $ar;
            array_push($b, $n);
            array_merge($partitions, $this->partition($left - $n, $n, $b, $partitions));
        }
        return $partitions;
    }
2 Answers
Related