PostgreSQL find all possible combinations (permutations) in recursive query

Question

Input is an array of 'n' length. I need to generate all possible combinations of array elements, including all combinations with fewer elements from the input array.

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

With repetitions, so with AB BA..

I have tried something like this:

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;

It is generating combinations without repetitions... so I need to modify that somehow.

Answer 1

In a recursive query the terms in the search table that are used in an iteration are removed and then the query repeats with the remaining records. In your case that means that as soon as you have processed the first array element ("A") it is no longer available for further permutations of the array elements. To get those "used" elements back in, you need to cross-join with the table of array elements in the recursive query and then filter out array elements already used in the current permutation (position(t.i in cte.combo) = 0) and a condition to stop the iterations (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;