Generate unique pairings -- a "Fixture" -- from a table

I have a table with:

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

And so on ...

And I need to combine them to each-other by class id (in the example I am combining them by name) randomly but in some sort of group, the result should be like this:

Table 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

as you can see no group contains the same record twice.

Something similar to game fixtures in a sports tournaments, if this makes my question easier to understand.

I need either a MySQL line or a PHP functio开发者_如何学Gon, whatever works better.

---

I went ahead and coded this in MySQL as a challenge/exercise.

Given the tables:

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

And:

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

And the data:

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

Then this procedure:

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 ;

Called the first time with:

call BuildFixtureTable( 1 );

Generates this table:

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

---

Your second table should only specify associations (an adjacency matrix):

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 being the "connection ID".

After you've got that, you can use MySQL's JOIN.

To generate all the combinations of the Home and Away columns you need an algorithm like this: http://labix.org/snippets/permutations#head-132e017244f864c098296f85de0f112916e82001. In the example you've provided, K=2 and N=4.