6

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.

9

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.

0
3

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)

2
  • 1
    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
2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.