php - 获取符合特定范围条件的可能组合(大小为 N)

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)

这意味着，每个组合都必须以 9 开​​头(如我们 $start = 9 )并尝试达到 16(即 $end = 16 IF AVAILABLE ) 在每个组合中有 n 元素(这里，n = 3)。

我在网上搜索了很多问题并尝试了一些自己的东西。但不幸的是，他们甚至没有得到更接近解决方案的标题。我正在处理的问题与上面的示例不同，而且很复杂。

Answer 1

您需要多次迭代执行此操作:

1. 创建一个递归函数，简单地构建大小 n 的组合超出给定数组。
   (作为预处理步骤，您要将 9-11 更改为 [9,11] 以便您稍后可以轻松检查范围，例如 >= $range[0] 最小值 ... <= $range[1] 最大值)
   • PHP algorithm to generate all combinations of a specific size from a single set将有助于这一步
2. 然后添加条件以过滤掉不以 $start 开头的组合.
3. 然后添加条件过滤掉那些不以$end结尾的

---

编辑:一个好的开始可能是:

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;
}

用作:

$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 ', ';
}

输出:

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,