Get possible combinations (of size N) that match specific range criteria

Question

// Input array
$arr = [
    'A' => '9-11',
    'B' => '9-12',
    'C' => '12-14',
    'D' => '13-14',
    'E' => '15-16',
    'F' => '15-16',
    'G' => '13-14',
    'H' => '14-16'
];

// ranges
$start = 9;
$end = 16;

// Desired outputs:
A + C + E (9-11, 12-14, 15-16)
A + C + F (9-11, 12-14, 15-16)
A + C + H (9-11, 12-14, 14-16)

B + D + E (9-12, 13-14, 15-16)
B + G + F (9-12, 13-14, 15-16)
B + G + H (9-12, 13-14, 14-16)

So it means, every combination MUST start with 9 ( as we $start = 9 ) and try to get up to 16 ( ie. the $end = 16 IF AVAILABLE ) with n elements in each combination( here, n = 3).

I searched the web for many problems and tried something of myself. But unfortunately, they didn't even get a title bit closer of the solution. The problem I'm working is different from above example and complex.

Answer 1

You need to do this in multiple iterations:

1. Create a recursive function that simply builds combinations of size n out of given array.
   (as pre-processing step you want to change 9-11 into [9,11] so that you can easily check range later, e.g. >= $range[0] for min ... <= $range[1] for max)
   • PHP algorithm to generate all combinations of a specific size from a single set will help with this step
2. Just then add condition to filter out combinations that don't start with $start.
3. Then add condition to filter out those that don't end with $end

---

EDIT: A good start could be:

function appendElements($elements, & $dst) {
    foreach ($elements as $ele) $dst[] = $ele;
}

function buildTouples($map, $start, $end, $size, $currentSize, $touplesToExtend) {
    if ($currentSize == $size) return $touplesToExtend;
    if ($map === []) return [];

    $allTouples = [];
    foreach ($map as $key => $range) {
        unset($map[$key]);
        foreach ($touplesToExtend as $toupleToExtend) {
            $toupleToExtend[] = $key;
            $newTouples = 
               buildTouples($map, $start, $end, $size, $currentSize+1, [$toupleToExtend]);
            appendElements($newTouples, $allTouples);
        }
    }
    return $allTouples;
}

used as:

$map = [
    'A' => [9,11],
    'B' => [9,12],
    'C' => [12,14],
    'D' => [13,14],
    'E' => [15,16],
    'F' => [15,16],
    'G' => [13,14],
    'H' => [14,16]
];
$start = 9;
$end = 16;
$size = 3;
$touples = buildTouples($map, $start, $end, $size, 0, [[]]);

foreach ($touples as $touple) {
    foreach ($touple as $val) echo $val;
    echo ', ';
}

outputs:

ABC, ABD, ABE, ABF, ABG, ABH, ACD, ACE, ACF, ACG, ACH, ADE, ADF, ADG, ADH, AEF, AEG, AEH, AFG, AFH, AGH, BCD, BCE, BCF, BCG, BCH, BDE, BDF, BDG, BDH, BEF, BEG, BEH, BFG, BFH, BGH, CDE, CDF, CDG, CDH, CEF, CEG, CEH, CFG, CFH, CGH, DEF, DEG, DEH, DFG, DFH, DGH, EFG, EFH, EGH, FGH,