Permutations

Library Snippets

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.