Databases
StackOverflow2013
Postsdbo
POBetter method of finding every possible combination of the partitioned sets
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBetter method of finding every possible combination of the partitioned sets
    primarykey
    data
    text
    <p>I need to find every possible combination of N sets of X length with no duplicates and in a particular order, e.g.</p> <pre><code>input: [["A"], ["B"], ["C"]] output: [["A","B","C"],["A","B"],["A","C"],["B","C"],["A"],["B"],["C"]] </code></pre> <p>Rules:</p> <ul> <li>The number or size of partitions is not fixed.</li> <li>Only one member from each partition in each combination.</li> <li>Combinations with more members are higher precedence.</li> <li>Members earlier on in the input are higher precedence than members later on.</li> </ul> <p>Another example with larger sets:</p> <pre><code>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"]] </code></pre> <p>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?</p> <p>Here's what I have already:</p> <pre class="lang-php prettyprint-override"><code>$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 &lt; $members; $i++) { $b = sprintf("%0".$count."b",$i); $out = array(); for ($j = 0; $j &lt; $count; $j++) { if ($b[$j] == '1') { $out[] = $in[$j]; } } if (count($out) &gt;= $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) &gt; array_sum($b)) ? 1 : -1; } return (count($a) &lt; 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) &lt; 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 "&lt;br /&gt;output: ".json_encode(combinations($test2)); </code></pre> <p>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.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USPhil Moorhouse
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBetter method of finding every possible combination of the partitioned sets
      1. USBytemain
      1. VTFavorite
    2. VO
      singulars
      1. POBetter method of finding every possible combination of the partitioned sets
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload