Generate all combinations of a list of strings

I'm trying to generate all combinations of a list of Strings
list = ['A', 'B', 'C', 'D'].

I want to generate all possibilities and then search in the DB

ABCD, ABC, ABD, ACD, BCD, AB, AC, AD, BC, BD, CD, A, B, C, D

With my columns being like this:

result
code

1
A

2
BC

3
AC

4
B

5
ABC

6
AD

7
BCD

8
CD

9
ABCD

10
ABD

.......
......

To clarify: Order doesn't matter (ABC = BAC = CAB) and it should return multiple results (For list = ['A', 'B', 'C'] with same with the 10 columns above it should return [1, 2, 3, 4, 5]).

I'm using Postgres and I've tried with some recursive functions I've seen but none quite accomplish my needs.

So I'm not sure why you want to do this, but I'll just assume you've exhausted all other options.

TLDR, he's a fiddle to do what you want: https://dbfiddle.uk/?rdbms=postgres_13&fiddle=27cdc7ef6eaf179936d4d048276b139b

Explanation

To do this we need three things:

• A list of elements

• A collation with a sort order we agree with for this purpose

• A recursive query to build the tuples

The collation is important because if we are saying AB = BA, that's not an easy comparison to do within a database, especially as the length grows. HOWEVER, we can sort strings in a database and enforce the condition that the character in position n must be less than the character in position n+1. That makes the string BA an invalid construction.

We need recursion since we must build the strings from the prior concatenation of elements. This is possible in Postgres through the use of a recursive CTE.

Logically the process works as such:

• Start with all unique elements

• To prior results, concatenate elements greater than the last element

• Append the output and repeat

This is self-terminating as once the length of the string is equal to the number of elements, there are no elements greater than the last element.

Code

First, need a table of elements:

CREATE TABLE Element
(
  Element  CHAR(1)  NOT NULL COLLATE "en_US" /* Chosen since a < A < B < C.  Case support varies by Postgres version, check constraint handles this */
 ,CONSTRAINT PK_Element PRIMARY KEY (Element)
 ,CONSTRAINT CK_Element_Is_Uppercase CHECK (Element = UPPER(Element))
)

Next, populate that table:

INSERT INTO Element VALUES ('A'),('B'),('C'),('D')

Finally, recursive query to build the desired output:

WITH RECURSIVE Tuple AS
(
  SELECT
    CAST(Element AS Text) AS Tuple
   ,1 AS TupleLength
  FROM
    Element
  
    UNION ALL
    
  SELECT
    T.Tuple || E.Element
   ,TupleLength + 1
  FROM
    Tuple T
  INNER JOIN
    Element E
      ON E.Element > RIGHT(T.Tuple,1)
)
SELECT
  Tuple
FROM
  Tuple
ORDER BY
  TupleLength
 ,Tuple

If elements can repeat (AA,AAA,BB,etc.)

https://dbfiddle.uk/?rdbms=postgres_13&fiddle=f4b1822f65334ae45109680d3afc0c7f

Here we can change or criteria to >=, however we need to terminate the recursion based on the number of elements.

WITH RECURSIVE Tuple AS
(
  SELECT
    CAST(Element AS Text) AS Tuple
   ,1 AS TupleLength
  FROM
    Element
  
    UNION ALL
    
  SELECT
    T.Tuple || E.Element
   ,TupleLength + 1
  FROM
    Tuple T
  INNER JOIN
    Element E
      ON E.Element >= RIGHT(T.Tuple,1)
  WHERE
    TupleLength < (SELECT COUNT(*) FROM Element)
)
SELECT
  Tuple
FROM
  Tuple
ORDER BY
  TupleLength
 ,Tuple

StackExchange Database Administrators Q#301181, answer score: 7