h1

Calculating permutations of a list

January 11, 2012

A recent project found me with the need to calculate all the possible permutations of a list of values. This is the possible order of all the values in the list.

For example, the list

1, 2, 3

Has 6 possible permutations:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

My first attempt tried to calculate all the permutations in one go using a recursive function. In PHP, this looks like this:

/**
* Recursive permutations function for calculating the
* possible permutations of an array.
*
* @param array $list
* The list to calculate the pemutations of.
*
* @return array
* An array of arrays. Each sub array is a permutation
* of the originial array.
*/
function permutations(array $list) {

if (count($list) == 1) {
return array($list);
}

$perms = array();

foreach ($list as $key => $value) {
$sublist = $list;
unset($sublist[$key]);
foreach (permutations($sublist) as $subperm) {
array_unshift($subperm, $value);
$perms[] = $subperm;
}
}

return $perms;
}

This worked great for small lists of up to about 8 elements but past 8 the number of permutations grows great and you start to run out of memory in the recursive calculations. Incidentally, the total number of permutations is always given as the factorial of the number of elements. So, for 3 elements the total number is 3! or 3 x 2 x 1 = 6.

Here is a short piece of code for calculating the factorial of a positive integer.

/**
* Factorial function. For calculating some of the numbers
* of possible combinations.
*/
function nfact($n) {
if ($n == 0) {
return 1;
}
else {
return $n * nfact($n - 1);
}
}

So, my second attempt was to come up with a relationship between the permutation number and the order of the elements in a list given the starting order. I came up with this (in PHP again)

/**
* Given a list in it's initial state workout the
* i'th permutation.
*
* @param array $initial_state
* The initial state of the array.
* @param int $i
* The permutation of the initial state to find. Initial state is 0.
*
* @return array
* The i'th permutation of the initial state.
*/
function permutation(array $initial_state, $i) {

$n = count($initial_state);

// Requires all keys to be numeric in ascending order.
$initial_state = array_values($initial_state);

if ($n == 1) {
return $initial_state;
}

$t = nfact($n);

$first_value_position = floor($i / ($t / $n));
$first_value = $initial_state[$first_value_position];

// Setup the args of for the next value in the permutation.
unset($initial_state[$first_value_position]);
$i = $i % ($t / $n);

return array_merge(array($first_value), permutation($initial_state, $i));
}

To get all permutations you can then loop $i from 0 to the total number of permutations for the list.

$initial_state = array(1, 2, 3, 4, 5, 6, 7, 8);
$permutations = array();

for ($i = 0; $i < nfact(count($initial_state)); $i++) {
$permutations[] = permutation($initial_state, $i);
}

Advertisements

One comment

  1. You might want to look at the subset library which includes a lot of combination/permutation code. I’ve used it for combinations to avoid any need for recursion.

    http://people.sc.fsu.edu/~jburkardt/m_src/subset/subset.html



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: