生成字符串列表的所有组合

Question

我正在尝试生成 Strings 列表的所有组合 list = ['A', 'B', 'C', 'D']。

我想生成所有可能性，然后在数据库中搜索

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

我的专栏是这样的：

结果	代码
1	A
2	公元前
3	交流电
4	乙
5	ABC
6	广告
7	BCD
8	光盘
9	A B C D
10	阿布德
…………	......

澄清一下：顺序并不重要（ABC = BAC = CAB），它应该返回多个结果（对于 list = ['A', 'B', 'C'] 与上面的 10 列相同，它应该返回 [1 、2、3、4、5]）。

我正在使用 Postgres，并且尝试过一些我见过的递归函数，但没有一个能够完全满足我的需求。

Answer 1

所以我不确定你为什么要这样做，但我假设你已经用尽了所有其他选择。

TLDR，他是一个小提琴手，可以做你想做的事：https://dbfiddle.uk/? rdbms=postgres_13&fiddle=27cdc7ef6eaf179936d4d048276b139b

解释

为此，我们需要三件事：

1. 元素列表
2. 具有我们为此目的同意的排序顺序的排序规则
3. 用于构建元组的递归查询

排序规则很重要，因为如果我们说 AB = BA，那么在数据库中进行比较并不容易，尤其是随着长度的增长。然而，我们可以对数据库中的字符串进行排序，并强制执行位置 n 中的字符必须小于位置 n+1 中的字符的条件。这使得字符串 BA 成为无效结构。

我们需要递归，因为我们必须从先前的元素串联构建字符串。这在 Postgres 中可以通过使用递归 CTE来实现。

从逻辑上讲，该过程的工作原理如下：

1. 从所有独特的元素开始
2. 对于先前的结果，连接大于最后一个元素的元素
3. 附加输出并重复

这是自动终止的，因为一旦字符串的长度等于元素的数量，就没有元素大于最后一个元素。

代码

首先，需要一个元素表：

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))
)

接下来，填充该表：

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

最后，递归查询来构建所需的输出：

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

元素是否可以重复（AA、AAA、BB 等）

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

这里我们可以将 or 条件更改为 >=，但是我们需要根据元素数量终止递归。

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