# Combinations, Dispositions and Permutations in PHP

Posted on

Combinations, Dispositions and Permutations in PHP – Here in this article, we will share some of the most common and frequently asked about PHP problem in programming with detailed answers and code samples. There’s nothing quite so frustrating as being faced with PHP errors and being unable to figure out what is preventing your website from functioning as it should like php and algorithm . If you have an existing PHP-based website or application that is experiencing performance issues, let’s get thinking about Combinations, Dispositions and Permutations in PHP.

What is the most efficient way to generate all the combinations, dispositions and permutations of an array in PHP?

Solution :

Here is code to get all permutations:

http://php.net/manual/en/function.shuffle.php#90615

With the code to get the power set, permutations are those of maximal length, the power set should be all combinations. I have no idea what dispositions are, so if you can explain them, that would help.

You can use this class: http://pear.php.net/package/Math_Combinatorics

and use it like:

``````\$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>';
}
}
``````

I’d like to suggest my solution of a CombinationsGenerator, which generates combinations of array items.

It’s limited to all combinations are of the full length, and not repeats any item. But I believe implementation would not be too hard.

``````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);
}
``````

It’s in PHP7 style, it uses a `Generator` ’cause I believe there are good reasons for doing it.

``````/* 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;
}
}
``````

I had to modify @hejdav’s answer so that it includes partial combinations, so that it fully delivers all of the results.

I scoured the Internet for this solution and as of June 2019, I believe this is the only publicly accessible answer (anywhere) that truly lists all possible, non-duplicating possibilities.

``````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);
}
}
}
}
``````