[php] Automatische groepindeling op voorkeuren

[rogierslag]

Ik zit met een dilemma met betrekking tot het maken van een automatische groepsindeling.

Het probleem is ongeveer zo:
We hebben een grote groep van ongeveer 400 - 500 personen. Tijdens de inschrijving hebben zij uit 16 interesses er een aantal moeten aankruisen. Het aantal aangekruiste vakjes is niet vastgelegd.
Deze personen moeten vervolgens automatisch geroosterd worden dat ze twee interesses volgen die ze hebben aangegeven en eentje welke ze niet hebben aangegeven. Ze kunnen dezelfde interesse maar een keer volgen. In totaal zijn er drie sessies (ze hebben dus continu iets te doen). Groepen zijn gelimiteerd op een aantal, wat wisselt bij iedere interesse, wel gelijk door tijd. Uit het systeem moet een rooster komen wat per persoon aangeeft welke interesses hij/zij in welke volgorde moet doen.

Per persoon staat in een database wat hij/zij wilt doen. Ook de capaciteit staat in de database. De database is een MySQL database.

Probleem: ik heb geen idee hoe dit te doen. Ik kan wel iedere persoon uit de database halen en aan zoveel mogelijk koppelen, maar mogelijk kunnen dan de laatste personen helemaal niet meer gekoppeld worden. Is hiervoor een handig algoritme om te gebruiken of bieden sommige databases deze functionaliteit direct?

Veel Googlen levert namelijk niet echt iets relevants op en ik zit met de handen in het haar na veel gedoe. Eventueel kan ik ook wel een Java applicatie klussen als PHP totaal ongeschikt blijkt te zijn. Ik wil het in ieder geval wel zelf maken of freeware gebruiken gezien er 0,0 budget is voor een aankoop

In short: wat is de meest efficiënte manier om dit te doen?

[bomberboy]

Het lijkt een beetje op een oude programmingcontest hier op het forum:
Programming Contest Nieuwe Stijl: Contest 3 *uitslagen!*

Je kan daar misschien wat inspiratie opdoen.

[Davio]

En wat nu als er mensen zijn die alles aangevinkt hebben en mensen die niks aangevinkt hebben? Of heeft iedereen precies twee dingen aangevinkt?

En wat nu als iedereen hetzelfde heeft aangevinkt?

[rogierslag]

Mensen die meer dan 3 dingen aanvinken worden bij 3 dingen geplaatst. Een gedeelte zou dan genegeerd moeten worden. Zij die te weinig aanvinken mogen willekeurig als "opvulmiddel" worden gebruikt.

Ik maak nu in de database 2 tijdelijke tabellen: personen met velden 'id','gr1','gr2','gr3', sporten met 'id','gr1','gr2','gr3','total'

Bij personen is gr# een 1 indien die geplaatst is bij een dagdeel en een 0 indien niet. Bij sporten is gr# de hoeveelheid geplaatsten (wat weer kleiner of gelijk is aan total)

[Tharulerz]

Ik denk dat je datamodel al fout zit.

Leer uitnormaliseren.

Een persoon heeft meerdere keuzes, een keuze heeft meerdere personen. Dan heb je dus een tabel keuzes met daarin:

'id' en 'keuze'

Daarin insert je voor elke persoon zijn keuzes (dus per persoon max 3 rijen, eventueel kan je een trigger zetten dat als je een 4e rij probeert te inserten voor een ID hij die gewoon negeert).

Daarna kan je verder werken.

[rogierslag]

Inmiddels heb ik een redelijke oplossing. Helemaal perfect is het natuurlijk niet. Het indelen van ongeveer 400 personen met een capaciteit van 440 personen per sessie duurt ongeveer 10-20 seconden, afhankelijk van de randomness die MySQL heeft.

Tijdens de inschrijving hebben de personen aangegeven welke sporten ze interessant vinden en welke ze beoefenen. Beoefenen is bijvoorbeeld 'golfh' (let op de h van huidig), interessant is 'golf'. De capaciteit per sessie al bij alledrie de sessie gelijk.

Verder is er bewust niet gekozen om drie voorkeuren te forceren, vooral omdat een gedeelte ook handmatig (niet via een pc) wordt ingevoerd en later overgenomen. Tenslotte weten de deelnemers niets van de sportdag, dat is een verrassing. Er teveel op hameren verneukt dat een beetje

In aa_personeninfo heeft iedereen een unieke key van 4 tekens in een combi van cijfers en letters. Dit is de enige relevante info uit die tabel.

Verder is het een vrij simpel algoritme natuurlijk, maar meer dan voldoende voor deze taak. Met de hand duurt het nu namelijk soms uren en dan is het nog lastig ook om voorkeuren te matchen en worden er fouten gemaakt.

Tenslotte de code:

PHP:

<?php
# Deze functie genereert een sportindeling
function GenerateSportIndeling ( )
    {
    global $rDatabaseConnection;
    
    $iStart = microtime(true);
    
    #####
    # Capaciteit en aantal personen ophalen
    $strSelect1 = "SELECT sum(capaciteit) FROM aa_sporten";
    $strSelect2 = "SELECT count(`key`) FROM aa_personeninfo WHERE status!='inschrijf' AND status!='ingeschreven' AND status!='uitgeschreven'";
    $rSelect1 = mysqli_query ( $rDatabaseConnection , $strSelect1 );
    $rSelect2 = mysqli_query ( $rDatabaseConnection , $strSelect2 );
    $aSelect1 = mysqli_fetch_array ( $rSelect1 );
    $aSelect2 = mysqli_fetch_array ( $rSelect2 );
    
    #####
    # TABELLEN AANMAKEN
    
    # Eerst maken we een tabel met personen. ID, gr1, gr2, gr3
    $strCreateTempPersonen = "CREATE TABLE IF NOT EXISTS `aa_temp_persoon` (
    `id` VARCHAR( 4 ) NOT NULL PRIMARY KEY ,
    `gr1` INT ( 2 ) NOT NULL DEFAULT 0,
    `gr2` INT ( 2 ) NOT NULL DEFAULT 0,
    `gr3` INT ( 2 ) NOT NULL DEFAULT 0 
    ) ENGINE = MYISAM ;";
    
    # nu eentje met sporten
    $strCreateTempSporten = "CREATE TABLE IF NOT EXISTS `aa_temp_sport` (
    `id` INT( 11 ) NOT NULL AUTO_INCREMENT PRIMARY KEY ,
    `gr1` INT ( 3 ) NOT NULL ,
    `gr2` INT ( 3 ) NOT NULL ,
    `gr3` INT ( 3 ) NOT NULL ,
    `total` INT ( 3 ) NOT NULL
    ) ENGINE = MYISAM ;";
    
    $rCreateTempPersonen = mysqli_query ( $rDatabaseConnection , $strCreateTempPersonen );
    $rCreateTempSporten = mysqli_query ( $rDatabaseConnection , $strCreateTempSporten );
    
    $rEmptyTempPersonen = mysqli_query ( $rDatabaseConnection , "TRUNCATE TABLE `aa_temp_persoon`");
    $rEmptyTempSporten = mysqli_query ( $rDatabaseConnection , "TRUNCATE TABLE `aa_temp_sport`");
    
    if ( $aSelect1[0] < $aSelect2[0] )
        {
        # meer personen dan capaciteit, stop uitvoering
        echo "<p>De capaciteit van de sporten is onvoldoende om alle personen geplaatst te krijgen. <br>Uitvoer afgebroken</p>";
        return false;
        }
    echo '<p>OV capaciteit: ' . $aSelect1[0] . '<br>Aantal personen: ' . $aSelect2[0] . '</p>';
        
    
    #####
    # TABELLEN VULLEN
    
    $strFillPersoon = "SELECT `key` FROM aa_personeninfo WHERE status!='inschrijf' AND status!='ingeschreven' AND status!='uitgeschreven'";
    $rFillPersoon = mysqli_query ( $rDatabaseConnection , $strFillPersoon );
    while ( $aFillPersoon = mysqli_fetch_array ( $rFillPersoon ) )
        {
        $rIets = mysqli_query ( $rDatabaseConnection , "INSERT INTO aa_temp_persoon (`id`) VALUES ('" . $aFillPersoon[0] . "')");
        }
    
    $strFillSport = "SELECT id,capaciteit FROM aa_sporten";
    $rFillSport = mysqli_query ( $rDatabaseConnection , $strFillSport );
    while ( $aFillSport = mysqli_fetch_array ( $rFillSport ) )
        {
        $rIets = mysqli_query ( $rDatabaseConnection , "INSERT INTO aa_temp_sport (`id`,`total`) VALUES ('" . $aFillSport[0] . "','" . $aFillSport[1] . "')");
        }
        
    #####
    # Sporten ophalen en indelen. Alle indelingen nu gebeuren op voorkeur
    for ( $j=1;$j<5;$j++)
        {
        # 4 verschillende matches die allemaal worden doorlopen
        for ( $i=1;$i<4;$i++ )
            {
            # 3 groepen
            $strSelectSporten = "SELECT match".$j.",id,capaciteit FROM aa_sporten ORDER BY id ASC";
            $rSelectSporten = mysqli_query ( $rDatabaseConnection , $strSelectSporten );
            while ( $aSelectSporten = mysqli_fetch_array ( $rSelectSporten ) )
                {
                if ( $aSelectSporten[0] == NULL )
                    # Indien match gelijk aan NULL, skip die match
                    continue 2;
                $strSelectPersoon = "SELECT `key` FROM aa_personeninfo persoon LEFT JOIN aa_interesses intr ON intr.ID=persoon.`key` WHERE status!='inschrijf' AND status!='ingeschreven' AND status!='uitgeschreven' AND intr." . $aSelectSporten[0] . "='1' ORDER BY RAND() LIMIT 0," . $aSelectSporten[2];
                $rSelectPersoon = mysqli_query ( $rDatabaseConnection , $strSelectPersoon );
                while ( $aSelectPersoon = mysqli_fetch_array ( $rSelectPersoon ) )
                    {
                    # Persoon koppelen
                    $strSelect = "SELECT gr1,gr2,gr3 FROM aa_temp_persoon WHERE `id`='" . $aSelectPersoon[0] . "'";
                    $rSelect = mysqli_query ( $rDatabaseConnection , $strSelect );
                    $aSelect = mysqli_fetch_array ( $rSelect );
                    if ( $aSelect[$i-1] != 0 )
                        # Indien al iets ingevuld
                        continue;
                    if ( $aSelect[0] == $aSelectSporten[1] || $aSelect[1] == $aSelectSporten[1] || $aSelect[2] == $aSelectSporten[1] )
                        # Als die al gekoppeld is aan de sport niet nogmaals koppelen
                        continue;
                    
                    # Persoon koppelen, één extra bijtellen bij de sport voor die groep
                    $strUpdate = "UPDATE aa_temp_persoon SET gr".$i."='" . $aSelectSporten[1] . "' WHERE `id`='" . $aSelectPersoon[0] . "'";
                    $rUpdate = mysqli_query ( $rDatabaseConnection , $strUpdate );
                    $strUpdate = "UPDATE aa_temp_sport SET gr".$i."=gr".$i."+1 WHERE `id`='" . $aSelectSporten[1] . "'";
                    $rUpdate = mysqli_query ( $rDatabaseConnection , $strUpdate);
                    $strSelect = "SELECT gr".$i.",total FROM aa_temp_sport WHERE `id`='" . $aSelectSporten[1] . "'";
                    $rSelect = mysqli_query ( $rDatabaseConnection , $strSelect );
                    $aSelect = mysqli_fetch_array ( $rSelect );
                    if ( $aSelect[0] >= $aSelect[1] )
                        # Aantal is nu hoger dan capaciteit, sport afbreken
                        continue 2;
                    }
                }
            }
        }
        
        
    #####
    # Niet ingedeelde personen indelen. Voorkeuren zijn op, dus nu random
    $strSelectPersonen = "SELECT id,gr1,gr2,gr3 FROM aa_temp_persoon WHERE gr1=0 OR gr2=0 OR gr3=0 ORDER BY RAND()";
    $rSelectPersonen = mysqli_query ( $rDatabaseConnection , $strSelectPersonen );
    while ( $aSelectPersonen = mysqli_fetch_array ( $rSelectPersonen ) )
        {
        # Controleren wanneer vrij
        for ( $i = 1; $i < 4; $i++ )
            {
            # doorgaan indien niet leeg
            if ( $aSelectPersonen[$i] != 0 )
                continue;
                
            while (true)
                {
                $strSelect = "SELECT id FROM aa_temp_sport WHERE gr".$i."<total ORDER BY RAND()";
                $rSelect = mysqli_query ( $rDatabaseConnection , $strSelect );
                $aSelect = mysqli_fetch_array ( $rSelect );
                
                if ( $aSelect[0] == $aSelectPersonen[1] || $aSelect[0] == $aSelectPersonen[2] || $aSelect[0] == $aSelectPersonen[3] ) 
                    # Niet tweemaal zelfde sport
                    continue;
                    
                break;
                }       
            
            # Updaten   
            $strUpdate = "UPDATE aa_temp_persoon SET gr".$i."='".$aSelect[0]."' WHERE id='" . $aSelectPersonen[0] . "'";
            $rUpdate = mysqli_query ( $rDatabaseConnection , $strUpdate );
            $strUpdate = "UPDATE aa_temp_sport SET gr".$i."=gr".$i."+1 WHERE id='" . $aSelect[0] . "'";
            $rUpdate = mysqli_query ( $rDatabaseConnection , $strUpdate );
            }
        }
    $iStop = microtime(true);
    
    echo '<p>Het genereren van een nieuw sportoverzicht is voltooid. De indeling duurde ' . round($iStop-$iStart,3) . ' seconden.</p>';
    return true;
    }
?>

De tabel aa_sporten ziet er zo uit

SQL:

-- 
-- Tabel structuur voor tabel `aa_sporten`
-- 

CREATE TABLE `aa_sporten` (
  `id` int(11) NOT NULL auto_increment,
  `naam` varchar(128) NOT NULL,
  `capaciteit` int(3) NOT NULL,
  `match1` varchar(32) NOT NULL,
  `match2` varchar(32) default NULL,
  `match3` varchar(32) default NULL,
  `match4` varchar(32) default NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM;

-- 
-- Gegevens worden uitgevoerd voor tabel `aa_sporten`
-- 

INSERT INTO `aa_sporten` VALUES (1, 'hockey', 40, 'hockey', 'hockeyh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (2, 'tennis', 18, 'tennis', 'tennish', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (3, 'klimmen', 16, 'klimmen', 'klimmenh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (4, 'voetbal', 60, 'voetbal', 'voetbalh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (5, 'cultuur', 30, 'lancet', 'lanceth', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (6, 'dansen', 20, 'dans', 'mdans', 'dansh', 'mdansh');
INSERT INTO `aa_sporten` VALUES (7, 'muziek', 25, 'band', 'bandh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (8, 'foto', 30, 'foto', 'fotoh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (9, 'golf', 16, 'golf', 'golfh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (10, 'basketbal', 30, 'basketbal', 'basketbalh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (11, 'rugby', 30, 'rugby', 'rugbyh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (13, 'Vrij', 3, '', NULL, NULL, NULL);
INSERT INTO `aa_sporten` VALUES (14, 'roeien', 40, 'roeien', 'roeienh', NULL, NULL);
INSERT INTO `aa_sporten` VALUES (15, 'squash', 40, 'squash', 'squashh', NULL, NULL);

[Verwijderd]

Ik heb dit gemaakt voor profielwerkstuk, ik ga de source nog open maken. Het staat nu even op http://activiteito.nl/ . Als je een DM stuurt als je een account hebt gemaakt, help ik je wel verder! (als het nog nodig is)

[ Voor 5% gewijzigd door Verwijderd op 01-05-2010 18:38 ]