Поиск всех неконфликтных комбинаций значений из нескольких списков значений
https://stackoverflow.com/questions/1378098
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть следующий массив, который содержит массивы значений:
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
Может быть любое количество массивов, и массив может содержать любое количество значений.В настоящее время у меня есть фрагмент кода, который будет генерировать все комбинации, в которых из каждого массива берется по одному значению.например:
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
Однако то, что я на самом деле хочу, - это только комбинации, в которых в каждом столбце находится только одно значение, т.е.1ax не подходит, потому что все три значения 1, a и x находятся в первом столбце, 1by не подходит, потому что b и y находятся во втором столбце.Таким образом, из приведенного выше примера только эти комбинации были бы допустимы:
1cy, 2cx
Изначально я планировал просто сгенерировать все комбинации, а затем отфильтровать те, которые содержат конфликты, но это не масштабируется, поскольку это упрощенный пример, в реальном приложении будут ситуации, когда потенциально могут быть миллионы комбинаций (включая конфликтующие).
Кто-нибудь может помочь с лучшим способом решить эту проблему?Я работаю на PHP, но любой пример кода, который четко демонстрирует логику, был бы полезен.
Заранее благодарю.
Обновить:
Я протестировал решения, которые работают с большим набором данных, чтобы получить некоторые тесты, и вот результаты на данный момент:
$array = array(
array('1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3', '1', '2', '3'),
array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
array('x', 'y', 'z', 'x', 'y', 'z', 'x', 'y', 'z'),
array('1', '2', '3', '1', '2', '3', '1', '2', '3'),
array('a', 'b', 'c', 'd', 'a', 'b', 'c', 'd', 'a', 'b', 'c', 'd'),
array('x', 'y', 'z'),
);
Джош Дэвис 2 - е Решение:
Combinations: 249480
Time: 0.3180251121521 secs
Memory Usage: 22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb
Джош Дэвис:
Combinations: 249480
Time: 1.1172790527344 secs
Memory Usage: 22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb
Том Хейг:
Combinations: 249480
Time: 5.7098741531372 secs
Memory Usage: 39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
Решение
Это один из тех случаев, когда самогенерируемый код и грубая сила превосходят большинство алгоритмов по простоте и производительности.В предыдущих ответах я видел много рекурсии, манипуляций с массивами и вычислений, хотя на самом деле вы хотите сделать следующее:
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";
}
}
}
Приведенная выше процедура создает копию значений в начале каждого цикла, а затем удаляет значения, используемые внешними циклами.Вы можете улучшить этот процесс, создав копию значений. только один раз в начале удаляйте ключи по мере их использования (в начале каждого цикла) и кладите обратно по мере освобождения (в конце каждого цикла).Тогда процедура выглядит так:
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);
Другие советы
Интересная проблема!Это оказалось сложнее, чем я думал, но, похоже, работает.
Основная стратегия состоит в том, чтобы сначала упорядочить массивы от меньшего к большему (отслеживая, в каком порядке они были, чтобы я мог вывести ответы в правильном порядке).
Я храню ответы в виде массива индексов в этом отсортированном массиве входных списков.
Теперь, когда списки отсортированы, я могу сохранить первый правильный ответ как array(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);
Ваша проблема аналогична проблеме найти определитель матрицы.Лучший способ, по моему мнению, - заполнить меньшие массивы каким-либо символом, скажем, "0", чтобы все они имели одинаковое количество значений в вашем примере.
$array = array(
array('1', '2', '0'),
array('a', 'b', 'c'),
array('x', 'y', '0'),
);
затем пройдитесь по каждому из значений первого массива и для каждого увеличения индекса массива на 1 и проверьте следующий массив и следующий столбец (в первом цикле это будет «1», а индекс будет увеличен с 0 до 1, затем получите $массив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);
