排列

库片段

数组的排列

适用于 PostgreSQL

8.4

用

SQL

依赖于

无

生成给定数组的所有排列（在本例中，为 6 个元素）

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;

封装在 SQL 函数中

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$;

背后的逻辑如下：递归子查询实现用于生成列表第 n 个排列的可变位编码算法（本质上将 n 转换为 阶乘基）；列 p 是迄今为止生成的输出，a 是迄今为止未使用的数组项，b 是当前基数。在每个递归级别，选择一个元素并将其附加到 p，从 a 中移除，并将基数减 1。当 b=0 时，递归结束，该行包含所需的结果。

对于 [0..n!-1] 上的值，此子查询的迭代生成所有排列。