# Permutations

### From PostgreSQL wiki

Permutations of an array

Works with PostgreSQL

8.4

Written in

SQL

Depends on

Nothing

Generation of all permutations of a given array (in this example, of 6 elements):

SELECT (WITH RECURSIVE r(n,p,a,b) AS (SELECT i, '{}'::integer[], ARRAY[1,2,3,4,5,6], 6 UNION ALL SELECT n / b, p || a[n % b + 1], a[1:n % b] || a[n % b + 2:b], b-1 FROM r WHERE b > 0) SELECT p FROM r WHERE b=0) FROM generate_series(0,6!::integer-1) i;

Wrapped in an SQL function:

CREATE FUNCTION permute(anyarray) RETURNS SETOF anyarray LANGUAGE SQL IMMUTABLE AS $f$ SELECT (WITH RECURSIVE r(n,p,a,b) AS (SELECT i, $1[1:0], $1, array_upper($1,1) UNION ALL SELECT n / b, p || a[n % b + 1], a[1:n % b] || a[n % b + 2:b], b-1 FROM r WHERE b > 0) SELECT p FROM r WHERE b=0) FROM generate_series(0,(array_upper($1,1))!::integer-1) i; $f$;

The logic behind this is as follows: the recursive subselect implements the variable-bit-encoding algorithm for generating the `n`

'th permutation of a list (essentially converting `n`

into the factorial base); the column `p`

is the output generated so far, `a`

is the array items not used so far, and `b`

is the current base. At each recursion level, one element is chosen and appended to `p`

, removed from `a`

, and the base decremented. Recursion ends when `b=0`

, and that row contains the desired result.

Iteration of this subselect for values over [0..n!-1] generates all permutations.