StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Interesting problem! This turned out to be more complex than I thought, but it seems to work.</p> <p>Basic strategy is to first order the arrays smallest to largest (keeping track of what order they were in, so I can output the answers in the correct order).</p> <p>I keep answers in the form of an array of indexes into this sorted array of input lists.</p> <p>Now that the lists are sorted, I can store the first correct answer as array(0,1,2,...,n);</p> <p>Then I recurse into a function for trying all values in the first slot there (the 0 above) by swapping it with other values in that answer array (all the ones that aren't too big for that slot). Since I've got it sorted by size, I can move any value to the right when I'm swapping, without worrying about it being to big for that right slot.</p> <p>outputting each valid slot has some crazy indirection to undo all the sorting.</p> <p>Sorry if this looks confusing. I didn't spend much time cleaning it up.</p> <pre><code><?php # $lists is an array of arrays function noconfcombos($lists) { $lengths = array(); foreach($lists as $list) { $lengths[] = count($list); } # find one solution (and make sure there is one) $answer = array(); $sorted_lengths = $lengths; asort($sorted_lengths); $answer_order_lists = array(); $answer_order_lengths = array(); $output_order = array(); $min = 1; $max_list_length = 0; foreach($sorted_lengths as $lists_key => $list_max) { if($list_max < $min) { # no possible combos return array(); } $answer[] = $min - 1; # min-1 is lowest possible value (handing out colums starting with smallest rows) $output_order[$lists_key] = $min - 1; # min-1 is which slot in $answers corresponds to this list $answer_order_lists[] = $lists[$lists_key]; $answer_order_lengths[] = $lengths[$lists_key]; ++$min; } ksort($output_order); $number_of_lists = count($lists); $max_list_length = end($sorted_lengths); if($max_list_length > $number_of_lists) { for($i = $number_of_lists; $i < $max_list_length; ++$i) { $answer[] = $i; } $stop_at = $number_of_lists; } else { $stop_at = $number_of_lists - 1; } # now $answer is valid (it has the keys into the arrays in $list for the # answer), and we can find the others by swapping around the values in # $answer. $ret = array(); $ret[] = noconfcombos_convert($answer, $answer_order_lists, $output_order); noconfcombos_recurse($ret, $max_list_length, $stop_at, $answer_order_lengths, $answer_order_lists, $output_order, $answer, 0); return $ret; } # try swapping in different indexes into position $index, from the positions # higher, then recurse function noconfcombos_recurse(&$ret, $max_list_length, $stop_at, &$lengths, &$lists, &$output_order, $answer, $index) { if($index < $stop_at) { noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1); } for($other = $index + 1; $other < $max_list_length; ++$other) { if($answer[$other] < $lengths[$index]) { # && $answer[$index] < $lengths[$other]) { $tmp = $answer[$index]; $answer[$index] = $answer[$other]; $answer[$other] = $tmp; $ret[] = noconfcombos_convert($answer, $lists, $output_order); if($index < $stop_at) { noconfcombos_recurse($ret, $max_list_length, $stop_at, $lengths, $lists, $output_order, $answer, $index + 1); } } } } function noconfcombos_convert(&$indexes, &$lists, &$order) { $ret = ''; foreach($order as $i) { $ret .= $lists[$i][$indexes[$i]]; } return $ret; } function noconfcombos_test() { $a = array('1', '2', '3', '4'); $b = array('a', 'b', 'c', 'd', 'e'); $c = array('x', 'y', 'z'); $all = array($a, $b, $c); print_r(noconfcombos($all)); } noconfcombos_test(); </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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