代码之家 › 专栏 › 技术社区 › Ali Sheikhpour

SQL:如何生成不存在的组合

sql-server sql

Ali Sheikhpour · 技术社区 · 7 年前

我想通过两个单词的组合来创建一个巨大的列表。字典里的每一个词都应该和其他词结合起来。换句话说,我会 Total^2

this Q/A 生成所有可能的组合,但我不知道如何使用SQL查询查找不存在的组合可能是这样的:

select * from words a ... join words b 
where (a.id, b.id) not in (select * from combinaions)

如果SQL对此没有直接的解决方案,请您推荐一种算法来编程实现。请注意,可能有一些遗漏 身份证件

餐桌组合话

3 回复 | 直到 7 年前

VahiD 7 年前

您可以使用交叉连接来拥有所有可能的组合,然后根据条件,您可以移除已经存在的组合。

Select * from words a cross join words b 
where not exists (select * from combinations c where c.first_id = a.id and c.second_id = b.id)

Zack 7 年前

CROSS JOIN 是拼图的中心部分。除了使用子查询,您还可以 LEFT JOIN 交叉连接 字数,并检查 NULL s(意味着给定的笛卡尔积组合不存在于现有的组合表中)。

例如:

WITH 
    -- sample data (notice that there's no word with ID of 3)
    words(word_id, word) AS
    (
        SELECT 1, 'apple'   UNION ALL
        SELECT 2, 'pear'    UNION ALL
        SELECT 4, 'orange'  UNION ALL
        SELECT 5, 'banana'
    )
    -- existing combinations
    ,combinations(first_id, second_id) AS
    (
        SELECT 1, 2 UNION ALL
        SELECT 1, 5 UNION ALL
        SELECT 2, 4 UNION ALL
        SELECT 2, 5 UNION ALL
        SELECT 4, 5
    )
    -- this is the CTE you'll use to create the cartesian product
    -- of all words in your words table. You can also put this as a 
    -- sub-query, but I'd argue that a CTE makes it clearer.
    ,cartesian(w1_id, w1_word, w2_id, w2_word) AS
    (
        SELECT *
        FROM words w1, words w2
    )
-- the actual query
SELECT * 
FROM cartesian
    LEFT JOIN combinations ON
        combinations.first_id = cartesian.w1_id
        AND combinations.second_id = cartesian.w2_id
WHERE combinations.first_id IS NULL

现在,一个重要的警告是,在相同的情况下,此查询不考虑组合 word1 和 word2 (1,2) 不等于 (2,1) . 但是,解决此问题只需调整联接即可:

SELECT * 
FROM cartesian
    LEFT JOIN combinations ON
        (combinations.first_id = cartesian.w1_id OR combinations.first_id = cartesian.w2_id)
        AND
        (combinations.second_id = cartesian.w1_id OR combinations.second_id = cartesian.w2_id)
WHERE combinations.first_id IS NULL

Tim Mylott 7 年前

这是另一个选择。在子查询中构建完整列表,并将其放在组合表的外部以查找缺少的内容。

DECLARE @Words TABLE
    (
        [Id] INT
      , [Word] NVARCHAR(200)
    );

DECLARE @WordCombo TABLE
    (
        [Id1] INT
      , [Id2] INT
    );

INSERT INTO @Words (
                       [Id]
                     , [Word]
                   )
VALUES ( 1, N'Cat' )
     , ( 2, N'Taco' )
     , ( 3, N'Test' )
     , ( 4, N'Cake' )
     , ( 5, N'Apple' )
     , ( 6, N'Pear' );

INSERT INTO @WordCombo (
                           [Id1]
                         , [Id2]
                       )
VALUES ( 1, 2 )
     , ( 2, 6 )
     , ( 5, 3 )
     , ( 5, 1 );

--select from a sub query that builds out all combinations and then left outer to find what's missing in @WordCombo
SELECT          [fulllist].[Id1]
              , [fulllist].[Id2]
FROM            (
                    --Rebuild full list
                    SELECT     [a].[Id] AS [Id1]
                             , [b].[Id] AS [Id2]
                    FROM       @Words [a]
                    INNER JOIN @Words [b]
                        ON 1 = 1
                    WHERE      [a].[Id] <> [b].[Id] --Would a word be combined with itself?

                ) AS [fulllist]
LEFT OUTER JOIN @WordCombo [wc]
    ON [wc].[Id1] = [fulllist].[Id1]
       AND [wc].[Id2] = [fulllist].[Id2]
WHERE           [wc].[Id1] IS NULL;