获取具有固定值和和数组模型的数组的所有可能组合

Question

我有一个函数，它在一个固定长度和固定总和的数组中给出所有值的组合：

// $n_valeurs is the length of the array
// $x_entrees is the sum
    function distributions_possibles($n_valeurs, $x_entrees, $combi_presences = array()) {
        if ($n_valeurs == 1) {
            $combi_presences[] = $x_entrees;
            return array($combi_presences);
        }

        $combinaisons = array();

        // on fait appel à une fonction récursive pour générer les distributions
        for ($tiroir = 0; $tiroir <= $x_entrees; $tiroir++) {
            $combinaisons = array_merge($combinaisons, distributions_possibles(
                $n_valeurs - 1,
                $x_entrees - $tiroir,
                array_merge($combi_presences, array($tiroir))));
        }
        return $combinaisons;
    }

distributions_possibles(4,2);

// output :
[0,0,0,2]
[0,0,1,1]
[0,0,2,0]
[0,1,0,1]
[0,1,1,0]
[0,2,0,0]
[1,0,0,1]
[1,0,1,0]
[1,1,0,0]
[2,0,0,0]

我需要生成所有可能的组合并添加另一个参数：一个参考数组 $ref，其值被视为限制。

生成的所有组合 $combi 必须遵守规则：$combi[x] <= $ref[x]

例如 [2,1,1,0] 我们不能有 [0,0,2,0], [0,2,0,0].

我创建了以下函数来添加新参数：

// $distribution is the array reference
// $similitude is the sum of values
    function SETpossibilites1distri($distribution, $similitude){
        $possibilites = [];
        $all_distri = distributions_possibles(count($distribution), $similitude);

        foreach($all_distri as $distri){
            $verif = true;
            $distri_possi = [];

            for($x = 0; $x < count($distri); $x++){
                if($distri[$x] > $distribution[$x]){
                    $verif = false;
                    break;
                }

                if($distribution[$x] == 0){
                    $distri_possi[$x] = null;
                }

                elseif($distribution[$x] > $distri[$x] && $distri[$x] != 0){
                    // si c'est une valeur fixée qui informe sur la distri_cach
                    if($this->distri_cach[$x] == $distri[$x]){
                        $distri_possi[$x] = $distri[$x]+.1;
                    }

                    else{
                        $distri_possi[$x] = $distri[$x]+.2;
                    }
                }
                else{
                    $distri_possi[$x] = $distri[$x];
                }
            }
            if($verif){
                $possibilites[] = $distri_possi;
            }
        }
        return $possibilites;
    }

此功能使我可以使用新参数生成并筛选大量组合。我需要一个只生成我想要的组合的函数。你有什么想法吗？

Answer 1

老实说，最简单的解决方案是生成完整的可能性集合，然后过滤掉不合适的结果。像这样尝试在递归函数上应用掩码将是一大堆工作，这可能只会使过程复杂化并陷入困境。

也就是说，我认为有几种方法可以优化您的生成。

缓存

编写一个简单的缓存层，这样您就不会不断地重新计算较小的子列表，例如：

function cached_distributions_possibles($n_valeurs, $x_entrees, $combi_presences = array()) {
    $key = "$n_valeurs:$x_entrees";
    if( ! key_exists($key, $this->cache) ) {
        $this->cache[$key] = distributions_possibles($n_valeurs, $x_entrees, $combi_presences);
    }
    return $this->cache[$key];
}

您可能希望对将被缓存的列表大小设置下限，以便在内存使用和 CPU 时间之间取得平衡。

发电机：https://www.php.net/manual/en/language.generators.overview.php

就目前而言，该函数基本上是在内存中构建许多冗余的组合子树，并且您可能运行考虑内存使用问题，具体取决于可能性集的范围。而不是像：
```
function foo() {
    $result = [];
    for(...) {
        result[] = foo(...);
    }
    return $result;
}
```
类似于：
```
function foo() {
    for(...) {
        yield foo(...);
    }
}
```
现在，您基本上只会在内存中保存您当前感兴趣的子列表段的单个副本，以及一些协程，而不是整个子树。

Answer 2

我找到了解决办法，这里是：

function sous($dist, $d){
    $l = count($dist);
    $L = [[]];
    foreach(range(0,$l - 1) as $i){
        $K = [];
        $s = array_sum(array_slice($dist, $i+1));
        foreach($L as $p){
            $q = array_sum($p);
            $m = max($d-$q-$s, 0);
            $M = min($dist[$i], $d-$q);
            foreach(range($m, $M) as $j){
                $p_copy = $p;
                $p_copy[] = $j;
                $K[] = $p_copy;
            }
        }
        $L = $K;
    }
    return $L;
}

获取具有固定值和和数组模型的数组的所有可能组合

Get every possible combinations of an array with fixed sum of values and array model

php

arrays

combinations