[VBA] Code-ontwerp voor brute-forcen

[Clock]

Hallo,

Dit topic is een vervolg op mijn topic van vorige week. Omdat het probleem nu een andere is dan die omschreven staat in de topicstart, en om jullie een boel leeswerk en discussie te besparen, heb ik in overleg met de modjes dit nieuwe topic geopend.

Ik wil door middel van brute-force een ideale verdeling maken. Alle code en ideeen om de beste verdeling te selecteren uit de hele groep is klaar, echter heb ik een probleem met het genereren van alle mogelijke mogelijkheden.

Voor de duidelijkheid onderstaande afbeelding:

k zoek een manier op alle mogelijke verdelingen door te lopen. Het zal dan gaan om enkele miljoenen mogelijke planningen.

Voorwaarden/beperkingen:
- Per object kan het aantal persoon-slots variëren (tussen 0 en 3)
- Een persoon kan per planning maar toegewezen worden aan 1 object. (bij een volgende iteratie/planning weer aan een ander object natuurlijk)

Alvast heel erg bedankt!

[ Voor 3% gewijzigd door Clock op 17-03-2010 11:32 ]

[Haan]

Niet om je meteen te ontmoedigen, maar is performance een factor die van belang is? Want ik voorzie dat dat weleens een pijnpunt kan zijn.

[Clock]

Haan schreef op woensdag 17 maart 2010 @ 11:59:
Niet om je meteen te ontmoedigen, maar is performance een factor die van belang is? Want ik voorzie dat dat weleens een pijnpunt kan zijn.

In het vorige topic was dat een van de punten waarop ik de keuze hebt gemaakt tussen een ingewikkeld algoritme en het makkelijk brute-forcen. Performance is niet echt een issue, en na een eigen test blijkt dat 5 miljoen iteraties in 20 seconden gedaan worden. Voor de toepassing is dat geen probleem.

Helaas blijkt nu dat het 'makkelijk' brute-forcen niet zo makkelijk is als ik dacht

[NMe]

Dubbel loopje met alle "objecten" in de buitenste en alle "personen" in de binnenste loop, waarbij je van tevoren de personen op willekeurige volgorde sorteert?

[Clock]

NMe schreef op woensdag 17 maart 2010 @ 12:28:
Dubbel loopje met alle "objecten" in de buitenste en alle "personen" in de binnenste loop, waarbij je van tevoren de personen op willekeurige volgorde sorteert?

Correct me if i'm wrong, maar op die manier krijg je toch niet alle mogelijke verdelingen? Met 10 objecten en 10 personen loopt ie maar 100 keer door de loop heen, terwijl er een factor xxx meer verdelingen te maken zijn.

Ik heb het geprobeerd met 8 geneste loops, dan krijg ik wel miljoenen planningen maar wordt er geen rekening gehouden met de mogelijkheid van meerdere personen per object en dat een persoon maar op 1 object tegelijk kan worden ingedeeld.

[NMe]

Clock schreef op woensdag 17 maart 2010 @ 13:25:
[...]

Correct me if i'm wrong, maar op die manier krijg je toch niet alle mogelijke verdelingen? Met 10 objecten en 10 personen loopt ie maar 100 keer door de loop heen, terwijl er een factor xxx meer verdelingen te maken zijn.

Ah, verkeerd gelezen inderdaad, sorry.

[Haan]

Wat in dit soort gevallen, zeker als je toch gaat bruteforcen, goed kan helpen, is voor een beperkte set (bijv. 5 objecten) gewoon uitschrijven hoe je het met de hand zou oplossen. Daarna die oplossing overzetten in code.

[Hydra]

Ik zou punten toewijzen (1e voorkeur 100, 2e voorkeur 66, 3e voorkeur 33 punten bijvoorbeeld) aan personen die ingedeeld zijn in het object van hun voorkeur. Op die manier kun je alle combinaties afwerken en die met de 'hoogste' score als oplossing gebruiken. Dit heeft als voordeel dat als je een oplossing aan het genereren bent die sowieso niet meer hoger kan scoren dan je hoogste je op kan houden die te bekijken.

Voorbeeld:

Persoon: Voorkeur 1: Voorkeur 2: Voorkeur 3:
A O1 O2 O3
B O2 O3 O1
C O1 O3 O2

Oplossing 1:
Persoon A > Object 1 (100p)
Persoon B > Object 2 (100p)
Persoon C > Object 3 (66p)
Totaal: 266p

Oplossing 2:
Persoon A: > Object 2 (66p)
Persoon B: > Object 3 (66p)
Persoon C: > Object 1 (100p)
Totaal: 232p

Oplossing 1 is 'beter' kwa punten. Op die manier zoek je je hele 'boom' af.

[RikTW]

Zijn alle personen in iedere iteratie toegewezen aan 1 object?
(m.a.w. is het totaal aantal "persoon slots" van alle objecten gelijk aan het totaal aantal personen?)

Als dit het geval is is de oplossing alle mogelijke permutaties van personen over de "persoon slots"

[ Voor 23% gewijzigd door RikTW op 17-03-2010 13:52 ]

[djluc]

Werkt zoiets niet:

PHP:

<pre>
<?PHP

$people=array(
    'a' => array(
        1,
        4,
        5,
    ),
    'b' => array(
        1,
        5,
        6,
    ),
    'c' => array(
        1,
        6,
        7,
    ),
);

$objects=array();
$l=10;
for($i=1; $i<$l; $i++) {
    $objects[$i]=rand(0,3)+1;
}

print_R($people);

print_R($objects);

$assigned = array();

foreach($people AS $person => $preferences) {
    foreach($preferences AS $order => $preference) {
        foreach($objects AS $objectName => $limit) {
            if($objectName==$preference) {
                if(empty($assigned[$objectName]) OR count($assigned[$objectName])<$limit) {
                    $assigned[$objectName][]=$person;
                    break 2;
                }
            }
        }
    }
}

print_R($assigned);





?>

Mogelijke uitvoer:

code:

Array
(
    [a] => Array
        (
            [0] => 1
            [1] => 4
            [2] => 5
        )

    [b] => Array
        (
            [0] => 1
            [1] => 5
            [2] => 6
        )

    [c] => Array
        (
            [0] => 1
            [1] => 6
            [2] => 7
        )

)
Array
(
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 1
    [5] => 2
    [6] => 4
    [7] => 3
    [8] => 3
    [9] => 3
)
Array
(
    [1] => Array
        (
            [0] => a
        )

    [5] => Array
        (
            [0] => b
        )

    [6] => Array
        (
            [0] => c
        )

)

[Arie-]

Is dit niet gewoon probleem welke te formuleren en op te lossen is met de "Simplex Methode", of snap ik het probleem niet?

[Clock]

Hydra schreef op woensdag 17 maart 2010 @ 13:34:
Ik zou punten toewijzen (1e voorkeur 100, 2e voorkeur 66, 3e voorkeur 33 punten bijvoorbeeld) aan personen die ingedeeld zijn in het object van hun voorkeur. Op die manier kun je alle combinaties afwerken en die met de 'hoogste' score als oplossing gebruiken. Dit heeft als voordeel dat als je een oplossing aan het genereren bent die sowieso niet meer hoger kan scoren dan je hoogste je op kan houden die te bekijken.

Voorbeeld:

Persoon: Voorkeur 1: Voorkeur 2: Voorkeur 3:
A O1 O2 O3
B O2 O3 O1
C O1 O3 O2

Oplossing 1:
Persoon A > Object 1 (100p)
Persoon B > Object 2 (100p)
Persoon C > Object 3 (66p)
Totaal: 266p

Oplossing 2:
Persoon A: > Object 2 (66p)
Persoon B: > Object 3 (66p)
Persoon C: > Object 1 (100p)
Totaal: 232p

Oplossing 1 is 'beter' kwa punten. Op die manier zoek je je hele 'boom' af.

De hele punten methode had ik al uitgewerkt, en dat is het probleem niet. Ik heb een code opzet nodig die alle mogelijke verdelingen bijlangs gaat zodat ik die puntenaanatallen kan berekenen.

RikTW schreef op woensdag 17 maart 2010 @ 13:47:
Zijn alle personen in iedere iteratie toegewezen aan 1 object?
(m.a.w. is het totaal aantal "persoon slots" van alle objecten gelijk aan het totaal aantal personen?)

Als dit het geval is is de oplossing alle mogelijke permutaties van personen over de "persoon slots"

In de situatie hoeft het aantal slots en personen niet aan elkaar gelijk te zijn, maar als dat het een en ander makkelijker maakt stellen we gewoon dat dat zo moet zijn

Ik wil dus een code opzet die alle verdelingen bijlangs gaat. Het toekennen van een score aan elke planning en al die dingen zijn geen probleem.

[ Voor 3% gewijzigd door Clock op 17-03-2010 14:04 ]

[Clock]

djluc schreef op woensdag 17 maart 2010 @ 13:49:
Werkt zoiets niet:
.............

Dat is een mooie oplossing voor het verdeelprobleem. Echter moeten mensen zich soms 'opofferen' zodat 1 of meerdere personen ook hun voorkeursobject kunnen krijgen. Dus een persoon moet soms, ondanks het beschikbaar zijn van hun 1e keus, toch zijn 2e of 3e keus krijgen, zodat iemand anders ook een object van zijn voorkeur kan krijgen.

Uit het vorige topic kwam ook naar voren dat de makkelijkste oplossing het brute-forcen is, waarmee je bij elke verdeling een score berekend. De verdeling met de hoogste score wint. Op die manier pak je de verdeling waarmee het systeem als geheel zo tevreden mogelijk is.

Het probleem waar ik nu mee zit is het doorlopen van alle mogelijke verdelingen. Hoe kan ik de code opzetten zodat alle mogelijke planningen (met x slots en y personen) afloopt, waarin ik dan mijn 'scoreberekeningen' kan doen?

[ Voor 13% gewijzigd door Clock op 17-03-2010 14:18 ]

[slow whoop]

Volgens mij zijn er een beetje veel mogelijkheden. Stel je een gesimplificeerde versie voor waarbij elk project maar 1 persoon kan hebben (in plaats van 3). Dan kan
persoon 1 kiezen uit 10 projecten
persoon 2 kiezen uit 9 projecten
persoon 3 kiezen uit 8 projecten
persoon 4 kiezen uit 7 projecten
persoon 5 kiezen uit 6 projecten
persoon 6 kiezen uit 5 projecten
persoon 7 kiezen uit 4 projecten
persoon 8 kiezen uit 3 projecten
persoon 9 kiezen uit 2 projecten
persoon 10 kiezen uit 1 project
Dit zijn al 10! = 3268800 mogelijkheden voor 10 personen. Deze 10 personen kies je uit een poel van 50. Dat kan op 50!/(10!*40!) = 10272278170 manieren. Totaal zit je dan op 3268800*10272278170 = 3.73*10^16 mogelijkheden.

Als jouw computer 5 miljoen iteraties is 20 seconden kan doen, dan is ie dus na:
20*3.73*10^16/5000000 = 1.49*10^11 seconden klaar. Dat is ongeveer 4728 jaar.

Dit is dus voor het simpele geval van 1 persoon per project. Voor 3 personen per project zijn er nog meer mogelijkheden.

Of doe ik iets verkeerd?

[RikTW]

Als het aantal personen ongeveer gelijk is aan het aantal slots dan is het alweer een stuk minder, maar ik denk dat je evengoed gelijk hebt dat het snel uit de klauwen kan lopen.

[Clock]

slow whoop schreef op woensdag 17 maart 2010 @ 14:27:
Volgens mij zijn er een beetje veel mogelijkheden. Stel je een gesimplificeerde versie voor waarbij elk project maar 1 persoon kan hebben (in plaats van 3). Dan kan
persoon 1 kiezen uit 10 projecten
persoon 2 kiezen uit 9 projecten
persoon 3 kiezen uit 8 projecten
persoon 4 kiezen uit 7 projecten
persoon 5 kiezen uit 6 projecten
persoon 6 kiezen uit 5 projecten
persoon 7 kiezen uit 4 projecten
persoon 8 kiezen uit 3 projecten
persoon 9 kiezen uit 2 projecten
persoon 10 kiezen uit 1 project
Dit zijn al 10! = 3268800 mogelijkheden voor 10 personen. Deze 10 personen kies je uit een poel van 50. Dat kan op 50!/(10!*40!) = 10272278170 manieren. Totaal zit je dan op 3268800*10272278170 = 3.73*10^16 mogelijkheden.

Als jouw computer 5 miljoen iteraties is 20 seconden kan doen, dan is ie dus na:
20*3.73*10^16/5000000 = 1.49*10^11 seconden klaar. Dat is ongeveer 4728 jaar.

Dit is dus voor het simpele geval van 1 persoon per project. Voor 3 personen per project zijn er nog meer mogelijkheden.

Of doe ik iets verkeerd?

De enige 'fout' is dat je ervanuit gaat die die 10 personen random uit een pool van 50 getrokken worden.
Deze 10 personen worden door mij uit die 50 personen gekozen (die staan ingepland voor die dag).

Er zijn dus 8 objecten (vast) met elk tussen de 0 en 3 slots voor personen. Er zijn tussen de 10 en 15 personen die elk een voorkeur hebben voor 3 objecten (1e, 2e en 3e). Het aantal slots hoeft in de praktijk niet overeen te komen met het aantal personen, maar als dat nodig is voor de oplossing is dat een mogelijkheid.

Ik wil met een stuk code alle mogelijke verdelingen maken van het aantal personen over de objecten/slots. Ik verzin vervolgens zelf code om te kijken welke van die miljoenen verdelingen het beste is.

[slow whoop]

Clock schreef op woensdag 17 maart 2010 @ 14:44:
[...]


De enige 'fout' is dat je ervanuit gaat die die 10 personen random uit een pool van 50 getrokken worden.
Deze 10 personen worden door mij uit die 50 personen gekozen (die staan ingepland voor die dag).

Er zijn dus 8 objecten (vast) met elk tussen de 0 en 3 slots voor personen. Er zijn tussen de 10 en 15 personen die elk een voorkeur hebben voor 3 objecten (1e, 2e en 3e). Het aantal slots hoeft in de praktijk niet overeen te komen met het aantal personen, maar als dat nodig is voor de oplossing is dat een mogelijkheid.

Ik wil met een stuk code alle mogelijke verdelingen maken van het aantal personen over de objecten/slots. Ik verzin vervolgens zelf code om te kijken welke van die miljoenen verdelingen het beste is.

OK. Ik snap het. Toch lijkt het me zinnig om na te gaan hoeveel mogelijke combinaties er nu echt zijn. Als je dat weet, en dus weet hoe je het moet uitrekenen, wordt het denk ik eenvoudiger om uit te vissen hoe je code er uit moet zien.

[Clock]

slow whoop schreef op woensdag 17 maart 2010 @ 14:48:
[...]


OK. Ik snap het. Toch lijkt het me zinnig om na te gaan hoeveel mogelijke combinaties er nu echt zijn. Als je dat weet, en dus weet hoe je het moet uitrekenen, wordt het denk ik eenvoudiger om uit te vissen hoe je code er uit moet zien.

Ik ga er eens mijn hoofd over breken. Ondertussen heb ik een heel klein simpel voorbeeld uitgewerkt om mijn bedoeling te illustreren. In dit geval hebben alle paden 1 slot en zijn er maar 3 personen.


Ik wil met een loop door alle combo's heenlopen met x slots en y personen.

[slow whoop]

Clock schreef op woensdag 17 maart 2010 @ 15:01:
[...]


Ik ga er eens mijn hoofd over breken. Ondertussen heb ik een heel klein simpel voorbeeld uitgewerkt om mijn bedoeling te illustreren. In dit geval hebben alle paden 1 slot en zijn er maar 3 personen.

[afbeelding]
Ik wil met een loop door alle combo's heenlopen met x slots en y personen.

In je voorbeeld heb je inderdaad 3*2*1 = 6 verdelingen. Maar als er 3 personen per object mogen worden het 3*3*3 = 27 verdelingen. En dit is natuurlijk het simpelste geval.

[Blade-Groentje]

Is recursie niet een idee?
Met onderstaand 'voorbeeld' worden alle personen altijd ingedeeld, maar objecten kunnen leeg blijven.

C:

toekennen_persoon_aan_object(lijstje_personen, lijstje_objecten, huidige_verdeling)
{
  if (lijstje_personen is leeg)
  {
    doe_geniale_actie(huidige_verdeling);
  }
  foreach (persoon in lijstje_personen)
  {
    foreach (object in lijstje_objecten)
    {
       nieuw_lijstje_personen = lijstje_personen minus persoon;
       nieuwe_verdeling = huidige_verdeling plus (object, persoon);

       toekennen_persoon_aan_object(nieuw_lijstje_personen, lijstje_objecten, nieuwe_verdeling)
    }
  }
}

[djluc]

Clock schreef op woensdag 17 maart 2010 @ 14:16:
[...]


Dat is een mooie oplossing voor het verdeelprobleem. Echter moeten mensen zich soms 'opofferen' zodat 1 of meerdere personen ook hun voorkeursobject kunnen krijgen. Dus een persoon moet soms, ondanks het beschikbaar zijn van hun 1e keus, toch zijn 2e of 3e keus krijgen, zodat iemand anders ook een object van zijn voorkeur kan krijgen.

Uit het vorige topic kwam ook naar voren dat de makkelijkste oplossing het brute-forcen is, waarmee je bij elke verdeling een score berekend. De verdeling met de hoogste score wint. Op die manier pak je de verdeling waarmee het systeem als geheel zo tevreden mogelijk is.

Het probleem waar ik nu mee zit is het doorlopen van alle mogelijke verdelingen. Hoe kan ik de code opzetten zodat alle mogelijke planningen (met x slots en y personen) afloopt, waarin ik dan mijn 'scoreberekeningen' kan doen?

http://dev.tentoday.com/test.php
http://dev.tentoday.com/test.phps

Even een testje, dit deelt iedereen in op zijn eerste keuze indien beschikbaar, anders op de 2de keuze en zo verder. Dan heb je een redelijk optimale oplossing aangezien iedereen zo hoog mogelijk geplaatst wordt. De lijst met personen zou ik gewoon random maken dan krijgt iedereen een keer de eerste kans.

[Clock]

djluc schreef op woensdag 17 maart 2010 @ 15:18:
[...]

http://dev.tentoday.com/test.php
http://dev.tentoday.com/test.phps

Even een testje, dit deelt iedereen in op zijn eerste keuze indien beschikbaar, anders op de 2de keuze en zo verder. Dan heb je een redelijk optimale oplossing aangezien iedereen zo hoog mogelijk geplaatst wordt. De lijst met personen zou ik gewoon random maken dan krijgt iedereen een keer de eerste kans.

Bedankt voor je opzet! Ik heb het even aangepast aan een iets meer realistische situatie om het te testen.
http://files.danhof.org/test.php
http://files.danhof.org/test.txt

Er zit 1 flaw in. Er zijn 9 personen en 9 slots. Echter worden maar 8 personen verdeeld (object 5 heeft 1 persoon ipv 2). Als er aan het eind een slot overblijft moet de laatste persoon daar hoe dan ook komen te staan, ondanks zijn voorkeur. Ik probeer het script nog te doorgronden, maar waar dat met simpele code geen probleem is, zit ik hier toch nog scheef naar te kijken.

Blade-Groentje schreef op woensdag 17 maart 2010 @ 15:07:
Is recursie niet een idee?
Met onderstaand 'voorbeeld' worden alle personen altijd ingedeeld, maar objecten kunnen leeg blijven.

C:

toekennen_persoon_aan_object(lijstje_personen, lijstje_objecten, huidige_verdeling)
{
  if (lijstje_personen is leeg)
  {
    doe_geniale_actie(huidige_verdeling);
  }
  foreach (persoon in lijstje_personen)
  {
    foreach (object in lijstje_objecten)
    {
       nieuw_lijstje_personen = lijstje_personen minus persoon;
       nieuwe_verdeling = huidige_verdeling plus (object, persoon);

       toekennen_persoon_aan_object(nieuw_lijstje_personen, lijstje_objecten, nieuwe_verdeling)
    }
  }
}

Bedankt voor je code: eerlijk gezegd snap ik de code niet. Ik ga even het een en ander opzoeken over recursie en of VBA dat een beetje ondersteund.

Bijna alle tot nu toe aangedragen oplossingen (waarvoor ik dankbaar ben) gaan uit van een andere indeelmethode dan brute-forcen. Niet dat ik daar niet open voor sta, echter heb ik het 'scoren' van die planningen al helemaal uitgewerkt met code ed. En aangezien het niet uitmaakt dat het 2 min duurt om alles te berekenen, lijkt me BF ook de beste oplossing geven. Is het onmogelijk om alle mogelijkheden met relatief simpele code af te lopen?

[ Voor 10% gewijzigd door Clock op 17-03-2010 15:57 ]

[Blade-Groentje]

Misschien dat een beetje extra uitleg helpt (het is niet mijn sterkste punt

Het idee is dat je een functie hebt die 3 parameters meekrijgt: een array van personen, een array van objecten en bv een array van object, persoon combinaties.

Bij de eerste aanroep is de 3e parameter een lege array. Wat de functie doet is bij elke stap alle combinaties van personen en objecten in een resultaat opslaan (de 3e parameter). Om naar de volgende stap te gaan wordt dan het lijstje van personen zonder degene die we net gehad hebben en de resultaat array inclusief onze nieuwe combinatie meegegeven aan dezelfde functie.
Dit gaat net zolang door tot er geen personen meer over zijn en dan gebeurt er iets met het eindresultaat. Dit 'iets' wordt dus voor elke mogelijke combinatie uitgevoerd. Als je het print krijg je alle mogelijkheden te zien, maar waarschijnlijk wil jij dan een functie aanroepen die er een score aan geeft.

[djluc]

Clock schreef op woensdag 17 maart 2010 @ 15:51:
[...]


Bedankt voor je opzet! Ik heb het even aangepast aan een iets meer realistische situatie om het te testen.
http://files.danhof.org/test.php
http://files.danhof.org/test.txt

Er zit 1 flaw in. Er zijn 9 personen en 9 slots. Echter worden maar 8 personen verdeeld (object 5 heeft 1 persoon ipv 2). Als er aan het eind een slot overblijft moet de laatste persoon daar hoe dan ook komen te staan, ondanks zijn voorkeur. Ik probeer het script nog te doorgronden, maar waar dat met simpele code geen probleem is, zit ik hier toch nog scheef naar te kijken.

http://dev.tentoday.com/test.php
http://dev.tentoday.com/test.phps

Heb dat er even voor je uit gehaald als test. Tevens even de code van commentaar voorzien. Door .phps krijg je trouwens een beetje kleurtjes te zien om het leesbaarder te maken. Dat heb je met .txt niet. Nu vult het compleet uit. De strategie is in dit geval zoveel mogelijk mensen hun eerste keuze geven. Je kan uiteraard ook voor een andere strategie kiezen, wat je vooral bij spelletjes e.d. vaak ziet dat je in elk geval iedereen een keuze uit zijn voorkeuren geeft. Dat hangt dus af van je wensen.

Bijna alle tot nu toe aangedragen oplossingen (waarvoor ik dankbaar ben) gaan uit van een andere indeelmethode dan brute-forcen. Niet dat ik daar niet open voor sta, echter heb ik het 'scoren' van die planningen al helemaal uitgewerkt met code ed. En aangezien het niet uitmaakt dat het 2 min duurt om alles te berekenen, lijkt me BF ook de beste oplossing geven. Is het onmogelijk om alle mogelijkheden met relatief simpele code af te lopen?

Wat ik als voorbeeld toon is gewoon brute force, zit echt totaal geen slimheid achter hoor Veel simpeler dan dit gaat het niet:

PHP:

foreach($objects AS $objectName => $limit) {
    //starting with prio 1 to the latest prio
    for($i=0; $i<$preferencesLength; $i++) {
        //loop all people, checking from the current prio
        foreach($people AS $person => $preferences) {
            //check whether this user has a preference for this object
            if($objectName==$preferences[$i]) {
                //he wants this object so check whether it is available
                if(empty($assigned[$objectName]) OR count($assigned[$objectName])<$limit-1 ) {
                    $assigned[$objectName][]=$person;
                    unset($people[$person]);
                    break;
                }
            }
        }
    }
}

//assigned any left people to open slots
foreach($objects AS $objectName => $limit) {
    //checking whether the limit of the object has not been reached
    if($limit>0 AND count($assigned[$objectName])<$limit) {
        //assign the people left to any open slot
        $toFill=$limit-count($assigned[$objectName]);
        foreach($people AS $name => $preferences) {
            $assigned[$objectName][]=$name;
            
            //check to see whether this slot has been filled
            $toFill--;
            if($toFill==0) {
                break;
            }
        }
    }
}

Je zou die 2 eventueel nog kunnen combineren maar dit is vrij recht toe recht aan. Het is slecht het doorlopen van alle objecten en mensen.

[ Voor 42% gewijzigd door djluc op 17-03-2010 20:19 ]

[Clock]

Blade-Groentje schreef op woensdag 17 maart 2010 @ 16:26:
Misschien dat een beetje extra uitleg helpt (het is niet mijn sterkste punt

Het idee is dat je een functie hebt die 3 parameters meekrijgt: een array van personen, een array van objecten en bv een array van object, persoon combinaties.

Bij de eerste aanroep is de 3e parameter een lege array. Wat de functie doet is bij elke stap alle combinaties van personen en objecten in een resultaat opslaan (de 3e parameter). Om naar de volgende stap te gaan wordt dan het lijstje van personen zonder degene die we net gehad hebben en de resultaat array inclusief onze nieuwe combinatie meegegeven aan dezelfde functie.
Dit gaat net zolang door tot er geen personen meer over zijn en dan gebeurt er iets met het eindresultaat. Dit 'iets' wordt dus voor elke mogelijke combinatie uitgevoerd. Als je het print krijg je alle mogelijkheden te zien, maar waarschijnlijk wil jij dan een functie aanroepen die er een score aan geeft.

Bedankt voor je uitleg! Ik heb me even wat ingelezen in recursie, en heb de code nog even goed bekeken. Ik snap nu hoe het in elkaar zit. Ik heb geprobeerd het te implementeren in VBA, echter loop ik dan tegen de beperkingen van die taal aan. Zo is het meegeven van een array aan een functie beperkt in functionaliteit, en ontbreekt het returnen van een array helemaal. Ook is het aantal 'recursie-iteraties' beperkt. Een lastige opgave dus, welke door de beperkingen van de taal niet te implementeren valt. Het heeft me wel een inkijk gegeven in recursie functies ed, dus thnx

@DJluc.
Bedankt voor alle moeite die je in de code hebt gestoken. De code klopt nu helemaal, en ik ben nu bezig het te implementeren in VBA. Op deze manier kan ik een nette verdeling op een veel snellere manier maken

Echter ben ik nog naar 1 ding nieuwsgierig. Is het mogelijk om met soortgelijke simpele code door alle mogelijke verdelingen te lopen zonder dat er bij de toewijzing van een persoon aan een object rekening gehouden wordt met een voorkeur? Gewoon alle xx miljoenen verdelingen doorlopen (wat Blade-Groentje met een recursieve functie deed). Ik ben erg benieuwd naar de verschillen in uitkomst tussen beide bereken-manieren.

[djluc]

Wat zou dan het optimaal zijn volgens je idee? Dan ga je toch gewoon van bovenaf vullen? Dus de objecten van voor tot achter vol zetten met mensen?

[pedorus]

Clock schreef op woensdag 17 maart 2010 @ 23:44:
Ik heb geprobeerd het te implementeren in VBA, echter loop ik dan tegen de beperkingen van die taal aan. Zo is het meegeven van een array aan een functie beperkt in functionaliteit, en ontbreekt het returnen van een array helemaal. Ook is het aantal 'recursie-iteraties' beperkt.

Waar heb je het over?

Visual Basic:

Public Function test() As Variant()
    ReDim test(10)
End Function

Public Function maxRecursion(i As Integer)
    maxRecursion = maxRecursion(i + 1) 'out of stack space after 5000+ calls
End Function

Daarnaast vermoed ik dat je recursie niet eens nodig hebt; het gaat hier simpelweg om het afgaan van alle mogelijkheden, dat kan ook gewoon iteratief. (Bijvoorbeeld door ze allemaal te ontwikkelen in een array, zoals hier.)

[Clock]

djluc schreef op woensdag 17 maart 2010 @ 23:55:
Wat zou dan het optimaal zijn volgens je idee? Dan ga je toch gewoon van bovenaf vullen? Dus de objecten van voor tot achter vol zetten met mensen?

Als je alle mogelijke planning maakt, van a tot z, z tot a en alles ertussen in (miljoenen ja, ik weet het), en per planning een score berekend kan je daar een (of meerdere) beste uit kiezen.

Per planning krijgt een persoon bijv 5 punten als hij ingedeeld is op zijn 1e voorkeur object, 3 punten indien hij op zijn 2e voorkeur staat en 1 punt voor de 3e voorkeur. Er kunnen zelfs punten worden afgetrokken als een persoon op een object staat ingedeeld die niet op zijn voorkeurenlijst staat. De grootte van de puntenaantallen is een kwestie van testen en uitproberen.

Als de punten van alle personen bij elkaar opgeteld worden krijg je een totaalscore. Deze is voor (bijna) alle planningen anders. Indien de score van de huidige iteratie/verdeling hoger is dan de hoogste tot dan toe wordt de nieuwe topscore+verdeling opgeslagen. Aan het eind van de xx miljoen iteraties/verdelingen blijft er een planning over met de hoogste totaalscore.

Op die manier volgt (denk ik) een net iets nauwkeurigere verdeling op, omdat rekening gehouden wordt met de opofferingen. (iemand die genoegen moet nemen met zijn 3e voorkeur zodat 2 anderen een voorkeursobject kunnen krijgen ipv een on-voorkeurs object.)

Om deze manier te implementeren heb ik code nodig die alle mogelijke verdelingen maakt voor 8 objecten met x slots per object en y personen. Per verdeling bereken ik dat die score. Die score berekenen is no problemo, echter alle mogelijke verdelingen doorlopen wel.

Dit is niks ten nadele van de code die je gemaakt hebt, alleen nieuwsgierigheid.

[Clock]

pedorus schreef op donderdag 18 maart 2010 @ 00:27:
[...]

Waar heb je het over?

Visual Basic:

Public Function test() As Variant()
    ReDim test(10)
End Function

Public Function maxRecursion(i As Integer)
    maxRecursion = maxRecursion(i + 1) 'out of stack space after 5000+ calls
End Function

Daarnaast vermoed ik dat je recursie niet eens nodig hebt; het gaat hier simpelweg om het afgaan van alle mogelijkheden, dat kan ook gewoon iteratief. (Bijvoorbeeld door ze allemaal te ontwikkelen in een array, zoals hier.)

"At approximately 6800 stack entries, the stack is filled to capacity and VBA terminates everything with an Out Of Stack Space run time error. " In dit geval hoeft dat bij nader inzien idd geen probleem te zijn omdat er geen duizenden planningen gemaakt worden. Ik dacht dat er evenveel aanroepen als mogelijke planningen plaatsvonden.

"Note that returning an array as the result of a function or property was added in Office 2000 -- functions in Office 97 cannot return arrays." En laat ik nou net gedwongen zijn met office 97 te moeten werken door ultieme legacy.

[djluc]

Het lijkt me dat je dan zoiets als mogelijkheden krijgt in een simpel voorbeeld:

PHP:

$places=array(1,2,3);
$people=array('a', 'b', 'c');

/*

possible
1=a
2=b
3=c

1=b
2=a
3=c

1=c
2=a
3=b

1=b
2=c
3=a

1=c
2=b
3=a

*/

[Clock]

djluc schreef op donderdag 18 maart 2010 @ 01:12:
Het lijkt me dat je dan zoiets als mogelijkheden krijgt in een simpel voorbeeld:

PHP:

$places=array(1,2,3);
$people=array('a', 'b', 'c');

/*

possible
1=a
2=b
3=c

1=b
2=a
3=c

1=c
2=a
3=b

1=b
2=c
3=a

1=c
2=b
3=a

*/

Exact. Dit had ik in de vorige pagina in een plaatje samengevat:


Echter hoe genereer je die mogelijke verdelingen? (de pure random mogelijke verdelingen)

[ Voor 3% gewijzigd door Clock op 18-03-2010 01:22 ]

[djluc]

Een eerste idee met 1 object, dus nog geen complete verdeling maar alle mogelijkheden binnen een object:
http://dev.tentoday.com/tweakers/optimalone.php
http://dev.tentoday.com/tweakers/optimalone.phps

edit

Geeft alle mogelijke paden weer:
http://dev.tentoday.com/tweakers/optimal.php
http://dev.tentoday.com/tweakers/optimal.phps

Ik krijg niet voor elkaar om de paden compleet op te tellen of in elk geval per pad een totaalscore op te slaan. Hij "vergeet" het begin van het pad, hoe dat precies moet weet ik ook niet.

[ Voor 44% gewijzigd door djluc op 18-03-2010 04:39 ]

[Clock]

@DJluc
Met recursieve code is het idd lastig om een score te berekenen. Het zal ook niet mogelijk zijn alle mogelijkheden in een array te zetten, daar er dan zoveel geheugen gebruikt gaat worden dat de boel vastloopt (een array met enkele miljoenen subarray's). De score moet op dezelfde plek berekend worden als dat de semi-rondom verdeling gegenereerd wordt.

Ik heb een uurtje of wat zitten kloten in kladblok, en ik denk dat deze code het gewenste resultaat moet opleveren. Ik implementeer het morgen in VBA, en zal het dan testen.

Het is wel wat lastig leesbaar vermoed ik.

code:

'Gevulde variabelen
iNumSlots
iNumPersonen
aPersonenVoorkeur ('a'=>(1,2,3), 'b'=>(3,4,6),'c'=>(5,4,1), 'd'=>(3,2,5))
aSlotObjectAss (1=>1, 2=>2, 3=>3, 4=>4, 5=>4, 6=>5)

'Declareer vars
Dim iStopLoop as Integer
Dim iSlotTeller as Integer
Dim aPersonenTeller(iNumSlots) As Variant
Dim i As Integer
Dim iVerdelingScore As Integer
Dim iVerdelingTopscore As Integer
Dim iPuntenVoorkeur1 As Integer
Dim iPuntenVoorkeur2 As Integer
Dim iPuntenVoorkeur3 As Integer
Dim iPuntenAftrek As Integer

'Init vars
iStopLoop=0
iSlotTeller=1
i=0
For i = 0 To iNumSlots
  aPersonenTeller(i)=1
Next
iVerdelingScore=0
iVerdelingTopscore=0
iPuntenVoorkeur1=5
iPuntenVoorkeur2=3
iPuntenVoorkeur3=1
iPuntenAftrek=2

'loop semi oneindig (tot iStopLoop op 1 gezet wordt)
Do
  'Loop door elk slot (en genereer een complete verdeling)
  For iSlotTeller=1 to iNumSlots
    'Bereken score voor dit persoon op dit slot
    Select Case aSlotObjectAss(iSlotTeller)
      Case aPersonenVoorkeur(aPersonenTeller(iSlotTeller))(1)
        'Punten voor 1e voorkeur
        iVerdelingScore=iVerdelingScore+iPuntenVoorkeur1
      Case aPersonenVoorkeur(aPersonenTeller(iSlotTeller))(2)
        'Punten voor 2e voorkeur
        iVerdelingScore=iVerdelingScore+iPuntenVoorkeur2
      Case aPersonenVoorkeur(aPersonenTeller(iSlotTeller))(3)
        'Punten voor 3e voorkeur
        iVerdelingScore=iVerdelingScore+iPuntenVoorkeur3
      Case Else
        'Eventuele puntenaftrek
        iVerdelingScore=iVerdelingScore-iPuntenAftrek
    End Select

    'Als alle personen geweest zijn in dit slot:
    If (aPersonenTeller(iSlotTeller)=iNumPersonen) Then
      aPersonenTeller(iSlotTeller)=1
      aPersonenTeller(iSlotTeller-1)=aPersonenTeller(iSlotTeller-1)+1
    End If

    'Als we in het laatste slot zitten:
    If (iSlotTeller=iNumSlots) Then
      aPersonenTeller(iSlotTeller)=aPersonenTeller(iSlotTeller)+1
    End If
  Next iSlotTeller

  'Vergelijk verdelingscore met topscore
  If (iVerdelingScore > iVerdelingTopscore) Then
    'Nieuwe topscore
    iVerdelingTopscore=iVerdelingScore
    'Sla topverdeling op (VBA ondersteund geen array copy, dus moet ik nog iets voor verzinnen)
    '......
  End If
    
  Next

  'Als alle mogelijke planningen doorlopen zijn: breek uit de loop
  If (aPersonenTeller(1)=iNumPersonen) Then
    iStopLoop=1
  End If
Loop Until iStopLoop=1

Edit: Ik realiseer me net dat er 2 flaws in zitten: 1 grote en 1 kleine.
De grote flaw is dat hij nog geen rekening houdt met de contraint van 1 persoon per slot. Bij bijv de eerste verdeling die wordt gegenereerd staat persoon 1/a op alle objecten ingedeeld. Ik denk dat dat met wat extra code wel valt op te lossen. (bij de scoreberekening kijken of aPersonenTeller(iSlotTeller) niet reeds voorkomt in aPersonenTeller. Zo ja: aftrek van 100 punten zodat die verdeling nooit kan winnen (want ongeldige verdeling))
De kleine flaw is dat de code er van uitgaat dat heet aantal slots en personen gelijk zijn. Dat laat ik eerst even zo. Dan maak ik daar gewoon een harde eis van bij het invoeren van de parameters.

[ Voor 9% gewijzigd door Clock op 18-03-2010 14:53 ]

[Clock]

Ik heb het geïmplementeerd, en het werkt nog ook

code:

Sub BerekenPlanning_BF()
    Dim aPersonenVoorkeur() As Variant
    Dim aSlotObjectAss() As Variant
    Dim iNumSlots As Integer
    Dim iNumPersonen As Integer
    
    iNumPersonen = CInt(Worksheets("Rekensheet").Cells(24, "D").Value)
    iNumSlots = CInt(Worksheets("Rekensheet").Cells(46, "H").Value)
    aPersonenVoorkeur = LaadVullerData()
    aSlotObjectAss = LaadSlotData()

    'Declareer vars
    Dim iStopLoop As Integer
    Dim iSlotTeller As Integer
    Dim aPersonenTeller() As Variant
    ReDim aPersonenTeller(1 To iNumSlots) As Variant
    Dim aWinnendeVerdeling() As Variant
    ReDim aWinnendeVerdeling(1 To iNumSlots) As Variant
    Dim i As Integer
    Dim iVerdelingScore As Integer
    Dim iVerdelingTopscore As Integer
    Dim iPuntenVoorkeur1 As Integer
    Dim iPuntenVoorkeur2 As Integer
    Dim iPuntenVoorkeur3 As Integer
    Dim iPuntenAftrek As Integer
    Dim iPuntenAftrekDP As Integer
    Dim iIteratieTeller As Long
    Dim vTempVar() As Variant
    ReDim vTempVar(1 To iNumSlots) As Variant
    Dim bla As Boolean
    Dim teller As Long
    

    'Init vars
    iStopLoop = 0
    iSlotTeller = 1
    i = 1
    For i = 1 To iNumSlots
        aPersonenTeller(i) = 1
    Next
    iVerdelingScore = 0
    iVerdelingTopscore = 0
    iPuntenVoorkeur1 = 10
    iPuntenVoorkeur2 = 9
    iPuntenVoorkeur3 = 8
    iPuntenAftrek = 15
    iPuntenAftrekDP = 100
    iIteratieTeller = 0
    teller = 0
    
    'loop semi oneindig (tot iStopLoop op 1 gezet wordt)
    Do
        'Loop door elk slot (en genereer een complete verdeling)
        For iSlotTeller = 1 To iNumSlots
            'Als alle personen geweest zijn in dit slot:
            If (aPersonenTeller(iSlotTeller) = iNumPersonen) Then
                aPersonenTeller(iSlotTeller) = 1
                aPersonenTeller(iSlotTeller - 1) = aPersonenTeller(iSlotTeller - 1) + 1
            End If
    
            'Als we in het laatste slot zitten:
            If (iSlotTeller = iNumSlots) Then
                aPersonenTeller(iSlotTeller) = aPersonenTeller(iSlotTeller) + 1
            End If
            
            'Vul array met de verdeling tot dan toe om te checken op dubbele personen
            For i = 1 To iNumSlots
                If (i < iSlotTeller) Then
                    vTempVar(i) = aPersonenTeller(i)
                Else
                    vTempVar(i) = -1
                End If
            Next
        
            '--Bereken score voor dit persoon op dit slot
            'Kijk of persoon al eerder is ingedeeld
            If (UBound(Filter(vTempVar, aPersonenTeller(iSlotTeller))) >= 0) Then
                'persoon is eerder ingedeeld: geef strafpunten
                iVerdelingScore = iVerdelingScore - iPuntenAftrekDP
                teller = teller + 1
            Else
                'Persoon is niet eerder ingedeeld: bereken score
                Select Case aSlotObjectAss(iSlotTeller)
                    Case aPersonenVoorkeur(aPersonenTeller(iSlotTeller))(1)
                        'Punten voor 1e voorkeur
                        iVerdelingScore = iVerdelingScore + iPuntenVoorkeur1
                    Case aPersonenVoorkeur(aPersonenTeller(iSlotTeller))(2)
                        'Punten voor 2e voorkeur
                        iVerdelingScore = iVerdelingScore + iPuntenVoorkeur2
                    Case aPersonenVoorkeur(aPersonenTeller(iSlotTeller))(3)
                        'Punten voor 3e voorkeur
                        iVerdelingScore = iVerdelingScore + iPuntenVoorkeur3
                    Case Else
                        'Eventuele puntenaftrek
                        iVerdelingScore = iVerdelingScore - iPuntenAftrek
                End Select
            End If
        
        Next iSlotTeller
    
        
        'Vergelijk verdelingscore met topscore
        If ((iVerdelingScore + iPuntenAftrekDP) > iVerdelingTopscore) Then
            'Nieuwe topscore
            iVerdelingTopscore = (iVerdelingScore + iPuntenAftrekDP)
            'Sla topverdeling op
            i = 1
            For i = 1 To iNumSlots
                aWinnendeVerdeling(i) = aPersonenTeller(i)
            Next
        End If
        
        'Reset verdelingscore
        iVerdelingScore = 0
        iIteratieTeller = iIteratieTeller + 1
    
        'Als alle mogelijke planningen doorlopen zijn: breek uit de loop
        If (aPersonenTeller(1) = iNumPersonen) Then
            iStopLoop = 1
        End If
    Loop Until iStopLoop = 1
    
    'Schrijf winnende verdeling naar sheet
    i = 1
    For Each ding In aWinnendeVerdeling
        Worksheets("Rekensheet").Cells((i + 25), "J").Value = "Pad " + CStr(aSlotObjectAss(i))
        Worksheets("Rekensheet").Cells((i + 25), "K").Value = "Vuller " + CStr(ding)
        i = i + 1
    Next
    Worksheets("Rekensheet").Cells((26), "N").Value = CStr(iVerdelingTopscore)
End Sub

De code is nog niet erg netjes en geoptimaliseerd, maar het doet wat het moet doen. Het loopt alle mogelijke verdelingcombinaties af, en geeft elke verdeling een score. De verdeling met de hoogste score is de beste, en wordt de uiteindelijke verdeling. Het doorlopen duurt een aardige tijd (4 min voor 10 personen en 10 slots), maar dat is niet zo'n probleem. Er zijn dan ook meer dan 18 miljoen iteraties.

Ik moet nog spelen met de puntenaantallen voor 1e/2e/3e voorkeur en de aftrek van geen-voorkeur, want dat beinvloed de uitkomst van de planning. Daarvoor heb ik even wat real-life data nodig, zo dat ik de aantallen aan de hand van de gewenste uitkomst kan tweaken.

Verder zal ik in het weekend de resultaten eens naast de resultaten van de code van DJluc leggen. Ik ben benieuwd of, en zo ja, welke verschillen erin zitten. Bedankt voor alle hulp!

[TheWickedD]

Hoi Clock,

Ik heb het topic niet helemaal gelezen, maar in z'n algemeen kan de opzet zo zijn:

als je de volgende objecten en slots hebt:

object	#slots
O1	1
O2	2
O3	1
O4	3

Dan heb je 7 slots in totaal. Pas bij het berekenen van de score van een verdeling maakt het uit welk slot bij welk object hoort, daarvoor niet. dus je kunt gewoon een platte array met daarin 7 slots gebruiken (en dan ergens anders een arraytje bijhouden waarin te vinden is voor elk slot bij welk object het hoort.

Dan:
1) Als er meer personen (N) zijn dan slots bij objecten (M)
buitenste for-loop: loop over alle mogelijke trekkingen van M uit N (nchoosek - weet niet wat de juiste beduiding voor dit probleem is, met die binominale coefficienten, dit is de naam van de functie in matlab)
binnenste for-loop: voor elke trekking, loop over alle mogelijke permutaties van de getrokken set en bereken de score
2) Als er evenveel personen als slots zijn
laat de buitenste for-loop weg
3) Als er minder personen (N) zijn dan slots bij objecten (M)
buitenste for-loop: loop over alle mogelijke permutaties van de personen
binnenste for-loop: loop over alle mogelijke trekkingen van N uit M slots (nchoosek) en vul de getrokken slots met de permutatie van de buitenste loop, bereken de score

Volgens mij heb je dan alle mogelijkheden te pakken. Het is ook het meeste brute-force wat je kunt doen. dit is trouwens ook nog makkelijk aan te passen als bepaalde slot (of objecten) een hogere prioriteit zouden hebben dan andere, gewoon een extra weegfactor gebruiken per slot/object bij het berekenen van de score.

Er zijn op het internet vast wel goede algorimen voor het genereren van permutaties en nchoosek sets te vinden

[ Voor 0% gewijzigd door TheWickedD op 19-03-2010 05:00 . Reden: tabel even rechtgetrokken ]

[pedorus]

Clock schreef op vrijdag 19 maart 2010 @ 01:28:
De code is nog niet erg netjes en geoptimaliseerd, maar het doet wat het moet doen. Het loopt alle mogelijke verdelingcombinaties af, en geeft elke verdeling een score.

Nee. Combinaties met een 1 op het einde worden vergeten, en het algoritme stopt te vroeg (kun je trouwens Exit Do of GoTo voor gebruiken). Daarnaast worden combinaties onnodig geëvalueerd (bij dubbele personen). En soms worden dezelfde combinaties meerdere keren geëvalueerd. Dit gebeurd bij 2 slots die op dezelfde positie zittten: De combinatie 1-3 is dan hetzelfde als de combinatie 3-1, dus je kan bijvoorbeeld alleen de opeenvolgende combinaties evalueren. Ik zou combinaties die niks gaan opleveren gelijk uitsluiten (dmv continue of goto), in plaats van dat je ze een penalty geeft. Ik zou trouwens ook uitgaan van de personen (die een plek moeten krijgen), in plaats van van de slots (die een persoon moeten krijgen). Dan heb je nooit een persoon dubbel, en een plek dubbel mag soms wel; beschikbaarheid van plekken kun je bijhouden in een aparte array.

Overigens kan "For iSlotTeller = 1 To iNumSlots" beter van achter naar voren en korter doorgaan, zodat je niet steeds onnodig gaat testen of je eentje hoger mag. Daar kan dan ook gelijk de "Exit Do" komen.

offtopic:
En verder haat ik hungarian notation. Als je het in VB toch wil, dan heeft VB bijvoorbeeld $ voor strings, % voor integers, enz. Dat is zeg maar de hongaarse notatie die al in VB zat en werd afgedwongen. Hier is men niet voor niks veelal van afgestapt: het was korter, maar minder duidelijk.