Voilà à quoi j'arrive (cela requiert de créer d'abord une table d'integers pour l'initialisation des students):
Logiquement, il est possible de mettre de grosses grosses valeurs dans les "SET", de lancer le calcul dans un client, et de se connecter avec un autre client pour "auditer" la table "test_students_result", et obtenir des résultats intermédiaires pendant le calcul (qu'on peut alors laisser traîner sur plusieurs heures ou une nuit entière).
Code :
DROP TABLE IF EXISTS test_students; -- List of students (temporary table for calculation)
CREATE TABLE test_students (id INT UNSIGNED NOT NULL, classroom INT UNSIGNED NULL, PRIMARY KEY (id)) ENGINE=HEAP;
DROP TABLE IF EXISTS test_students_result; -- List of students (real result you should look to)
CREATE TABLE test_students_result (id INT UNSIGNED NOT NULL, classroom INT UNSIGNED NULL, PRIMARY KEY (id)) ENGINE=HEAP;
DROP TABLE IF EXISTS test_classrooms; -- List of classrooms
CREATE TABLE test_classrooms (id INT UNSIGNED NOT NULL, globalScore DOUBLE NULL, score DOUBLE NULL, PRIMARY KEY (id)) ENGINE=HEAP;
DROP PROCEDURE IF EXISTS test_students_n_classes;
DROP PROCEDURE IF EXISTS test_eval_classrooms_scores;
DELIMITER $$
CREATE PROCEDURE test_eval_classrooms_scores(
studentsPerClass DOUBLE)
BEGIN
UPDATE test_classrooms AS c
INNER JOIN (
SELECT
c.id,
SUM(tr.strength)
-- AVG(tr.strength)/(0.1 + STD(tr.strength))
AS score
FROM test_classrooms AS c
INNER JOIN test_students AS f ON f.classroom = c.id
INNER JOIN test_students AS t ON t.id > f.id AND t.classroom = c.id
INNER JOIN test_relations AS tr ON tr.id_from = f.id AND tr.id_to = t.id
GROUP BY c.id) AS scores ON scores.id = c.id
SET
-- If we do some "fake Swaps", then number of students in a classroom may differ from initial distribution, in such case, give this difference a weight
-- The goal is to have balanced classrooms (globalScore is always negative, and the farther from balanced classroom, the more negative score)
c.globalScore = -POW( (SELECT SUM(1) FROM test_students AS s WHERE s.classroom = c.id)-studentsPerClass,2 )*SQRT(studentsPerClass),
c.score = scores.score + c.globalScore
;
END$$
CREATE PROCEDURE test_students_n_classes (
eleves INT UNSIGNED,
partitionnings INT UNSIGNED,
tries INT UNSIGNED,
iterationsPerTry INT UNSIGNED,
fakeSwapsProportion DOUBLE)
BEGIN
SET @tryScore := NULL;
SET @tries := tries;
WHILE (@tries > 0) DO
-- We create a random partitionning
SET @currentScore := NULL;
UPDATE test_students SET classroom = FLOOR(1+RAND()*partitionnings);
-- We try a change, then eval the new partitionning score, and if better, keep that change effective
SET @iterationsPerTry := iterationsPerTry;
WHILE (@iterationsPerTry > 0) DO
SET @randomStud1 := FLOOR(1+RAND()*eleves);
SET @randomClass1 := (SELECT classroom FROM test_students WHERE id = @randomStud1);
SET @randomClass2 := (SELECT id FROM test_classrooms AS c WHERE c.id != @randomClass1 ORDER BY RAND() LIMIT 1);
SET @randomStud2 := (SELECT id FROM test_students AS s WHERE s.classroom = @randomClass2 ORDER BY RAND() LIMIT 1);
UPDATE test_students AS s SET classroom = @randomClass2 WHERE s.id = @randomStud1;
IF (RAND() > fakeSwapsProportion) THEN
UPDATE test_students AS s SET classroom = @randomClass1 WHERE s.id = @randomStud2;
END IF;
CALL test_eval_classrooms_scores(eleves/partitionnings);
SET @newScore := (
SELECT
SUM(score)
-- AVG(score)/(0.01 + STD(score))
FROM test_classrooms AS t);
IF (@newScore > @currentScore OR @currentScore IS NULL) THEN
SET @currentScore := @newScore;
SET @iterationsPerTry := iterationsPerTry;
ELSE
UPDATE test_students AS s SET classroom = @randomClass1 WHERE s.id = @randomStud1;
UPDATE test_students AS s SET classroom = @randomClass2 WHERE s.id = @randomStud2;
SET @iterationsPerTry := @iterationsPerTry - 1;
END IF;
END WHILE;
IF (@currentScore > @tryScore OR @tryScore IS NULL) THEN
TRUNCATE TABLE test_students_result;
INSERT INTO test_students_result (SELECT * FROM test_students);
SET @tryScore := @currentScore;
SET @tries := tries;
ELSE
SET @tries := @tries - 1;
END IF;
END WHILE;
COMMIT;
END$$
DELIMITER ;
-- Step 0: values
SET @eleves := 60;
SET @partitionnings := 3;
SET @tries := 20; -- Actually, it's the number of consecurive failed tries
SET @iterationsPerTry := 200; -- Actually, it's the number of consecutive failed iterations in a try
SET @fakeSwapsProportion := 0.2; -- Probability 0(=only swaps)..1(=no swap) of moving student B to class cA when swapping students A and B from classrooms cA and cB
TRUNCATE TABLE test_students;
INSERT INTO test_students (SELECT n AS id, NULL FROM integers WHERE n BETWEEN 1 AND @eleves);
TRUNCATE TABLE test_classrooms;
INSERT INTO test_classrooms (SELECT n AS id, NULL, NULL AS score FROM integers WHERE n BETWEEN 1 AND @partitionnings);
-- Step 1: each pair of student must have an "affinity score", from 0 (they "must" not be together) to 1 (they "must" be together in a class)
-- Commented out are some suggestions to try
TRUNCATE TABLE test_relations;
INSERT INTO test_relations (id_from, id_to, strength) (
SELECT
f.id,
t.id,
-- IF(FLOOR(f.id / (@eleves/@partitionnings)) = FLOOR(t.id / (@eleves/@partitionnings)), 1, 0)
-- f.id / t.id
RAND()
FROM test_students AS f
INNER JOIN test_students AS t ON t.id > f.id);
-- Step 2: calculate
CALL test_students_n_classes(@eleves, @partitionnings, @tries, @iterationsPerTry, @fakeSwapsProportion);
-- Step 3: results!
SELECT
c.id,
c.score,
c.globalScore,
GROUP_CONCAT(s.id ORDER BY s.id ASC) AS students,
SUM(1) AS studentCount
FROM test_classrooms AS c
INNER JOIN test_students_result AS s ON s.classroom = c.id
GROUP BY c.id
ORDER BY studentCount;
SELECT * FROM test_relations;Logiquement, il est possible de mettre de grosses grosses valeurs dans les "SET", de lancer le calcul dans un client, et de se connecter avec un autre client pour "auditer" la table "test_students_result", et obtenir des résultats intermédiaires pendant le calcul (qu'on peut alors laisser traîner sur plusieurs heures ou une nuit entière).