Encontrar todas as combinações não conflitantes de valores em várias listas de valores
https://stackoverflow.com/questions/1378098
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho o seguinte array que contém arrays de valores:
$array = array(
array('1', '2'),
array('a', 'b', 'c'),
array('x', 'y'),
);
Pode haver qualquer número de matrizes e uma matriz pode conter qualquer número de valores.Atualmente tenho um trecho de código que irá gerar todas as combinações onde um valor é retirado de cada array.por exemplo:
1ax, 1ay, 1bx, 1by, 1cx, 1cy, 2ax, 2ay, 2bx, 2by, 2cx, 2cy
No entanto, o que eu realmente quero são apenas as combinações onde apenas um valor fica em cada coluna, ou seja.1ax não é bom porque todos os três valores 1, a e x ficam na primeira coluna, 1by não é bom porque b e y ficam na segunda coluna.Portanto, no exemplo acima, apenas estas combinações seriam válidas:
1cy, 2cx
Originalmente, planejei apenas gerar todas as combinações e depois filtrar aquelas com conflitos, mas isso não é escalonável, pois este é um exemplo simplificado. Na aplicação real, haverá situações em que existem potencialmente milhões de combinações (incluindo conflitantes). ).
Alguém pode ajudar com uma maneira melhor de resolver isso?Estou trabalhando em PHP, mas qualquer exemplo de código que demonstre claramente a lógica seria útil.
Desde já, obrigado.
Atualizar:
Testei as soluções que funcionam em um conjunto de dados maior, para obter alguns benchmarks. Estes são os resultados até agora:
$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ª solução de Josh Davis:
Combinations: 249480
Time: 0.3180251121521 secs
Memory Usage: 22.012168884277 mb
Peak Memory Usage: 22.03059387207 mb
Josh Davis:
Combinations: 249480
Time: 1.1172790527344 secs
Memory Usage: 22.004837036133 mb
Peak Memory Usage: 22.017387390137 mb
Tom Haigh:
Combinations: 249480
Time: 5.7098741531372 secs
Memory Usage: 39.145843505859 mb
Peak Memory Usage: 39.145843505859 mb
Solução
Este é um daqueles casos em que o código autogerado e a força bruta superarão a maioria dos algoritmos em simplicidade e desempenho.Nas respostas anteriores, vi muita recursão, manipulação de array e cálculos, quando na verdade o que você gostaria de fazer é:
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;
}
}
}
Claro, você não pode escrever isso a menos que saiba quantos arrays existem $array.É aí que o código gerado é útil:
$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);
Observe que esta rotina assume que $array é uma matriz indexada numericamente baseada em zero, como no seu exemplo.Ele irá gerar o código citado acima, ajustado para um número arbitrário de arrays.
Atualizar
Aqui está um algoritmo alternativo.Ainda é autogerado, mas com menos força bruta.Ainda temos loops aninhados, exceto que cada loop funciona em uma cópia do array onde as chaves usadas atualmente pelos loops externos foram removidas do array deste loop.Por exemplo, se os valores deveriam ser (a,b,c), mas os loops externos estão usando os índices 0 e 2, removemos "a" (índice 0) e "c" (índice 2) e tudo o que nos resta é "b".Isso significa que os loops funcionam apenas em combinações possíveis e não precisamos de um if condição mais.
Além disso, e esta parte também pode ser aplicada ao algoritmo anterior, processamos os arrays de valores na ordem do menor para o maior para garantir que os índices utilizados existem no array atual.A desvantagem é que não gera as combinações na mesma ordem.Ele gera as mesmas combinações, mas não na mesma ordem.O código fica assim:
$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";
}
}
}
A rotina acima configura uma cópia dos valores no início de cada loop e, em seguida, remove os valores usados pelos loops externos.Você pode melhorar esse processo configurando uma cópia dos valores apenas uma vez no início, retire as chaves à medida que vão sendo utilizadas (no início de cada loop) e coloque-as de volta à medida que forem liberadas (no final de cada loop).A rotina então fica assim:
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];
}
O código real que gera a fonte acima é:
$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);
Outras dicas
Problema interessante! Isso acabou sendo mais complexo do que eu pensava, mas parece funcionar.
A estratégia básica é primeiro ordenar as matrizes menores para a maior (acompanhando em que ordem eles estavam, para que eu possa emitir as respostas na ordem correta).
Eu mantenho as respostas na forma de uma matriz de índices nessa matriz classificada de listas de entrada.
Agora que as listas são classificadas, posso armazenar a primeira resposta correta como matriz (0,1,2, ..., n);
Em seguida, eu recorrei a uma função para tentar todos os valores no primeiro slot lá (o 0 acima), trocando -o com outros valores nessa matriz de resposta (todos os que não são grandes demais para esse slot). Como eu o resolvi por tamanho, posso mover qualquer valor para a direita quando estou trocando, sem me preocupar com o fato de ser grande por esse slot certo.
A saída de cada slot válido tem alguma indireção louca para desfazer toda a classificação.
Desculpe se isso parece confuso. Não gastei muito tempo limpando.
<?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();
Eu acho que isso funciona. Está usando a recursão para passar por cima da estrutura como uma árvore. Para cada ramificação, ele acompanha quais colunas já foram tomadas. Provavelmente é lento porque é uma abordagem de força bruta.
<?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);
Provavelmente não é a maneira mais elegante, mas faz o truque (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]);
}
}
}
}
}
Isso pode ser refatorado usando a recursão, fazendo com que funcione com qualquer quantidade arbitrária de matrizes. Se eu encontrar tempo, vou tentar eu mesmo.
ps. Não sei PHP, o exemplo está escrito em Delphi.
Editar: solução recursiva com # arbitrário
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.
Olhe para ele de um ângulo diferente: para compor uma linha de resultado, você precisa escolher um valor para cada coluna. Cada valor deve ser escolhido em uma linha de origem diferente. O problema é conhecido como "escolha n fora de m", ou mais matematicamente, um Combinação.
Isso significa que uma linha de resultado corresponde a uma matriz de índices de linha de origem.
Você pode construir todas as escolhas possíveis começando a construir um índice como este (pseudo-código)
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 );
}
Outra opção:
$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);
Seu problema é semelhante ao de Encontrar um determinante de uma matriz. A melhor maneira de o IMHO seria preencher matrizes menores com algum símbolo, digamos '0', para que todos tenham um número igual de valores, em seu exemplo
$array = array(
array('1', '2', '0'),
array('a', 'b', 'c'),
array('x', 'y', '0'),
);
Em seguida, passe por cada um dos primeiros valores da matriz e para cada incremento o índice de matriz por 1 e verifique a próxima matriz e a próxima coluna (no primeiro loop, será '1' e o índice será 0 incrementado - 1, depois obtenha $ matriz1 - 'B' e assim por diante) Se você chegar a '0', quebre, se você atingir a borda direita, redefine o primeiro índice para 0. Faça o mesmo com o decréscimo e você terá todas as combinações. Provavelmente não está claro, verifique a imagem à qual vinculei
Experimente isso:
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);
