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.
精彩评论