4

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.

2

2 Answers 2

7

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:

  1. A list of elements
  2. A collation with a sort order we agree with for this purpose
  3. 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:

  1. Start with all unique elements
  2. To prior results, concatenate elements greater than the last element
  3. 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
2
  • 1
    Fun extension to handle strings with a length > 1: dbfiddle.uk/…
    – bbaird
    Oct 15, 2021 at 18:20
  • This is almost perfect. I can work with this and try to create the more precise version I need. Thanks
    – LordHans
    Oct 18, 2021 at 6:18
1

You do not need a recursion, you can calculate the matrix of all the possible string combinations.
I find this to be more straightforward:

DROP TABLE IF EXISTS strings;
CREATE TABLE strings (
    id SERIAL PRIMARY KEY,
    string CHAR(1)
);

INSERT INTO strings 
    (string)
VALUES
    ('A'), ('B'), ('C'), ('D')
;

WITH
    string_matrix AS (
        SELECT
            t1.string AS code
        FROM
            strings t1
        UNION
        SELECT
            t1.string||t2.string AS code
        FROM
            strings t1
            JOIN strings t2 ON 1=1
        UNION
        SELECT
            t1.string||t2.string||t3.string AS code
        FROM
            strings t1
            JOIN strings t2 ON 1=1
            JOIN strings t3 ON 1=1
        ORDER BY code)
SELECT
    ROW_NUMBER() OVER () AS result, code
FROM string_matrix;
4
  • That doesn't eliminate "duplicates" (where the same characters appear but in a different order) -- that seems to be a requirement.
    – mustaccio
    Oct 18, 2021 at 19:58
  • I don't think that "Order doesn't matter" means to "eliminate duplicates". In any case I believe this comment is wrong because if you join the table with the string_matrix you will get the requested id's without any duplicates. Oct 19, 2021 at 20:54
  • Not something viable when I have to calculate combinations of up to 20 strings if not a few more
    – LordHans
    Oct 22, 2021 at 11:35
  • That is true, this method makes sense only if you have a small list of characters because it avoids the complexity of recursion. The question did't mention the 20 chars though. Oct 24, 2021 at 6:49

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.