主页 / dba / 问题 / 301181
Accepted
LordHans
Asked: 2021-10-16 03:10:28 +0800 CST

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

  • 772

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

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

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

我的专栏是这样的：

结果 代码
1 一个
2 公元前
3 交流电
4 乙
5 美国广播公司
6 广告
7 BCD
8 光盘
9 A B C D
10 ABD
………… ……

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

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

postgresql recursive

2 个回答

  1. Best Answer

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

    TLDR，他可以做你想做的事：https ://dbfiddle.uk/?rdbms=postgres_13&fiddle=27cdc7ef6eaf179936d4d048276b139b

    解释

    为此，我们需要三件事：

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

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

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

    从逻辑上讲，该过程是这样工作的：

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

  2. 您不需要递归，您可以计算所有可能的字符串组合的矩阵。
    我发现这更直接：

    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;
    • 1

相关问题