Marc Ermshaus

Linkblog

PHP snippet: Iterative calculation of permutations

Published on 22 Apr 2011. Tagged with php.

This function calculates the n-th permutation of the elements in an array using an iterative approach. It does not rely on recursion.

<?php // This code is public domain. The original author is Marc Ermshaus.

error_reporting(-1);

/**
 * Calculates the factorial of a given non-negative integer
 *
 * @param  int $n Non-negative integer
 * @return int Factorial of $n
 */
function fac($n)
{
    if (!is_int($n) || $n < 0) {
        throw new InvalidArgumentException(
                'n has to be a non-negative (int)');
    }

    for ($f = 1; $n > 1; $n--) {
        $f *= $n;
    }
    
    return $f;
};

/**
 * Returns a specific permutation of an array
 *
 * This function does not preserve key/value pairs.
 * 
 * Permutation table for input (a, b, c):
 *
 *    n   result
 *   -------------
 *   ...
 *   -6   a, b, c    initial state
 *   -5   a, c, b
 *   -4   b, a, c
 *   -3   b, c, a
 *   -2   c, a, b
 *   -1   c, b, a
 *    0   a, b, c    initial state
 *    1   a, c, b
 *    2   b, a, c
 *    3   b, c, a
 *    4   c, a, b
 *    5   c, b, a
 *    6   a, b, c    initial state
 *   ...
 *
 * @param  array $items Array to calculate permutation of
 * @param  int   $n     Index of wanted permutation
 * @return array Resulting array
 */
function getNthPermutation(array $items, $n)
{
    if (!is_int($n)) {
        throw new InvalidArgumentException(
                'n has to be an (int)');
    }

    $n      = (int) $n;
    $result = array();
    $l      = count($items);

    $facL = fac($l);

    while ($n < 0) {
        $n += $facL;
    }

    $n = $n % $facL;

    for ($i = 1; $l >= $i; $i++) {
        $facLI = fac($l - $i);

        // Calculate current index in $items
        $k = (int) ($n / $facLI);

        // Remove element from items and push to result
        $curItem = array_splice($items, $k, 1);
        $result[] = $curItem[0];

        $n -= $k * $facLI;
    }

    return $result;
}



header('content-type: text/plain');

$items = range('a', 'd');

$f = fac(count($items));

for ($i = $f * -2; $i <= $f * 2; $i++) {
    printf("% 3d  :  %s\n", $i, join(', ', getNthPermutation($items, $i)));
}