PHP: Retornando todas as combinações possíveis de um array multidimensional

11/02/2010

~ 8 mins

Acabei chegando a uma solução, que vou compartilhar aqui com vocês, mas que não me deixou lá muito satisfeito. Pra esse projeto específico resolvia e a fila de tarefas é grande, então bola pra frente (é dura a vida do programador)!

Vamos dar uma olhada no problema. Vejamos o array abaixo:

$opcoes = array(
  'Cor'      => array( 'Vermelho', 'Branco', 'Prata', 'Azul' ),
  'Capacidade'  => array( '2GB', '4GB', '8GB', '16GB' ),
  'Interface'    => array( 'Windows', 'Mac' ),
);

O que eu precisava fazer era retornar uma lista com as combinações, como o resultado abaixo:

Vermelho, 2GB, Windows
Vermelho, 2GB, Mac
Vermelho, 4GB, Windows
Vermelho, 4GB, Mac
Vermelho, 8GB, Windows
(...)
Azul, 4GB, Mac
Azul, 8GB, Windows
Azul, 8GB, Mac
Azul, 16GB, Windows
Azul, 16GB, Mac

A idéia então era uma função recursiva, que montaria o array final com as combinações. Pra cada ítem do primeiro registro do array multidimensional, a função teria que varrer todos os outros registros e montar as combinações. A lógica é simples, mas, na hora da execução, sem usar variáveis globais, só consegui fazer retornando uma string com delimitadores simples - o array é montado fora da função.

O primeiro problema era que o array original não possuía índices númericos. E como nossa função teria que ser de alguma forma progressiva, a melhor coisa a ser feita, na minha opinião, era converter esses índices:

$opcoes = array(
  'Cor'      => array( 'Vermelho', 'Branco', 'Prata', 'Azul' ),
  'Capacidade'  => array( '2GB', '4GB', '8GB', '16GB' ),
  'Interface'    => array( 'Windows', 'Mac' ),
);

$combinar = array();
foreach( $opcoes as $k => $v )
{
  $combinar[] = $v;
}

Agora a função já pode incrementar os índices para fazer as combinações. Como parâmetros, ela recebe a string que vai ser concatenada, o array com os termos e o índice atual. Se o índice atual foi maior ou igual ao total de termos, a função concatena com a string já gerada anteriormente e inicia uma nova linha.

function combinacao( $str, $termos, $i )
{
  $texto = '';
  if ( $i >= count( $termos ) )
  {
    $texto .= trim( $str ) . "\n";
  }
    else
    {
    foreach ( $termos[$i] as $termo )
    {
      $texto .= combinacao( $str . $termo . '##', $termos, $i + 1 );
    }
    }
    return $texto;
}

A chamada da função ficou assim:

$texto = combinacao( '', $combinar, 0 );

Começamos com a string de concatenação, passando o array $combinar (formatamos os índices do $opcoes nele) e o índice 0.

Já o retorno ficou assim:

Vermelho##2GB##Windows##
Vermelho##2GB##Mac##
Vermelho##4GB##Windows##
Vermelho##4GB##Mac##
(...)
Azul##8GB##Windows##
Azul##8GB##Mac##
Azul##16GB##Windows##
Azul##16GB##Mac##

Cada combinação é uma nova linha na string e as opções da mesma estão separadas por ‘##’. Como preciso dos dados em um novo array (para montar uma tabela, ou uma lista, por exemplo), após a execução da função tratamos o retorno:

$texto = preg_split( '/\n/', $texto, -1, PREG_SPLIT_NO_EMPTY );
$combinacoes = array();
foreach( $texto as $k => $v )
{
  $combinacoes[] = preg_split( '/##/', $v, -1, PREG_SPLIT_NO_EMPTY );
}

Pra quem não conhece, com a constante PREG_SPLIT_NO_EMPTY, a função preg_split não retorna registros vazios no array.

Segue o código completo:

<?php
function combinacao( $txt, $termos, $i )
{
  $texto = '';
  if ( $i >= count( $termos ) )
  {
    $texto .= trim( $txt ) . "\n";
  }
    else
    {
    foreach ( $termos[$i] as $termo )
    {
      $texto .= combinacao( $txt . $termo . '##', $termos, $i + 1 );
    }
    }
    return $texto;
}

$opcoes = array(
  'Cor'      => array( 'Vermelho', 'Branco', 'Prata', 'Azul' ),
  'Capacidade'  => array( '2GB', '4GB', '8GB', '16GB' ),
  'Interface'    => array( 'Windows', 'Mac' ),
);

$combinar = array();
foreach( $opcoes as $k => $v )
{
  $combinar[] = $v;
}

$texto = combinacao( '', $combinar, 0 );
$texto = preg_split( '/\n/', $texto, -1, PREG_SPLIT_NO_EMPTY );

$combinacoes = array();
foreach( $texto as $k => $v )
{
  $combinacoes[] = preg_split( '/##/', $v, -1, PREG_SPLIT_NO_EMPTY );
}
print_r( $combinacoes );
exit;

Fica aí o desafio pra quem quiser dar uma melhorada nesse código - quando eu tiver tempo vou trabalhar nele. O ideal seria a função combinacao() retorna já um array certinho, sem utilizar globais. Outra feature legal seria aceitar arrays nos registros do nosso array principal.

Espero que este post ajude alguém com o mesmo problema e até a próxima!

Função para PHP 5.3+

O leitor João Batista Neto enviou a seguinte função, utilizando o recurso de funções anônimas (closures) disponível na versão 5.3 do PHP. Muito bacana a implementação.

/**
* Retorna todas as combinações possíveis de um array multidimensional
* @param array $data Matriz multidimensional contendo os dados
* @param string $separator String que será utilizada para separar os elementos
* @return array Uma matriz contendo a lista de combinações
*/
function array_combine_recursive( array $data , $separator = ',' )
{
  $response = new stdClass();
  $callback = function( $item , $key , $aux ) use ( $response , $separator )
  {
    $aux[ 2 ][] = $item;

    if ( count( $aux[ 0 ] ) )
    {
      array_walk( array_shift( $aux[ 0 ] ) , $aux[ 1 ] , array( $aux[ 0 ] , $aux[ 1 ] , $aux[ 2 ] ) );
    }
    else
    {
      $response->data[] = implode( $separator , $aux[ 2 ] );
    }
  };

  $response->data = array();

  array_walk( array_shift( $data ) , $callback , array( $data , $callback , array() ) );

  return $response->data;
}