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.

What have you tried? Must you do this in Postgres? Can you use pl/PGSQL or another procedural language? Must you use arrays? — Politank-Z
– Politank-Z, Commented May 28, 2015 at 20:07
Input is ment to be variable so it should make combinations from all elements in array.. — Adam
– Adam, Commented May 28, 2015 at 20:30
Seems to be a mostly-repost of stackoverflow.com/q/30471120/398670 — Craig Ringer
– Craig Ringer, Commented May 29, 2015 at 1:05
Have you looked up well recognised algorithms for generating combinations? Perhaps if you determined how you wanted to do it, then tried to implement that in SQL, you'd have better results.. — Craig Ringer
– Craig Ringer, Commented May 29, 2015 at 1:06

Patrick · Accepted Answer · 2015-05-29 00:56:21Z

6

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;

answered May 29, 2015 at 0:56

Patrick

33k7 gold badges73 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Gordon Linoff Over a year ago

Here is a SQL Fiddle: sqlfiddle.com/#!15/9eecb7db59d16c80417c72d1e1f4fbf1/497.

Collectives™ on Stack Overflow

PostgreSQL find all possible combinations (permutations) in recursive query

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related