PHP : Combinations without permutations

user_6603862 0
Viewed 92

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?

combinations recursion sum php
1 Answers

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
        )

)
user_12481140
Related