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 elegantly with a recursive function in any decent procedural language. With PL/pgSQL:

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');

Performs best in my tests. ~ 50x faster than Laurenz query, and still ~ 2-3x faster than the following rCTE (with or without function wrapper).

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:

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

db<>fiddle here (with added performance test)

• 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 Nov 29 '21 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 Dec 1 '21 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