# How can I calculate all grouping permutations of an input string in SQL?

Given an input like "ABC" generate a query that calculates all potential splits of 0 or more of the given string,

Desired output,

``````A   B   C
A   BC
AB  C
ABC
``````

Given an input like "ABCD"

``````A    B   C    D
A    BC  D
A    B   CD
AB   C   D
A    BCD
AB   CD
ABC  D
ABCD
``````

Not all that concerned with how output is formed, array, rows, json, etc. More looking for discrete list of all permutations of grouping.

I guess that is just a challenge for fun, but here is my solution:

``````WITH s(s) AS (VALUES ('ABCD'))
SELECT substr(s, 1, 1) ||
string_agg(
CASE WHEN i & (2::numeric ^ p)::bigint = 0 THEN '' ELSE ' ' END ||
substr(s, p + 2, 1),
''
)
FROM s
CROSS JOIN generate_series(0, (2::numeric ^ (length(s) - 1) - 1)::bigint) AS i
CROSS JOIN generate_series(0, length(s) - 2) AS p
GROUP BY s, i;

?column?
══════════
A BC D
AB C D
ABCD
ABC D
A B CD
AB CD
A B C D
A BCD
(8 rows)
``````

The idea is to get the binary numbers from 0 to 2 ^ (length - 1) - 1 and interpolate spaces wherever there is a 1. So 101 (decimal 5) would become `A BC D`.

The binomial problem can be translated to this simple pseudo-code algorithm:

``````take the first letter
while more letters, loop
make two copies, one with trailing space
append next letter
end loop
``````

### Recursive function

This can be implemented with a recursive function in any capable procedural language. Using PL/pgSQL.

#### Basic version

``````CREATE OR REPLACE FUNCTION word_permutations(_word text)
RETURNS SETOF text
LANGUAGE plpgsql IMMUTABLE PARALLEL SAFE STRICT AS
\$func\$
BEGIN
IF length(_word) > 1 THEN
RETURN QUERY
SELECT left(_word, 1) || s || w
FROM  (VALUES (''), (' ')) sep(s)
, word_permutations(right(_word, -1)) w;
ELSE
RETURN NEXT _word;
END IF;
END
\$func\$;
``````

Call:

``````SELECT word_permutations('ABCD');
``````

fiddle (with performance test)

Performs much faster than Laurenz' query, and still ~ 2-3x faster than my rCTE below, with or without function wrapper. And scales better.

#### Optimized version

After input from ypercube. More than twice as fast and scales better. Shortcuts leaves to reduce the number of recursive calls.

``````CREATE OR REPLACE FUNCTION word_permutations2(_word text)
RETURNS SETOF text
LANGUAGE plpgsql IMMUTABLE PARALLEL SAFE STRICT AS
\$func\$
DECLARE
world_len int := length(_word);
BEGIN
CASE world_len
WHEN 2 THEN
RETURN NEXT _word;
RETURN NEXT OVERLAY(_word PLACING ' ' FROM 2 FOR 0);
WHEN 1, 0 THEN  -- corner cases
RETURN NEXT _word;
ELSE
RETURN QUERY
SELECT wl || s || wr
FROM  (VALUES (''), (' ')) sep(s)
, word_permutations2(left(_word, world_len/2)) wl
, word_permutations2(right(_word, -(world_len/2))) wr;
END CASE;
END
\$func\$;
``````

fiddle (with performance test)

### Pure SQL with rCTE

Since this is dba.SE, a pure SQL solution with a recursive CTE:

``````WITH RECURSIVE
val(w) AS (SELECT 'ABCD')      -- input
, sep(s) AS (VALUES (''), (' '))
, cte AS (
SELECT LEFT(w, 1) AS perm, right(w, -1) AS rest FROM val
UNION ALL
SELECT perm || s || LEFT(rest, 1), right(rest, -1)
FROM   cte, sep
WHERE  rest <> ''
)
SELECT perm FROM cte WHERE rest = '';
``````

Same result for all:

perm
ABCD
A BCD
AB CD
A B CD
ABC D
A BC D
AB C D
A B C D
• Erwin, have a look at my variation/improvement on your recursive one. I think it performs slightly better consistently. Not sure why, maybe it does less function calls. Only tested it in dbfiddle.uk Commented Nov 29, 2021 at 13:17
• @ypercubeᵀᴹ: Remarkable. I guess it's because your approach reduces the depth of the recursion. I added a version to test some more: db<>fiddle here Commented Dec 1, 2021 at 21:36

An experiment/improvement on Erwin's recursive solution:

``````-- experiment 3
-- variation on Erwin's recursive function
CREATE OR REPLACE FUNCTION word_permutations_yper(_word text)
RETURNS SETOF text
LANGUAGE plpgsql IMMUTABLE PARALLEL SAFE STRICT AS
\$func\$
declare
word_length int := length(_word);
BEGIN
IF word_length > 1 THEN
RETURN QUERY
SELECT wl || s || wr
FROM  (VALUES (''), (' ')) sep(s)
, word_permutations(left(_word, word_length/2)) wl
, word_permutations(right(_word, -(word_length/2))) wr;
ELSE
RETURN NEXT _word;
END IF;
END
\$func\$;
``````

Tested in: dbfiddle.uk