在没有排列的情况下找到数组的所有可能组合

Question

输入是 'n' 长度的数组。
我需要将此数组中的所有组合存储到新数组中。

IN: j='{A, B, C ..}'
OUT: k='{A, B, C, AB, AC, BC, ABC ..}'

没有重复，所以没有BA、CA等

Answer 1

使用 recursive CTE

的通用解决方案

适用于任意数量的元素和任何支持>运算符的基本数据类型。

WITH RECURSIVE t(i) AS (SELECT * FROM unnest('{A,B,C}'::text[]))  -- provide array
, cte AS (
   SELECT i::text AS combo, i, 1 AS ct
   FROM   t
  
   UNION  ALL
   SELECT cte.combo || t.i::text, t.i, ct + 1
   FROM   cte
   JOIN   t ON t.i > cte.i
   )
SELECT ARRAY (   
   SELECT combo
   FROM   cte
   ORDER  BY ct, combo
   ) AS result;

结果是示例中text的数组。

请注意，使用 RECURSIVE 关键字时，您可以拥有任意数量的额外非递归 CTE。

更通用

如果满足以下任一条件：

数组元素不唯一（如 '{A,B,B}'）。
基本数据类型不支持 > 运算符（如 json）。
数组元素非常大 - 为了更好的性能。

使用行号而不是比较元素：

WITH RECURSIVE t AS (
   SELECT i::text, row_number() OVER () AS rn
   FROM   unnest('{A,B,B}'::text[]) i         -- duplicate element!
   )
, cte AS (
   SELECT i AS combo, rn, 1 AS ct
   FROM   t
  
   UNION  ALL
   SELECT cte.combo || t.i, t.rn, ct + 1
   FROM   cte
   JOIN   t ON t.rn > cte.rn
   )
SELECT ARRAY (   
   SELECT combo
   FROM   cte
   ORDER  BY ct, combo
   ) AS result;

或在 Postgres 9.4+ 中使用 WITH ORDINALITY：

PostgreSQL unnest() with element number

特例：生成十进制数

要按照这些行生成 5 位十进制数：

WITH RECURSIVE t AS (
   SELECT i
   FROM   unnest('{1,2,3,4,5}'::int[]) i
   )
, cte AS (
   SELECT i AS nr, i
   FROM   t
  
   UNION  ALL
   SELECT cte.nr * 10 + t.i, t.i
   FROM   cte
   JOIN   t ON t.i > cte.i
   )
SELECT ARRAY (   
   SELECT nr
   FROM   cte
   ORDER  BY nr
   ) AS result;

SQL Fiddle 演示全部。

Answer 2

如果 n 小于 20 ，则可以使用位掩码方法找到所有可能的组合。它有 2^n 种不同的组合。数字值 0 到 (2^n - 1) 表示组合之一。例如 n=3

0代表{},空元素
2^3-1=7= 111 b代表元素，abc

伪代码如下

for b=0 to 2^n - 1 do #each combination
  res=""
  for i=0 to (n-1) do   # which elements are included

     if (b && (1<<i) != 0)
        res= res+arr[i]
    end
    print res
  end
end

在没有排列的情况下找到数组的所有可能组合

Find all possible combinations of array without permutations

sql

arrays

postgresql

combinations

permutation

使用 recursive CTE

更通用

特例：生成十进制数