PostgreSQL递归查询中查找所有可能的组合（排列）

Question

输入是一个长度为'n'的数组。我需要生成包括从输入数组中选择更少元素的所有可能组合的数组元素的所有可能组合。

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

有重复，比如AB和BA..

我尝试了类似以下的方法：

WITH RECURSIVE t(i) AS (SELECT * FROM unnest('{A,B,C}'::text[])) 
,cte AS (
    SELECT i AS combo, i, 1 AS ct 
    FROM t 
  UNION ALL 
    SELECT cte.combo || t.i, 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;

它生成的组合没有重复项...所以我需要以某种方式进行修改。

- Adam

---

你尝试过什么？你必须在Postgres中完成吗？你可以使用pl/PGSQL或其他过程化语言吗？你必须使用数组吗？ - Politank-Z

你只需要长度为1到3的字符串吗？ - 1010

输入应该是可变的，因此它应该从数组中的所有元素生成组合。 - Adam

似乎大部分是转载自http://stackoverflow.com/q/30471120/398670。 - Craig Ringer

你是否查找过生成组合的知名算法？也许如果你先确定如何实现，然后尝试在 SQL 中实现，会有更好的结果。 - Craig Ringer

Answer 1

在一次递归查询中，迭代中使用的搜索表中的术语将被删除，然后剩余的记录重新进行查询。在您的情况下，这意味着一旦您处理了第一个数组元素（“A”），它就不再可用于数组元素的进一步排列。要使这些“已使用”的元素重新生效，您需要在递归查询中与数组元素表交叉连接，然后过滤掉当前排列中已经使用的数组元素（position(t.i in cte.combo) = 0）以及停止迭代的条件（ct <= 3）。

WITH RECURSIVE t(i) AS (
  SELECT * FROM unnest('{A,B,C}'::char[])
), cte AS (
     SELECT i AS combo, i, 1 AS ct 
     FROM t 
   UNION ALL 
     SELECT cte.combo || t.i, t.i, ct + 1 
     FROM cte, t
     WHERE ct <= 3
       AND position(t.i in cte.combo) = 0
) 
SELECT ARRAY(SELECT combo FROM cte ORDER BY ct, combo) AS result;

- Patrick

---

这里有一个 SQL Fiddle：http://www.sqlfiddle.com/#!15/9eecb7db59d16c80417c72d1e1f4fbf1/497。 - Gordon Linoff