By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0. 3601568 fiddles created (47975 in the last week).
-- recursive function
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$;
SELECT word_permutations('ABCD');
✓
word_permutations
ABCD
A BCD
AB CD
A B CD
ABC D
A BC D
AB C D
A B C D
…
hidden batch(es)
-- rCTE
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 = '';
-> Result (cost=0.00..0.01 rows=1 width=0) (actual rows=1 loops=1)
Planning Time: 0.011 ms
Execution Time: 23.939 ms
…
hidden batch(es)
EXPLAIN (ANALYZE, TIMING OFF)
WITH RECURSIVE
val(w) AS (SELECT 'ABCDEFGHIJKLMNOP')
, 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 = ''
QUERY PLAN
CTE Scan on cte (cost=10.23..14.30 rows=1 width=32) (actual rows=32768 loops=1)
Filter: (rest = ''::text)
Rows Removed by Filter: 32767
CTE cte
-> Recursive Union (cost=0.00..10.23 rows=181 width=64) (actual rows=65535 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=64) (actual rows=1 loops=1)
-- Laurenz' function
EXPLAIN (ANALYZE, TIMING OFF)
WITH s(s) AS (VALUES ('ABCDEFGHIJKLMNOP'))
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;
-> Function Scan on generate_series p (cost=0.00..0.15 rows=15 width=4) (actual rows=15 loops=1)
-> Function Scan on generate_series i (cost=0.00..327.68 rows=32768 width=8) (actual rows=32768 loops=15)
Planning Time: 0.260 ms
Execution Time: 1126.010 ms
…
hidden batch(es)
-- ypercube
EXPLAIN (ANALYZE, TIMING OFF)
WITH s(s) AS (VALUES ('ABCDEFGHIJKLMNOP'))
SELECT
words
FROM s
, generate_series(0, (2::numeric ^ 15 - 1)::bigint) AS i
, lateral
( select
replace(replace(
string_agg(
substr(s, g+1, 1)||
substr(i::bit(15)::text, g+1, 1),
''
order by g
),
'0', ''),
'1', ' ') as words--
from generate_series(0, 15) as g
) as ag ;
-> Function Scan on generate_series g (cost=0.00..0.16 rows=16 width=4) (actual rows=16 loops=32768)
Planning Time: 0.150 ms
Execution Time: 453.432 ms
…
hidden batch(es)
-- experiment
-- EXPLAIN (ANALYZE, TIMING OFF)
WITH
val(w) AS (SELECT 'ABCD'::text) -- input
, sep(s) AS (VALUES (''::text), (' '))
select
v4.w as words
from
( select substr(val.w, 1, 1) as w from val) as v1,
lateral
( select v1.w || s || substr(val.w, 2, 1) as w
from sep, val
) as v2,
lateral
( select v2.w || s || substr(val.w, 3, 1) as w
from sep, val
) as v3,
lateral
( select v3.w || s || substr(val.w, 4, 1) as w
from sep, val
) as v4
words
ABCD
A BCD
AB CD
A B CD
ABC D
A BC D
AB C D
A B C D
…
hidden batch(es)
-- experiment
-- EXPLAIN (ANALYZE, TIMING OFF)
WITH
val(w) AS (SELECT 'ABCD'::text) -- input
, sep(s) AS (VALUES (''::text), (' '))
select
v4.w as words
from
( select substr(val.w, 1, 1) as w from val) as v1,
lateral
( select v1.w || s || substr(val.w, 2, 1) as w
from sep, val
) as v2,
lateral
( select v2.w || s || substr(val.w, 3, 1) as w
from sep, val
) as v3,
lateral
( select v3.w || s || substr(val.w, 4, 1) as w
from sep, val
) as v4
words
ABCD
A BCD
AB CD
A B CD
ABC D
A BC D
AB C D
A B C D
…
hidden batch(es)
-- experiment 2
-- EXPLAIN (ANALYZE, TIMING OFF)
WITH
val(w) AS (SELECT 'ABCD') -- input
, sep(s) AS (VALUES (''), (' '))
select
substr(w, 1, 1) || sep1.s
|| substr(w, 2, 1) || sep2.s
|| substr(w, 3, 1) || sep3.s
|| substr(w, 4, 1)
as words
from
val,
sep as sep1,
sep as sep2,
sep as sep3 ;
words
ABCD
AB CD
A BCD
A B CD
ABC D
AB C D
A BC D
A B C D
…
hidden batch(es)
-- experiment 2
EXPLAIN (ANALYZE, TIMING OFF)
WITH
val(w) AS (SELECT 'ABCDEFGHIJKLMNOP') -- input
, sep(s) AS (VALUES (''), (' '))
select
substr(w, 1, 1) || sep1.s
|| substr(w, 2, 1) || sep2.s
|| substr(w, 3, 1) || sep3.s
|| substr(w, 4, 1) || sep4.s
|| substr(w, 5, 1) || sep5.s
|| substr(w, 6, 1) || sep6.s
|| substr(w, 7, 1) || sep7.s
|| substr(w, 8, 1) || sep8.s
|| substr(w, 9, 1) || sep9.s
|| substr(w, 10, 1) || sep10.s
|| substr(w, 11, 1) || sep11.s
|| substr(w, 12, 1) || sep12.s
|| substr(w, 13, 1) || sep13.s
|| substr(w, 14, 1) || sep14.s
|| substr(w, 15, 1) || sep15.s
|| substr(w, 16, 1)
as words
from
val as v, sep as sep1,
sep as sep2,
sep as sep3,
sep as sep4,
sep as sep5,
sep as sep6,
sep as sep7,
sep as sep8,
sep as sep9,
sep as sep10,
sep as sep11,
sep as sep12,
sep as sep13,
sep as sep14,
sep as sep15
;
-- 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
world_length int := length(_word);
BEGIN
IF world_length > 1 THEN
RETURN QUERY
SELECT wl || s || wr
FROM (VALUES (''), (' ')) sep(s)
, word_permutations(left(_word, world_length/2)) wl
, word_permutations(right(_word, -(world_length/2))) wr;
ELSE
RETURN NEXT _word;
END IF;
END
$func$;
SELECT word_permutations_yper('ABCD');
