Combinações, Alienações e permutações em PHP
-
16-09-2019 - |
Pergunta
O que é a maneira mais eficiente para gerar todas as combinações, disposições e permutações de uma matriz em PHP?
Solução
Aqui está o código para obter todas as permutações:
http://php.net/manual/en/function.shuffle .php # 90615
Com o código para obter o conjunto de potência, permutações são os de comprimento máximo, o conjunto de potência deve ser todas as combinações. Eu não tenho nenhuma idéia do que disposições são, por isso, se você pode explicar-lhes, que iria ajudar.
Outras dicas
Você pode usar essa classe: http://pear.php.net/package/Math_Combinatorics
e usá-lo como:
$combinatorics = new Math_Combinatorics;
$words_arr = array(
'one' => 'a',
'two' => 'b',
'three' => 'c',
'four' => 'd',
);
for ($i=count($words_arr)-1;$i>=1;$i--) {
echo '<br><br>' . $i . ':<br>';
$combinations_arr = $combinatorics->combinations($words_arr, $i);
foreach ($combinations_arr as $combinations_arr_item) {
echo implode(', ', $combinations_arr_item) . '<br>';
}
}
Eu gostaria de sugerir a minha solução de um CombinationsGenerator , o que gera combinações de itens de matriz.
É limitado a todas as combinações são do corpo inteiro, e não repete qualquer item. Mas eu acredito que a implementação não seria muito difícil.
class CombinationsGenerator
{
public function generate(array $list): \Generator
{
if (count($list) > 2) {
for ($i = 0; $i < count($list); $i++) {
$listCopy = $list;
$entry = array_splice($listCopy, $i, 1);
foreach ($this->generate($listCopy) as $combination) {
yield array_merge($entry, $combination);
}
}
} elseif (count($list) > 0) {
yield $list;
if (count($list) > 1) {
yield array_reverse($list);
}
}
}
}
$generator = new \CombinationsGenerator();
foreach ($generator->generate(['A', 'B', 'C', 'D']) as $combination) {
var_dump($combination);
}
É em grande estilo PHP7, ele usa um \Generator
porque eu acredito que há boas razões para fazê-lo.
/* Combinations */
function nCr($n, $r)
{
if ($r > $n)
{
return NaN;
}
if (($n - $r) < $r)
{
return nCr($n, ($n - $r));
}
$return = 1;
for ($i = 0; $i < $r; $i++)
{
$return *= ($n - $i) / ($i +1);
}
return $return;
}
/* Permutations */
function nPr($n, $r)
{
if ($r > $n)
{
return NaN;
}
if ($r)
{
return $n * (nPr($n -1, $r -1));
}
else
{
return 1;
}
}
Eu tive que modificar @ resposta de hejdav para que ele inclui combinações parciais, de modo que ele oferece plenamente todos os resultados.
Eu percorri a internet para esta solução e em junho de 2019, eu acredito que esta é a resposta só é acessível ao público (em qualquer lugar) que realmente lista todos os possíveis, não-duplicação de possibilidades.
class CombinationsGenerator
{
/**
* Taken from https://stackoverflow.com/a/39447347/430062.
*
* @param array $list
* @return \Generator
*/
public function generate(array $list): \Generator
{
// Generate even partial combinations.
$list = array_values($list);
$listCount = count($list);
for ($a = 0; $a < $listCount; ++$a) {
yield [$list[$a]];
}
if ($listCount > 2) {
for ($i = 0; $i < count($list); $i++) {
$listCopy = $list;
$entry = array_splice($listCopy, $i, 1);
foreach ($this->generate($listCopy) as $combination) {
yield array_merge($entry, $combination);
}
}
} elseif (count($list) > 0) {
yield $list;
if (count($list) > 1) {
yield array_reverse($list);
}
}
}
}