PHP : Combinations without permutations

Question

This code gives me every possible combination of n values with a length of x, to have a sum of n.

function GETall_distri_pres($n_valeurs, $x_entrees, $combi_presences = array()) {
    if ($n_valeurs == 1) { 
        $combi_presences[] = $x_entrees;
        return array($combi_presences);
    }

    $combinaisons = array();

    // $tiroir est le nombre de chaussettes dans le tiroir suivant
    for ($tiroir = 0; $tiroir <= $x_entrees; $tiroir++) {
        $combinaisons = array_merge($combinaisons, GETall_distri_pres(
            $n_valeurs - 1,
            $x_entrees - $tiroir,
            array_merge($combi_presences, array($tiroir))));
    }
    return $combinaisons;
}

I need to generate only unique distributions for example not having [2,1,1,0] and [1,2,1,0], only [2,1,1,0].

var_dump(GETall_distri_pres(3,3)) will give :

array (size=10)
  0 => 
    array (size=3)
      0 => int 0
      1 => int 0
      2 => int 3
  1 => 
    array (size=3)
      0 => int 0
      1 => int 1
      2 => int 2
  2 => 
    array (size=3)
      0 => int 0
      1 => int 2
      2 => int 1
  3 => 
    array (size=3)
      0 => int 0
      1 => int 3
      2 => int 0
  4 => 
    array (size=3)
      0 => int 1
      1 => int 0
      2 => int 2
  5 => 
    array (size=3)
      0 => int 1
      1 => int 1
      2 => int 1
  6 => 
    array (size=3)
      0 => int 1
      1 => int 2
      2 => int 0
  7 => 
    array (size=3)
      0 => int 2
      1 => int 0
      2 => int 1
  8 => 
    array (size=3)
      0 => int 2
      1 => int 1
      2 => int 0
  9 => 
    array (size=3)
      0 => int 3
      1 => int 0
      2 => int 0

Do you have any ideas?

Can you give an example of the inputs?

El_Vanja
– El_Vanja

2020-12-23 10:26:58 +00:00
Commented Dec 23, 2020 at 10:26 — El_Vanja
– El_Vanja, Commented Dec 23, 2020 at 10:26
I just added an example, thank you.

Romain Charles
– Romain Charles

2020-12-23 10:35:19 +00:00
Commented Dec 23, 2020 at 10:35 — Romain Charles
– Romain Charles, Commented Dec 23, 2020 at 10:35

arkascha · Accepted Answer · 2020-12-23 11:33:56Z

2

This would be an approach: before returning the computed set you filter them by creating a fresh associative array, using the normalized permutations as keys. That will result in permutations overwriting themselves, so that only one will get preserved:

<?php

function GETall_distri_pres($n_valeurs, $x_entrees, $combi_presences = array()) {
    if ($n_valeurs == 1) { 
        $combi_presences[] = $x_entrees;
        return array($combi_presences);
    }

    $combinaisons = array();

    // $tiroir est le nombre de chaussettes dans le tiroir suivant
    for ($tiroir = 0; $tiroir <= $x_entrees; $tiroir++) {
        $combinaisons = array_merge($combinaisons, GETall_distri_pres(
            $n_valeurs - 1,
            $x_entrees - $tiroir,
            array_merge($combi_presences, array($tiroir))));
    }
    
    // filter out permutations
    $filteredCombinations = [];
    array_walk($combinaisons, function($entry) use(&$filteredCombinations) {
        arsort($entry);
        $filteredCombinations[join('', $entry)] = $entry;
    });
    return array_values($filteredCombinations);
}

$result = GETall_distri_pres(3, 3);

print_r($result);

The output obviously is:

Array
(
    [0] => Array
        (
            [0] => 3
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 2
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 1
            [1] => 1
            [2] => 1
        )

)

edited Dec 23, 2020 at 11:33

answered Dec 23, 2020 at 11:28

arkascha

43.2k8 gold badges61 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Romain Charles Over a year ago

You're the boss it works thank you!That being done, don't you think there would be a function which could generate without having to filter ?

arkascha Over a year ago

Certainly possible, you'd just have to take care not to just merge the functions numerical result arrays, but return an associative array along the same strategy as I implemented in the filter passage. And another details you might want to think about: recursive algorithms as you implemented one here are not exactly efficient. Maybe you want to think about implementing a solution with scales in a linear manner instead?

Collectives™ on Stack Overflow

PHP : Combinations without permutations

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related