Поиск всех несогласованных комбинаций значений из нескольких списков значений

Это один из тех случаев, когда самогенерируемый код и грубая сила будут бить большинство алгоритмов по простоте и производительности. В предыдущих ответах я видел много рекурсии, манипуляции массивами и вычислений, когда на самом деле то, что вы хотели бы сделать, это:

 foreach ($array[0] as $k0 => $v0) { foreach ($array[1] as $k1 => $v1) { if ($k1 == $k0) { continue; } foreach ($array[2] as $k2 => $v2) { if ($k2 == $k1 || $k2 == $k0) { continue; } $result[] = $v0.$v1.$v2; } } } 

Конечно, вы не можете написать это, если не знаете, сколько массивов в $array . Вот где сгенерированный код подходит:

 $array = array( array('1', '2'), array('a', 'b', 'c'), array('x', 'y') ); $result = array(); $php = ''; foreach ($array as $i => $arr) { $php .= 'foreach ($array[' . $i . '] as $k' . $i . ' => $v' . $i . '){'; if ($i > 0) { $sep = 'if ('; $j = $i - 1; do { $php .= $sep . '$k' . $i . ' == $k' . $j; $sep = ' || '; } while (--$j >= 0); $php .= ') { continue; } '; } } $php .= '$result[] = $v' . implode('.$v', array_keys($array)) . ';' . str_repeat('}', count($array)); eval($php); print_r($result); 

Обратите внимание, что эта подпрограмма предполагает, что $array представляет собой числовой индексный массив на основе нуля, как в вашем примере. Он будет генерировать приведенный выше код, скорректированный на произвольное количество массивов.

Обновить

Вот альтернативный алгоритм. Это по-прежнему самопроизвольно, но менее грубо. У нас все еще есть вложенные петли, за исключением того, что каждый цикл работает над копией массива, где ключи, которые в настоящее время используются внешними циклами, были удалены из массива этого цикла. Например, если значения должны быть (a, b, c), но внешние циклы используют индексы 0 и 2, мы удаляем «a» (индекс 0) и «c» (индекс 2), и все, что у нас осталось, это «б». Это означает, что циклы работают только на возможных комбинациях, и нам больше не нужно условие if .

Кроме того, и эта часть может быть применена и к предыдущему алгоритму, мы обрабатываем массивы значений в порядке от наименьшего до самого большого, чтобы гарантировать, что используемые индексы существуют в текущем массиве. Недостатком является то, что он не генерирует комбинации в одном порядке. Он генерирует одни и те же комбинации, но не в том же порядке. Код выглядит так:

 $a0 = $array[0]; foreach ($a0 as $k0 => $v0) { $a2 = $array[2]; unset($a2[$k0]); foreach ($a2 as $k2 => $v2) { $a1 = $array[1]; unset($a1[$k0], $a1[$k2]); foreach ($a1 as $k1 => $v1) { $result[] = "$v0$v1$v2"; } } } с $a0 = $array[0]; foreach ($a0 as $k0 => $v0) { $a2 = $array[2]; unset($a2[$k0]); foreach ($a2 as $k2 => $v2) { $a1 = $array[1]; unset($a1[$k0], $a1[$k2]); foreach ($a1 as $k1 => $v1) { $result[] = "$v0$v1$v2"; } } } 

Вышеупомянутая процедура устанавливает копию значений в начале каждого цикла, а затем удаляет значения, используемые внешними циклами. Вы можете улучшить этот процесс, установив копию значений только один раз в начале, удалите ключи по мере их использования (в начале каждого цикла) и поместите их обратно по мере их освобождения (в конце каждого цикла) , После этого процедура выглядит следующим образом:

 list($a0,$a1,$a2) = $array; foreach ($a0 as $k0 => $v0) { unset($a1[$k0], $a2[$k0]); foreach ($a2 as $k2 => $v2) { unset($a1[$k2]); foreach ($a1 as $k1 => $v1) { $result[] = "$v0$v1$v2"; } $a1[$k2] = $array[1][$k2]; } $a1[$k0] = $array[1][$k0]; $a2[$k0] = $array[2][$k0]; } с list($a0,$a1,$a2) = $array; foreach ($a0 as $k0 => $v0) { unset($a1[$k0], $a2[$k0]); foreach ($a2 as $k2 => $v2) { unset($a1[$k2]); foreach ($a1 as $k1 => $v1) { $result[] = "$v0$v1$v2"; } $a1[$k2] = $array[1][$k2]; } $a1[$k0] = $array[1][$k0]; $a2[$k0] = $array[2][$k0]; } 

Фактический код, который генерирует исходный код:

 $keys = array_map('count', $array); arsort($keys); $inner_keys = array(); foreach ($keys as $k => $cnt) { $keys[$k] = $inner_keys; $inner_keys[] = $k; } $result = array(); $php = 'list($a' . implode(',$a', array_keys($array)) . ')=$array;'; foreach (array_reverse($keys, true) as $i => $inner_keys) { $php .= 'foreach ($a' . $i . ' as $k' . $i . ' => $v' . $i . '){'; if ($inner_keys) { $php .= 'unset($a' . implode('[$k' . $i . '],$a', $inner_keys) . '[$k' . $i . ']);'; } } $php .= '$result[] = "$v' . implode('$v', array_keys($array)) . '";'; foreach ($keys as $i => $inner_keys) { foreach ($inner_keys as $j) { $php .= '$a' . $j . '[$k' . $i . ']=$array[' . $j . '][$k' . $i . "];\n"; } $php .= '}'; } eval($php); 

Интересная проблема! Это оказалось более сложным, чем я думал, но, похоже, он работает.

Основная стратегия состоит в том, чтобы сначала упорядочить массивы с наименьшими по величине (отслеживая, в каком порядке они были, поэтому я могу выводить ответы в правильном порядке).

Я сохраняю ответы в виде массива индексов в этот отсортированный массив входных списков.

Теперь, когда списки отсортированы, я могу сохранить первый правильный ответ как массив (0,1,2, …, n);

Затем я возвращаюсь к функции для проверки всех значений в первом слоте там (выше 0), заменяя ее другими значениями в этом массиве ответов (все те, которые не слишком велики для этого слота). Поскольку я сортировал его по размеру, я могу перемещать любое значение вправо, когда я обмениваюсь, не опасаясь, что он будет большим для этого правильного слота.

вывод каждого допустимого слота имеет некоторую сумасшедшую направленность, чтобы отменить все сортировки.

Извините, если это выглядит запутанным. Я не потратил много времени на его очистку.

 <?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(); 

Я думаю, что это работает. Он использует рекурсию для перехода по структуре, как дерево. Для каждой ветви она отслеживает, какие столбцы уже сделаны. Вероятно, он медленный, потому что это подход грубой силы.

 <?php $array = array( array('1', '2'), array('a', 'b', 'c'), array('x', 'y'), ); function f($array, & $result, $colsToIgnore = array(), $currentPath = array()) { $row = array_shift($array); $length = count($row); $isMoreRows = !! count($array); for ($col = 0; $col < $length; $col++) { //check whether column has already been used if (in_array($col, $colsToIgnore)) { continue; } $item = $row[$col]; $tmpPath = $currentPath; $tmpPath[] = $item; if ($isMoreRows) { $tmpIgnoreCols = $colsToIgnore; $tmpIgnoreCols[] = $col; f($array, $result, $tmpIgnoreCols, $tmpPath); } else { $result[] = implode('', $tmpPath); } } } $result = array(); f($array, $result); print_r($result); 

вероятно, не самый элегантный способ, но делает трюк (javascript)

 var result = []; for(i=0;i<arr1.length;i++) { for(j=0;j<arr2.length;j++) { if(j==i) continue; else { for(k=0;k<arr3.length;k++) { if(k==i||k==j) continue; else { result.push(arr1[i]+arr2[j]+arr3[k]); } } } } } 

Это может быть реорганизовано с использованием рекурсии, что позволяет работать с любым количеством массивов. Если я найду время, я попробую сам.

пс. Я не знаю php, пример написан в Delphi.

Редактировать: рекурсивное решение с произвольными # массивами

 type TSingleArray = array of string; TMasterArray = array of TSingleArray; var solutions: array of integer; // Q&D container to hold currently used indexes of SingleArrays procedure WriteSolution(const masterArray: TMasterArray); var I: Integer; indexes: string; solution: string; begin for I := 0 to High(solutions) do begin indexes := indexes + IntToStr(solutions[I]) + ' '; solution := solution + masterArray[I][solutions[I]]; end; Writeln('Solution: ' + solution + ' Using indexes: ' + indexes); end; procedure FindSolution(const masterArray: TMasterArray; const singleArrayIndex: Integer; var bits: Integer); var I: Integer; begin for I := 0 to High(masterArray[singleArrayIndex]) do begin //***** Use bit manipulation to check if current index is already in use if bits and (1 shl I) = (1 shl I ) then continue; solutions[singleArrayIndex] := I; Inc(bits, 1 shl I); //***** If it is not the last array in our masterArray, continue by calling RecursArrays recursivly. if singleArrayIndex <> High(masterArray) then FindSolution(masterArray, Succ(singleArrayIndex), bits) else WriteSolution(masterArray); Dec(bits, 1 shl I); end; end; //*************** // Initialization //*************** var I, J: Integer; bits: Integer; singleArrayString: string; masterArray: TMasterArray; begin I := 10; SetLength(masterArray, I); for I := 0 to High(masterArray) do begin SetLength(masterArray[I], High(masterArray) + Succ(I)); singleArrayString := EmptyStr; for J := 0 to High(masterArray[I]) do begin masterArray[I][J] := IntToStr(J); singleArrayString := singleArrayString + masterArray[I][J]; end; WriteLn(singleArrayString) end; ReadLn; //****** Start solving the problem using recursion bits := 0; SetLength(solutions, Succ(High(masterArray))); FindSolution(masterArray, 0, bits); end. 

Посмотрите на это под другим углом: для составления строки результата вам нужно выбрать значение для каждого столбца. Каждое значение должно выбираться из другой строки источника. Проблема известна как «выбрать N из M», или более математически, комбинацию .

Это означает, что строка результата соответствует массиву индексов строки-источника.

Вы можете построить все возможные подборки, начав строить такой индекс (псевдокод)

 function combinations( $source ) { if( count( $source ) == 0 ) return $source; $result=array(); // build one row foreach( $source as $index=>$value ) { $newsource = array_splice( $source, $index, 1 ); $reduced_combinations=combinations( $newsource ); foreach( $reduced_combinations as $reduced_combi ) { $newrow=array_unshift( $reduced_combi, $value ); $result[]=$newrow; } } return $result; } function retrieve_indices( $indices, $arrays ) { $result=array(); foreach( $indices as $column=>$index ) { $result[]=$arrays[$index][$column]; } return $result; } $source_arrays = array( array( "1", "2", "3" ), array( "a", "b", "c" ), array( "x", "y", "z" ) ); $index_combinations = combinations( range(0,2) ); $result=array(); foreach( $index_combinations as $combination ) { $result[]=retrieve_indices( $combination, $source_arrays ); } 

Другой вариант:

  $arr = array( array('1', '2'), array('a', 'b', 'c'), array('x', 'y'), ); //----- //assuming $arr consists of non empty sub-arrays function array_combinations($arr){ $max = 1; for ($i = 0; $i < count($arr); $i ++){ $max *= count($arr[$i]); } $matrix = array(); for ($i = 0; $i < $max; $i ++){ $matrix = array(); } $c_rep = 1; for ($i = count($arr) - 1; $i >= 0; $i --){ $c_rep *= ($i < count($arr) - 1)//last sub-array ? count($arr[$i + 1]) : 1; $k = 0; while ($k < $max){ for ($t = 0; $t < count($arr[$i]); $t ++){ for ($j = 0; $j < $c_rep; $j ++){ $matrix[$i][$k ++] = $arr[$i][$t]; } } } } return $matrix; } //----- $matrix = array_combinations($arr); 

Ваша проблема аналогична проблеме нахождения определителя матрицы . Лучший способ imho состоял бы в том, чтобы заполнить меньшие массивы некоторым символом, например «0», поэтому все они имеют равное количество значений в вашем примере

 $array = array( array('1', '2', '0'), array('a', 'b', 'c'), array('x', 'y', '0'), ); 

затем перебираем каждый из первых значений массива и для каждого приращения индекс массива на 1 и проверяем следующий массив и следующий столбец (в первом цикле он будет «1», а индекс будет увеличен на 0 – 1, затем получите $ array 1 – 'b' и т. д.), если вы достигнете «0», перерыв, если вы достигнете правой границы, сбросьте первый индекс на 0. Затем сделайте то же самое с декрементом, и у вас будут все комбинации. Вероятно, неясно, проверьте изображение, которое я связал с

попробуй это :

 function algorithmToCalculateCombinations($n, $elems) { if ($n > 0) { $tmp_set = array(); $res = algorithmToCalculateCombinations($n - 1, $elems); foreach ($res as $ce) { foreach ($elems as $e) { array_push($tmp_set, $ce . $e); } } return $tmp_set; } else { return array(''); } } $Elemen = array(range(0,9),range('a','z')); $Length = 3; $combinations = algorithmToCalculateCombinations($Length, $Elemen);