生成独特的配对——“夹具” ——来自表格

Question

我有一个表：

ID | NAME | CLASS
------------------
1  | Aaa  | 1
2  | Bbb  | 1
3  | Ccc  | 1
4  | Ddd  | 1

等等...

我需要按类 id 将它们随机组合在一起（在示例中我按名称组合它们），但在某种组中，结果应该是这样的：

表 2

ID | Home | Away | Class | Group
----------------------------------
1  | Aaa  | Bbb  | 1     |  1
2  | Ccc  | Ddd  | 1     |  1
3  | Bbb  | Ccc  | 1     |  2
4  | Ddd  | Aaa  | 1     |  2
5  | Aaa  | Ccc  | 1     |  3
6  | Bbb  | Ddd  | 1     |  3

可以看出，没有组包含两次相同的记录。

类似于体育锦标赛中的比赛装置，如果这能让我的问题更容易理解的话。

我需要 MySQL 行或 PHP 函数，无论哪种效果更好。

Answer 1

我继续在 MySQL 中将其编码为挑战/练习。

给定表：

CREATE TABLE IF NOT EXISTS  Teams  (
    ID          INT         NOT NULL AUTO_INCREMENT,
    Name        VARCHAR(25) NOT NULL,
    Class       INT         NOT NULL,
    PRIMARY KEY ( ID ),
    UNIQUE KEY  UniqName  ( Name )
);

和：

CREATE TABLE IF NOT EXISTS  Matchups  (
    ID          INT         NOT NULL AUTO_INCREMENT,
    Home        VARCHAR(25) NOT NULL,
    Away        VARCHAR(25) NOT NULL,
    Class       INT         DEFAULT NULL,
    GroupNum    INT         DEFAULT NULL,
    PRIMARY KEY ( ID ),
    KEY  Home  ( Home , Away )
);

和数据：

INSERT INTO     Teams (Name, CLASS)
VALUES          ('Astros',      1),
                ('Bears',       1),
                ('Cubs',        1),
                ('Dragons',     1),
                ('Eagles',      1),
                ('Firebirds',   2),
                ('Giants',      2);

然后此过程：

DROP PROCEDURE IF EXISTS BuildFixtureTable;
DELIMITER //

CREATE PROCEDURE BuildFixtureTable(IN ClassNum INT)
BEGIN
    DROP TABLE IF EXISTS tmpPool;
    DROP TABLE IF EXISTS tmpFixture;

    CREATE TEMPORARY TABLE tmpPool (
        J           INT NOT NULL AUTO_INCREMENT,
        ID          INT NOT NULL,
        unpicked    BIT NOT NULL DEFAULT 1
        , PRIMARY KEY ( J )
    );
    CREATE TEMPORARY TABLE tmpFixture (
        ID          INT NOT NULL AUTO_INCREMENT,
        HomeID      INT NOT NULL,
        AwayID      INT NOT NULL,
        GrpNum      INT NOT NULL,
        PRIMARY KEY ( `ID` )
    );

    INSERT INTO tmpPool (ID)
    SELECT      ID
    FROM        Teams
    WHERE       Class = ClassNum
    ORDER BY    ID;

    SELECT  COUNT(*)  INTO  @NumTeams  FROM tmpPool;
    IF @NumTeams % 2    THEN
        INSERT INTO tmpPool (ID) VALUES (0);
        SET @NumTeams       = @NumTeams + 1;
    END IF;

    ALTER TABLE  tmpPool  CHANGE COLUMN J  J  INT      NOT NULL
    , ADD INDEX  J_foo  (J ASC)
    , DROP PRIMARY KEY;

    SET SQL_SAFE_UPDATES    = 0;   -- Kill bogus warnings on updates.

    SET     @GroupNum       = 1;
    WHILE   @GroupNum < @NumTeams  DO
        REPEAT
            SELECT  ID INTO @Home FROM tmpPool  WHERE unpicked = 1  ORDER BY J ASC   LIMIT 1;
            SELECT  ID INTO @Away FROM tmpPool  WHERE unpicked = 1  ORDER BY J DESC  LIMIT 1;

            INSERT INTO tmpFixture (HomeID, AwayID, GrpNum)
            VALUES      (@Home, @Away, @GroupNum);

            UPDATE  tmpPool  SET unpicked = 0  WHERE ID = @Home  OR  ID = @Away;

            SELECT  COUNT(*) INTO  @TeamsLeft  FROM tmpPool  WHERE unpicked = 1;

        UNTIL @TeamsLeft < 1
        END REPEAT;

        SET @GroupNum = @GroupNum + 1;
        UPDATE  tmpPool  SET unpicked = 1;
        /*--- Do the "round robin" shuffle. This is the secret sauce.
        */
        UPDATE  tmpPool  SET J = J + 1  WHERE J > 1;
        UPDATE  tmpPool  SET J = 2      WHERE J = @NumTeams + 1;
    END WHILE;

    /*--- Now Update the payload table.
    */
    INSERT INTO
        Matchups (Home, Away, Class, GroupNum)
    SELECT
        IF( F.HomeID = 0, (SELECT Name  FROM Teams T WHERE T.ID = F.AwayID), (SELECT Name  FROM Teams T WHERE T.ID = F.HomeID) ),
        IF( F.AwayID = 0 || F.HomeID = 0, '*na*', (SELECT Name FROM Teams T WHERE T.ID = F.AwayID) ),
        ClassNum,
        F.GrpNum
    FROM
        tmpFixture  F
    ORDER BY
        F.GrpNum,
        1;
END//
DELIMITER ;

第一次调用：

call BuildFixtureTable( 1 );

生成此表：

ID      Home        Away    Class   GroupNum
 1      Astros      *na*      1         1
 2      Bears       Eagles    1         1
 3      Cubs        Dragons   1         1
 4      Astros      Eagles    1         2
 5      Bears       Cubs      1         2
 6      Dragons     *na*      1         2
 7      Astros      Dragons   1         3
 8      Bears       *na*      1         3
 9      Eagles      Cubs      1         3
10      Astros      Cubs      1         4
11      Dragons     Bears     1         4
12      Eagles      *na*      1         4
13      Astros      Bears     1         5
14      Cubs        *na*      1         5
15      Dragons     Eagles    1         5

Answer 2

您的第二个表应仅指定关联（邻接矩阵）：

C_ID | Home | Away | Class | Group
----------------------------------
1    | 1    | 2    | 1     |  1
2    | 3    | 4    | 1     |  1
3    | 2    | 3    | 1     |  2
4    | 4    | 1    | 1     |  2
5    | 1    | 3    | 1     |  3
6    | 2    | 4    | 1     |  3

C_ID是“连接 ID”。

完成后，您可以使用MySQL的JOIN。

要生成 Home 和 Away 列的所有组合，您需要这样的算法：http://labix.org/snippets/permutations#head-132e017244f864c098296f85de0f112916e82001。在您提供的示例中，K=2 且 N=4。