Better method of finding every possible combination of the partitioned sets

https://stackoverflow.com/questions/10250058

02-06-2021
|

Question

I need to find every possible combination of N sets of X length with no duplicates and in a particular order, e.g.

input:  [["A"], ["B"], ["C"]]
output: [["A","B","C"],["A","B"],["A","C"],["B","C"],["A"],["B"],["C"]]

Rules:

The number or size of partitions is not fixed.
Only one member from each partition in each combination.
Combinations with more members are higher precedence.
Members earlier on in the input are higher precedence than members later on.

Another example with larger sets:

input:  [["A","B"],["C","D","E"],["F"]]
output: [["A","C","F"],["A","D","F"],["A","E","F"],["B","C","F"],["B","D","F"],["B","E","F"],["A","C"],["A","D"],["A","E"],["B","C"],["B","D"],["B","E"],["A","F"],["B","F"],["C","F"],["D","F"],["E","F"],["A"],["B"],["C"],["D"],["E"],["F"]]

I've managed to get the output I want by combining the output of a power set function with a cartesian product function, but the resulting code isn't very concise or pretty. I was wondering if this could be better done with recursion?

Here's what I have already:

$test = json_decode('[["A"]]');
$test1 = json_decode('[["A"], ["B"], ["C"]]');
$test2 = json_decode('[["A", "B"], ["C", "D", "E"], ["F"]]');

/**
 * Returns a power set of the input array.
 */                   
function power_set($in, $minLength = 1) {
  $count = count($in);
  $members = pow(2,$count);
  $return = array();

  for ($i = 0; $i < $members; $i++) {
    $b = sprintf("%0".$count."b",$i);
    $out = array();

    for ($j = 0; $j < $count; $j++) {
      if ($b[$j] == '1') {
        $out[] = $in[$j];
      }
    }
    if (count($out) >= $minLength) {
      $return[] = $out;
    }
  }

  return $return;
}

/**
 * Returns the cartesian product of the input arrays.
 */
function array_cartesian() {
  $_ = func_get_args();

  if(count($_) == 0) {
    return array(array());
  }

  $a = array_shift($_);
  $c = call_user_func_array(__FUNCTION__, $_);
  $r = array();

  foreach($a as $v) {
    foreach($c as $p) {
      $r[] = array_merge(array($v), $p);
    }
  }

  return $r;
}

/**
 * Used with usort() to sort arrays by length, desc.
 * If two arrays are the same length, then a sum of 
 * their keys is taken, with lower values coming first.
 */
function arraySizeDesc($a, $b) {
  if(count($a) === count($b)) {
    if(array_sum($a) === array_sum($b)) {
      return 0;
    }

    return (array_sum($a) > array_sum($b)) ? 1 : -1;
  }

  return (count($a) < count($b)) ? 1 : -1;
}

/**
 * Calculates a powerset of the input array and then uses
 * this to generate cartesian products of each combination
 * until all possible combinations are aquired.
 */
function combinations($in) {
 $out = array();
 $powerSet = power_set(array_keys($in));
 usort($powerSet, 'arraySizeDesc');

 foreach($powerSet as $combination) {
   if(count($combination) < 2) {
     foreach($in[$combination[0]] as $value) {
       $out[] = array($value);
     }
   } else {
     $sets = array();

     foreach($combination as $setId) {
       $sets[] = $in[$setId];
     }

     $out = array_merge($out, call_user_func_array('array_cartesian', $sets));
   }
 }

 return $out;
}

echo "input: ".json_encode($test2);
echo "<br />output: ".json_encode(combinations($test2));

I realise the size of the output could grow very rapidly, but the input should only usually contain 1-5 sets of 1-50 members, so it doesn't need to deal with massive sets.

Solution

Essentially, your approach has been to generate the power-set of the input and then post-process that to arrive at your desired output.

One can approach it differently by attempting to solve it directly. One solution that came to me is the following.

Given an input A = [ A₁, ...], assume the problem is already solved for A \ A₁. Call this solution S'. How can we transform S' to the solution S for the whole of A? This is essentially by making two copy of S'. We distribute elements of A₁ into the first copy. Let's call the new sequence S''. Thus the solution to A becomes simply a concatenation of S'' and S'.

Algorithmically,

Input: A = [ A₁, A₂, ..., A_n]



combine(A, i, n):


if n < i
return []
if n == i 
return singletons(A_i)
S' = combine(A, i + 1, n)
S'' = [a, S'], for each a in A_i

return [S'', S']

The function singletons returns a family of one-element subsets of the input set. So, if it take the input [1, 2, 3], it'll return [[1], [2], [3]].

The approach should be clear if you ignore some loose usage of concatenation of sequences here and there ...

Good luck!

OTHER TIPS

Try

$test = array ();
$test [0] = json_decode ( '[["A"]]', true );
$test [1] = json_decode ( '[["A"], ["B"], ["C"]]', true );
$test [2] = json_decode ( '[["A", "B"], ["C", "D", "E"], ["F"]]', true );


echo "<pre>" ;
$set = array ();
getSet ( $test, $set );
$set = array_values(array_unique($set));
$return = powerSet($set,1,3);
print_r ($return);

Output

Functions used

function powerSet($in, $minLength = 1, $max = 10) {
    $count = count ( $in );
    $members = pow ( 2, $count );
    $return = array ();
    for($i = 0; $i < $members; $i ++) {
        $b = sprintf ( "%0" . $count . "b", $i );
        $out = array ();
        for($j = 0; $j < $count; $j ++) {
            if ($b {$j} == '1')
                $out [] = $in [$j];
        }
        if (count ( $out ) >= $minLength && count ( $out ) <= $max) {
            $return [] = $out;
        }

    }
    return $return;
}

function getSet($array, &$vals) {
    foreach ( $array as $key => $value ) {

        if (is_array ( $value )) {

            getSet ( $value, $vals );

        } else {

            $vals [] = $value;
        }
    }

    return $vals;
}

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow