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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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