# 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, your table wouldn't contain codes "ABC" and "ACB"? Oct 15, 2021 at 12:17
• Hi, and welcome to dba.se! Will your list only ever contain 5 elements? Oct 15, 2021 at 14:19

## 2 Answers

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
``````
• Fun extension to handle strings with a length > 1: dbfiddle.uk/… 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 Oct 18, 2021 at 6:18

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;
``````
• That doesn't eliminate "duplicates" (where the same characters appear but in a different order) -- that seems to be a requirement. 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 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