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

Question

I have a function which gives me all combination of values, in an array with fixed length a fixed sum :

// $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]

I need to generate all possible combinations adding another parameter : a reference array $ref whose values are considered as limits.

All combination $combi generated must respect the rule : $combi[x] <= $ref[x]

For example with [2,1,1,0] we can't have [0,0,2,0], [0,2,0,0].

I created the following function to add the new parameter :

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

This function makes me generate and filter a big list of combinations with the new parameter. I need to have a function which generates only the combinations I want. Do you have ideas ?

Sammitch · Accepted Answer · 2021-01-15 23:23:23Z

Honestly, the simplest solution would be to generate the full set of possibilities and then filter the unsuitable results afterwards. Trying to apply a mask over a recursive function like this is going to be a giant pile of work, which will likely only complicate and bog down the process.

That said, there are a couple ways in which I think you could optimize your generation.

Caching

Write a simple cache layer so that you're not constantly re-computing smaller sub-lists, eg:

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

You might want to set a lower limit on the size of a list that will be cached so you can balance between memory usage and CPU time.

Generators: https://www.php.net/manual/en/language.generators.overview.php

As it stands the function is basically building out many redundant subtrees of combinations in-memory, and you're likely to run into memory usage concerns depending on how broad the sets of possibilities become. Rather than something like:
```
function foo() {
    $result = [];
    for(...) {
        result[] = foo(...);
    }
    return $result;
}
```
Something like:
```
function foo() {
    for(...) {
        yield foo(...);
    }
}
```
Now you're essentially only ever holding in memory a single copy of the sublist segments you're currently interested in, and a handful of coroutines, rather than the whole subtree.

Thank you but very much, but I need to find a solution which doesn't force me to create useless combinations.

Romain Charles · Accepted Answer · 2021-01-16 21:10:49Z

0

I have found a solution, here it is :

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

answered Jan 16, 2021 at 21:10

Romain Charles

791 silver badge8 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related