Marc Ermshaus

Linkblog

PHP Snippet: Get all permutations

Published on 18 Nov 2010. Tagged with php.

<?php

/**
 * Returns all possible permutations of $values containing $n elements using a
 * "draw and place back" algorithm
 *
 * The resulting array will always have pow(count($values), $n) entries.
 *
 * For
 *   $values = array('a', 'b') and $n = 2,
 * the result will contain:
 *   [aa, ab, ba, bb]
 *
 * @param array $values Vector to generate permutations of
 * @param int $n Elements per permutation
 * @return array Possible permutations
 */
function getPermutations(array $values, $n)
{
    $rec = function (array $values, &$ret, $n, array $cur = array()) use (&$rec)
    {
        if ($n > 0) {
            foreach ($values as $v) {
                $newCur = $cur;
                $newCur[] = $v;
                $rec($values, $ret, $n - 1, $newCur);
            }
        } else {
            $ret[] = $cur;
        }
    };

    $ret = array();
    $rec($values, $ret, $n);

    return $ret;
}



$values = range('a', 'd');
$n = 2;

$ret = getPermutations($values, $n);

foreach ($ret as $r) {
    foreach ($r as $d) {
        echo $d;
    }
    echo '<br>';
}