PHP find all combinations to a sum in inner array

Question

I'm writing a PHP script for available rooms in a hotel. I want every combination for a group (i.e. 4 person). This is my array.

$room_array = array(
    array(
        "title"         => "1 person room",
        "room_for"      => 1,
        "price"         => 79
    ),
    array(
        "title"         => "2 person room with other",
        "room_for"      => 1,
        "price"         => 69
    ),
    array(
        "title"         => "2 person room alone",
        "room_for"      => 1, 
        "price"         => 89
    ),
    array(
        "title"         => "2 person",
        "room_for"      => 2,
        "price"         => 69
    ),
    array(
        "title"         => "3 person",
        "room_for"      => 3,
        "price"         => 69
    )
);

Possible outcome:

• 4x 1 person room
• 4x 2 person room with other
• 3x 1 person room + 1x 2 person room with other
• 2x 2 person room
• 1x 3 person room + 1x 1 person room

etc. etc.

This calls for a recursive function. But every example I looked at doesn't work with counting in the inner array. The closest i found was this question:

Finding potential combinations of numbers for a sum (given a number set to select from)

But i didn't get de solution to work..

UPDATE:

Hi, thanks for all the answers. Really helped me in finding the best practice. In the meantime, the assignment has changed a little so I can't answer my own original question. My problem is solved. Thanks again for the help!

Answer 1

My answer below will get you partway there.

---

Resources

I borrowed some code logic from this answer. To quote the answer (in case of future removal), please view below.

You can try

echo "<pre>";
$sum = 12 ; //SUM
$array = array(6,1,3,11,2,5,12);
$list = array();
# Extract All Unique Conbinations
extractList($array, $list);
#Filter By SUM = $sum     $list =
array_filter($list,function($var) use ($sum) { return(array_sum($var) == $sum);});
#Return Output
var_dump($list);

Output

array
  0 => array
    1 => string '1' (length=1)
    2 => string '2' (length=1)
    3 => string '3' (length=1)
    4 => string '6' (length=1)
  1 => array
    1 => string '1' (length=1)
    2 => string '5' (length=1)
    3 => string '6' (length=1)
  2 => array
    1 => string '1' (length=1)
    2 => string '11' (length=2)
  3 => array
    1 => string '12' (length=2)

Functions Used

function extractList($array, &$list, $temp = array()) {
    if(count($temp) > 0 && ! in_array($temp, $list))
        $list[] = $temp;
    for($i = 0; $i < sizeof($array); $i ++) {
        $copy = $array;
        $elem = array_splice($copy, $i, 1);
        if (sizeof($copy) > 0) {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            extractList($copy, $list, $add);
        } else {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            if (! in_array($temp, $list)) {
                $list[] = $add;
            }
        }
    }
}

---

My answer

The code below uses the code referenced above. I changed the return functionality of the array_filter function to map it to your needs.

The only thing left for you to do is change the function so that it can catch multiple of the same type of room. At the moment, the code below will only output 1 of each type of room (as per the code referenced above). An easy way to get around this would be to multiply the array values you send to the function by the number of guests you are searching for rooms, but up to the amount of rooms available. So: if you are looking to book for 4 guests and you have no single rooms remaining and only 1 double room, your best match result would have to be a 2 person room and a 3 person room. I've added some brief functionality to add this (it's commented out), although I have not tested it. It will likely take a while to process that as well so if you're looking for a quicker method, you're gonna have to use a better algorithm as already mentioned in previous comments/answers or solve P vs NP

The code below also gives you the option to toggle a value of $exact. This value, if set to true, will return only matches exactly equal to the number of guests, and if set to false will return all matches that equal to at least the number of guests.

<?php

class Booking {
    private $minGuests = 1;
    protected $guests = 1;
    protected $rooms = [];

    public function getRoomCombinations(bool $exact = true) {
        $guests = $this->guests;
        $list = [];
        $rooms = $this->rooms;

        /*for($i = 0; $i < $guests-1; $i++) {
            $rooms = array_merge($rooms, $this->rooms);
        }
        asort($rooms);*/
        $this->extractList($rooms, $list);

        $result = array_filter($list, function($var) use ($guests, $exact) {
            if($exact)
                return(array_sum(array_map(function($item) { return $item['room_for'];}, $var)) == $guests);
            else
                return(array_sum(array_map(function($item) { return $item['room_for'];}, $var)) >= $guests && count($var) <= $guests);
        });
        array_multisort(array_map('count', $result), SORT_ASC, $result);

        return $result;
    }

    private function extractList(array $array, array &$list, array $temp = []) {
        if (count($temp) > 0 && !in_array($temp, $list))
            $list[] = $temp;
        for($i = 0; $i < sizeof($array); $i++) {
            $copy = $array;
            $elem = array_splice($copy, $i, 1);
            if (sizeof($copy) > 0) {
                $add = array_merge($temp, array($elem[0]));
                sort($add);
                $this->extractList($copy, $list, $add);
            } else {
                $add = array_merge($temp, array($elem[0]));
                sort($add);
                if (!in_array($temp, $list)) {
                    $list[] = $add;
                }
            }
        }
    }

    public function setGuests(int $guests) {
        $this->guests = ($guests >= $this->minGuests ? $guests : $this->minGuests);
        return $this;
    }

    public function setHotelRooms(array $rooms) {
        $this->rooms = $rooms;
        return $this;
    }
}

$booking = (new Booking())
    ->setGuests(4)
    ->setHotelRooms([
        [
            "title"         => "1 person room",
            "room_for"      => 1,
            "price"         => 79
        ],
        [
            "title"         => "2 person room with other",
            "room_for"      => 1,
            "price"         => 69
        ],
        [
            "title"         => "2 person room alone",
            "room_for"      => 1, 
            "price"         => 89
        ],
        [
            "title"         => "2 person",
            "room_for"      => 2,
            "price"         => 69
        ],
        [
            "title"         => "3 person",
            "room_for"      => 3,
            "price"         => 69
        ]
    ]);
echo '<pre>' . var_export($booking->getRoomCombinations(true), true) . '</pre>';
?>

Answer 2

If you need all the combinations then you can use an backtracking iterative algorithm (depth path).

In summary:

1. Type of tree: binary tree because all the levels can contain a solution when the number of persons contabilized = objetive

   Binary tree

2. Algorithm functions You need to increment the cont every time that a level is generated with the number of persons of the level and decrement when you change your track (exploring brothers or back)

solution: array[0..levels-1] values {0 (node not selected) ,1 (node selected)}

solution[0] = 1 -> You choose that "1 person room" belongs to the solution

solutions: list/array of objects and every object contains array of titles of rooms

function Backtracking ()
    level:= 1
    solution:= s_initial
    end:= false
    repeat
         generate(level, solution)
         IF solution(level, solution) then
           save_solution
         else if test(level, solution) then
            level:= level+ 1
         else
            while NOT MoreBrothers(level, solution)
               go_back(level, s)

    until level==0

2.1. Generate: generate next node

2.2. Solution: test if it's a solution

2.3. Critery: if we must continue by this track or bound

2.4. MoreBrothers: if there are nodes without check at this level

2.5. Backtrack: all the nodes at this level were explored

2.6. Save solution: add to the solutions array your object that contains strings

Answer 3

$room_array = array(
    array(
        "title"         => "1 person room",
        "room_for"      => 1,
        "price"         => 79
    ),
    array(
        "title"         => "2 person room with other",
        "room_for"      => 1,
        "price"         => 69
    ),
    array(
        "title"         => "2 person room alone",
        "room_for"      => 1,
        "price"         => 89
    ),
    array(
        "title"         => "2 person",
        "room_for"      => 2,
        "price"         => 69
    ),
    array(
        "title"         => "3 person",
        "room_for"      => 3,
        "price"         => 69
    )
);

// Gets rooms based on a given number of guests
function get_possible_rooms($num_guests) {
    global $room_array;
    $possible_rooms = [];

    foreach ($room_array as $room) {
        if ($num_guests <= $room['room_for']) {
            $possible_rooms[] = $room['title'];
        }
    }

    return $possible_rooms;
}

// Gets the available room capacities
function get_room_capacities() {
    global $room_array;
    $capacities = [];

    foreach ($room_array as $room) {
        $capacities[] = $room['room_for'];
    }

    return array_unique($capacities);
}

// Gets the different combinations of groups of guests based on the room capacities
function get_guest_assignments($remaining_guests, $parent_id = '', $num_guests, &$result) {
    $room_capacities = get_room_capacities();

    for ($i = 1; $i <= $remaining_guests; ++$i) {
        if (in_array($i, $room_capacities)) {
            $parent_guests = (isset($result[$parent_id])) ? $result[$parent_id] : 0;
            $result[$parent_id . $i] = $parent_guests + $i;

            for ($j = 1; $j <= $remaining_guests - $i; ++$j) {
                // Recursively get the results for children
                get_guest_assignments($j, $parent_id . $i, $num_guests, $result);
            }
        }
    }

    if ($remaining_guests === 1 && $parent_id !== '') {
        // If it reaches the end and it does not fulfill the required number of guests,
        // mark it for removal later
        if ($result[$parent_id] < $num_guests) {
            $result[$parent_id] = null;
        }
    }

    // This is the last recursion
    if ($result[$parent_id . '1'] === $num_guests) {
        // Remove duplicates. 
        // To do this, we need to re-sort the keys (e.g. 21 becomes 12) and call array_unique()
        // I admit this is a bit sloppy implementation.
        $combinations = [];

        foreach ($result as $key => $value) {
            if ($value !== null) {
                $nums = str_split($key);
                sort($nums);
                $combinations[] = implode('', $nums);
            }
        }

        $result = array_unique($combinations);
    }
}

// Gets the rooms for each group of guest
function get_room_assignments($guest_str) {
    $rooms = [];

    for ($i = 0; $i < strlen($guest_str); ++$i) {
        $num_guests = intval(substr($guest_str, $i, 1));
        $rooms[] = get_possible_rooms($num_guests);
    }

    return $rooms;
}

//----------
// RUN
//----------

$guests = 4;
$result = [];

get_guest_assignments($guests, null, $guests, $result);

foreach ($result as $guest_combi) {
    $assignments = get_room_assignments($guest_combi);

    // Printing output
    echo 'Guest Combination ' . $guest_combi . "\n";
    echo json_encode($assignments, JSON_PRETTY_PRINT);
    echo "\n\n";
}

The output will look something like this:

...
Guest Combination 13
[
    [
        "1 person room",
        "2 person room with other",
        "2 person room alone",
        "2 person",
        "3 person"
    ],
    [
        "3 person"
    ]
]
...

"Guest combination 13" means the 4 guests will be split into groups of 1 and 3 persons.

Output is an array of possible rooms for each group. So in the example, the group of 1 can book 1 person room, 2 person room with other, ... 3 person room. And the group of 3 can book 3 person room.

—

Other notes:

• I know we hate global but doing this just for brevity. Feel free to modify.
• There's a shorter way to code this, but this implementation makes it easier to debug since guest combinations are used as keys.