# Permutations

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.