Postgres 12

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.

CREATE TABLE station (
  station text PRIMARY KEY
, booths  int NOT NULL  -- number of cashiers in station
);
INSERT INTO station VALUES 
  ('A', 1)
, ('B', 2)
, ('C', 1)
, ('D', 3);
4 rows affected

CREATE OR REPLACE FUNCTION f_pathfinder(_route text[])
  RETURNS TABLE (grp int, path text[]) LANGUAGE sql STABLE PARALLEL SAFE AS
$func$
WITH RECURSIVE rcte AS (
   SELECT cardinality($1) AS hops, 1 AS hop, ARRAY[s.station || booth] AS path
   FROM   station s, generate_series(1, s.booths) booth
   WHERE  s.station = $1[1]

   UNION ALL
   SELECT r.hops, r.hop + 1, r.path || (s.station || booth)
   FROM   rcte  r
   JOIN   station s ON s.station = _route[r.hop + 1], generate_series(1, s.booths) booth
   WHERE  r.hop < r.hops
   )
SELECT row_number() OVER ()::int AS grp, path
FROM   rcte r
WHERE  r.hop = r.hops;
$func$;
-- List of possible paths for given route ABCD
SELECT * -- grp, seq, booth
FROM  f_pathfinder('{A,B,C,D}'::text[]);


grp
path


1
{A1,B1,C1,D1}

2
{A1,B1,C1,D2}

3
{A1,B1,C1,D3}

4
{A1,B2,C1,D1}

5
{A1,B2,C1,D2}

6
{A1,B2,C1,D3}


-- with unnested arrays:
SELECT grp, seq, booth
FROM  f_pathfinder('{A,B,C,D}'::text[])
    , unnest(path) WITH ORDINALITY AS x(booth, seq);  -- ①


grp
seq
booth


1
1
A1

1
2
B1

1
3
C1

1
4
D1

2
1
A1

2
2
B1

2
3
C1

2
4
D2

3
1
A1

3
2
B1

3
3
C1

3
4
D3

4
1
A1

4
2
B2

4
3
C1

4
4
D1

5
1
A1

5
2
B2

5
3
C1

5
4
D2

6
1
A1

6
2
B2

6
3
C1

6
4
D3

grp	path
1	{A1,B1,C1,D1}
2	{A1,B1,C1,D2}
3	{A1,B1,C1,D3}
4	{A1,B2,C1,D1}
5	{A1,B2,C1,D2}
6	{A1,B2,C1,D3}

grp	seq	booth
1	1	A1
1	2	B1
1	3	C1
1	4	D1
2	1	A1
2	2	B1
2	3	C1
2	4	D2
3	1	A1
3	2	B1
3	3	C1
3	4	D3
4	1	A1
4	2	B2
4	3	C1
4	4	D1
5	1	A1
5	2	B2
5	3	C1
5	4	D2
6	1	A1
6	2	B2
6	3	C1
6	4	D3

grp	seq	booth
1	1	A1
1	2	B1
1	3	C1
1	4	D1
2	1	A1
2	2	B1
2	3	C1
2	4	D2
3	1	A1
3	2	B1
3	3	C1
3	4	D3
4	1	A1
4	2	B2
4	3	C1
4	4	D1
5	1	A1
5	2	B2
5	3	C1
5	4	D2
6	1	A1
6	2	B2
6	3	C1
6	4	D3

grp	seq	booth
1	1	A1
1	2	B1
1	3	C1
1	4	D1
2	1	A1
2	2	B1
2	3	C1
2	4	D2
3	1	A1
3	2	B1
3	3	C1
3	4	D3
4	1	A1
4	2	B2
4	3	C1
4	4	D1
5	1	A1
5	2	B2
5	3	C1
5	4	D2
6	1	A1
6	2	B2
6	3	C1
6	4	D3