使用SQL查询生成时间表的所有可能组合

Question

我有一个尴尬的SQL拼图,它击败了我.

我正在尝试生成学生单元的可能配置列表,以便我可以将他们的课程选择纳入时间表.学生可能的资格和学习列表如下:

Biology A
Biology C 
Biology D 
Biology E 

Chemistry B 
Chemistry C 
Chemistry D 
Chemistry E 
Chemistry F 

Computing D
Computing F 

Tutorial A 
Tutorial B 
Tutorial E 

可以为学生提供可能的积木解决方案

Biology D
Chemistry C 
Computing F 
Tutorial E 

如何查询上述数据集,为学生生成课程和块的所有可能组合？然后,我可以削减列表,删除那些冲突并选择一个有效的列表.我估计在这种情况下总共会有大约120种组合.

我可以想象它会是某种交叉连接.我已经尝试了使用窗口函数和交叉应用等各种解决方案,但它们都有一些缺陷.他们都往往被绊倒,因为每个学生都有不同数量的课程,每门课程都有不同数量的课程.

欢呼为您提供任何帮助!如果有必要,我可以粘贴在我的查询的粗糙混乱中!

亚历克斯

Answer 1

对于固定数量的资格,答案相对简单 - CROSS JOIN以前答案中的选项将完美地运作.

但是,如果资格数量未知,或将来可能发生变化,则硬编码四项CROSS JOIN操作将无效.在这种情况下,答案变得更加复杂.

对于少量行,您可以在DBA上使用此答案的变体,它使用2的幂和比特比较来生成组合.但是,这将限于非常少的行.

对于较大数量的行,您可以使用函数从"N"行生成"M"数字的每个组合.然后,您可以将其连接到ROW_NUMBER源数据上计算的值以获取原始行.

生成组合的功能可以写在TSQL的,但它会使尽可能使用SQLCLR更有意义:

[SqlFunction(
    DataAccess = DataAccessKind.None,
    SystemDataAccess = SystemDataAccessKind.None,
    IsDeterministic = true,
    IsPrecise = true,
    FillRowMethodName = "FillRow",
    TableDefinition = "CombinationId bigint, Value int"
)]
public static IEnumerable Combinations(SqlInt32 TotalCount, SqlInt32 ItemsToPick)
{
    if (TotalCount.IsNull || ItemsToPick.IsNull) yield break;

    int totalCount = TotalCount.Value;
    int itemsToPick = ItemsToPick.Value;
    if (0 >= totalCount || 0 >= itemsToPick) yield break;

    long combinationId = 1;
    var result = new int[itemsToPick];
    var stack = new Stack<int>();
    stack.Push(0);

    while (stack.Count > 0)
    {
        int index = stack.Count - 1;
        int value = stack.Pop();

        while (value < totalCount)
        {
            result[index++] = value++;
            stack.Push(value);

            if (index == itemsToPick)
            {
                for (int i = 0; i < result.Length; i++)
                {
                    yield return new KeyValuePair<long, int>(
                        combinationId, result[i]);
                }

                combinationId++;
                break;
            }
        }
    }
}

public static void FillRow(object row, out long CombinationId, out int Value)
{
    var pair = (KeyValuePair<long, int>)row;
    CombinationId = pair.Key;
    Value = pair.Value;
}

(基于此功能.)

一旦功能到位,生成有效组合列表相当容易:

DECLARE @Blocks TABLE 
(
    Qualification varchar(10) NOT NULL, 
    Block char(1) NOT NULL, 
    UNIQUE (Qualification, Block)
);

INSERT INTO @Blocks 
VALUES
    ('Biology', 'A'),
    ('Biology', 'C'), 
    ('Biology', 'D'), 
    ('Biology', 'E'),
    ('Chemistry', 'B'), 
    ('Chemistry', 'C'), 
    ('Chemistry', 'D'), 
    ('Chemistry', 'E'), 
    ('Chemistry', 'F'), 
    ('Computing', 'D'),
    ('Computing', 'F'), 
    ('Tutorial', 'A'), 
    ('Tutorial', 'B'), 
    ('Tutorial', 'E') 
;

DECLARE @Count int, @QualificationCount int;

SELECT
    @Count = Count(1),
    @QualificationCount = Count(DISTINCT Qualification)
FROM
    @Blocks
;

WITH cteNumberedBlocks As
(
    SELECT
        ROW_NUMBER() OVER (ORDER BY Qualification, Block) - 1 As RowNumber,
        Qualification,
        Block
    FROM
        @Blocks
),
cteAllCombinations As
(
    SELECT
        C.CombinationId,
        B.Qualification,
        B.Block
    FROM
        dbo.Combinations(@Count, @QualificationCount) As C
        INNER JOIN cteNumberedBlocks As B
        ON B.RowNumber = C.Value
),
cteMatchingCombinations As
(
    SELECT
        CombinationId
    FROM
        cteAllCombinations
    GROUP BY
        CombinationId
    HAVING
        Count(DISTINCT Qualification) = @QualificationCount
    And
        Count(DISTINCT Block) = @QualificationCount
)
SELECT
    DENSE_RANK() OVER(ORDER BY C.CombinationId) As CombinationNumber,
    C.Qualification,
    C.Block
FROM
    cteAllCombinations As C
    INNER JOIN cteMatchingCombinations As MC
    ON MC.CombinationId = C.CombinationId
ORDER BY
    CombinationNumber,
    Qualification
;

此查询将生成172行的列表,表示43个有效组合:

1  Biology    A
1  Chemistry  B
1  Computing  D
1  Tutorial   E

2  Biology    A
2  Chemistry  B
2  Computing  F
2  Tutorial   E
...

如果您需要该Combinations函数的TSQL版本:

CREATE FUNCTION dbo.Combinations
(
    @TotalCount int,
    @ItemsToPick int
)
Returns @Result TABLE
(
    CombinationId bigint NOT NULL,
    ItemNumber int NOT NULL,
    Unique (CombinationId, ItemNumber)
)
As
BEGIN
DECLARE @CombinationId bigint;
DECLARE @StackPointer int, @Index int, @Value int;
DECLARE @Stack TABLE 
( 
    ID int NOT NULL Primary Key,
    Value int NOT NULL
);
DECLARE @Temp TABLE
(
    ID int NOT NULL Primary Key,
    Value int NOT NULL Unique
);

    SET @CombinationId = 1;

    SET @StackPointer = 1;
    INSERT INTO @Stack (ID, Value) VALUES (1, 0);

    WHILE @StackPointer > 0
    BEGIN
        SET @Index = @StackPointer - 1;
        DELETE FROM @Temp WHERE ID >= @Index;

        -- Pop:
        SELECT @Value = Value FROM @Stack WHERE ID = @StackPointer;
        DELETE FROM @Stack WHERE ID = @StackPointer;
        SET @StackPointer -= 1;

        WHILE @Value < @TotalCount
        BEGIN
            INSERT INTO @Temp (ID, Value) VALUES (@Index, @Value);
            SET @Index += 1;
            SET @Value += 1;

            -- Push:
            SET @StackPointer += 1;
            INSERT INTO @Stack (ID, Value) VALUES (@StackPointer, @Value);

            If @Index = @ItemsToPick
            BEGIN
                INSERT INTO @Result (CombinationId, ItemNumber)
                SELECT @CombinationId, Value
                FROM @Temp;

                SET @CombinationId += 1;
                SET @Value = @TotalCount;
            END;
        END;
    END;

    Return;
END

它与SQLCLR版本几乎相同,除了TSQL没有堆栈或数组这一事实,所以我不得不用表变量伪造它们.