[Rikken] Tafelindeling genereren

[dailyleaf]

Intro:
Tijdens het organiseren van een half-jaarlijkse kaartmarathon, waar we de hele dag rikken, mag ik me bezighouden met het technische gedeelte om snel alle mensen in te delen voor aanvang.
Nu doe ik dat nog door elke deelnemer een willekeurige plaats toe te wijzen per ronde.

Probleem:
Hoewel het merendeel zeer te spreken is over wat de applicatie tot nu toe doet, blijft er steeds dezelfde vraag terugkomen: "Hoe komt het dat ik meer dan eens bij persoon a aan tafel heb gezeten en niet één keer bij persoon b.
Daarom ben ik nu op zoek naar een manier om alle deelnemers in te delen voor een x aantal rondes zonder dat zij meer dan eens bij een ander aan tafel zitten.

Het idee is dat ik nu indelingen genereer, zodat ik die later kan invullen met personen.
Afgelopen keer waren we met 40 deelnemers en hebben we 10 rondes gespeeld. Dat schema zou er dus sowieso uit moeten kunnen rollen.

Pre-condities:
spelersAantal % 4 = 0. (Rikken speel je met zijn vieren )
spelersAantal > maxRonde * 3. (Per ronde 3 tafelgenoten)

Om een mogelijk schema te genereren ben ik aan slag gegaan met backtracking in c++.
Ik hoop dat onderstaande code duidelijk maakt wat het idee is.

Het probleem waar ik nu tegenaan loop is dat het idioot lang duurt als het aantal rondes oploopt of het spelersaantal afneemt.

Algemene vraag:
Wat doe ik verkeerd?

SEA-vragen:
- Zijn er andere algoritmen om dit probleem te tackelen?
- Is mijn implementatie misschien inefficiënt op sommige punten?

PRG-vraag:
- Kan ik door andere datatypen te gebruiken mijn code sneller maken? Zo ja, waar?

Alle overige opmerkingen zijn natuurlijk ook welkom.

C++:

struct speler{
    int nr;
    vector<int> tafelPerRonde;
};
int maxRonde = 2;
int spelersAantal = 32;
vector<speler> spelers(spelersAantal);
vector<vector<int>> spelersPerRonde(maxRonde);

bool deelIn(int speler, int ronde)
{
    if(speler == spelersAantal) // nieuwe ronde
        return deelIn(0,ronde+1);
    if(ronde == maxRonde) // alle rondes ingedeeld
        return true;
    for(int i = 0; i < spelersAantal; i++) // alle stoelen proberen
    {
        if(spelersPerRonde[ronde][i] == -1) // stoel onbezet
        {
            bool veilig = true;
            for(int j = 0; j < 4; j++) // vergelijken met overige tafelgenoten
            {
                if(j != i%4 && spelersPerRonde[ronde][(i-(i%4))+j] != -1) // niet eigen stoel en geen lege stoel
                {
                    for(int k = 0; k < ronde; k++) // alle voorgaan ronden bekijken
                    {
                        if(spelers[speler].tafelPerRonde[k] == spelers[spelersPerRonde[ronde][(i-(i%4))+j]].tafelPerRonde[k]) // als je al aan tafel hebt gezeten
                            veilig =false;
                    }
                }
            }
            if(veilig)
            {
                spelersPerRonde[ronde][i] = speler; // speler plaatsen
                spelers[speler].tafelPerRonde[ronde] = (int)i/4;
                if(deelIn(speler+1, ronde)) // volgende speler
                    return true;
                else
                {
                    spelersPerRonde[ronde][i] = -1; // stoel leegmaken
                    spelers[speler].tafelPerRonde[ronde] = -1; // van tafel schoppen 
                }
            }

        }
    }
    return false;
}

int main()
{
...
Initialisatie op -1
...
    if(deelIn(0,0))
        cout << "Gelukt" << endl;
}

Voor degenen die niet weten wat Rikken is.

[Anoniem: 221080]

Een ander simpel algoritme om dit op te lossen:

Stel je hebt n spelers en m rondes.
Maak voor elke speler een lijst van alle andere spelers behalve zichzelf. Dit zijn de spelers waar deze speler nog niet tegen gespeeld heeft.

Per rond:
Kies een speler A en kies daarbij 3 andere spelers (B, C, D) uit de lijst van deze speler A.
Verwijder de spelers B, C, D uit de lijst van A
Verwijder de spelers A, C, D uit de lijst van B
Verwijder de spelers A, B, D uit de lijst van C
Verwijder de spelers A, B, C uit de lijst van D
Doe dit n/4 keer (aantal tafels) waarbij je natuurlijk steedts spelers kiest die nog niet aan andere tafels zitten.

Dit komt altijd mooi uit want per ronde worden er uit elke lijst precies 3 spelers verwijderd. Dus er moeten 3*m aantal spelers in elke lijst zitten en dit klopt precies (omdat n > m*3 zoals jij al zei).

Ik hoop dat de uitleg duidelijk genoeg is.

[dailyleaf]

Anoniem: 221080 schreef op woensdag 24 juni 2009 @ 20:28:
Een ander simpel algoritme om dit op te lossen:

Stel je hebt n spelers en m rondes.
Maak voor elke speler een lijst van alle andere spelers behalve zichzelf. Dit zijn de spelers waar deze speler nog niet tegen gespeeld heeft.

Per rond:
Kies een speler A en kies daarbij 3 andere spelers (B, C, D) uit de lijst van deze speler A.
Verwijder de spelers B, C, D uit de lijst van A
Verwijder de spelers A, C, D uit de lijst van B
Verwijder de spelers A, B, D uit de lijst van C
Verwijder de spelers A, B, C uit de lijst van D
Doe dit n/4 keer (aantal tafels) waarbij je natuurlijk steedts spelers kiest die nog niet aan andere tafels zitten.

Dit komt altijd mooi uit want per ronde worden er uit elke lijst precies 3 spelers verwijderd. Dus er moeten 3*m aantal spelers in elke lijst zitten en dit klopt precies (omdat n > m*3 zoals jij al zei).

Ik hoop dat de uitleg duidelijk genoeg is.

Volgens mij zit ik dan nog steeds met hetzelfde probleem.

De eerste speler aan een lege tafel is geen probleem, drie spelers uitzoeken uit het lijstje is ook nog geen probleem.
Maar persoon B, C en D mogen natuurlijk ook nog niet bij elkaar hebben gezeten.

En dan ben ik weer terug bij af.

[Soultaker]

dailyleaf schreef op woensdag 24 juni 2009 @ 17:09:
Het idee is dat ik nu indelingen genereer, zodat ik die later kan invullen met personen.
Afgelopen keer waren we met 40 deelnemers en hebben we 10 rondes gespeeld. Dat schema zou er dus sowieso uit moeten kunnen rollen.

Is het wel waar dit altijd kan? Als je er van uitgaat dat je met N spelers N/4 rondes zou kunnen spelen, hoe werkt dat dan voor vier spelers in twee rondes? (Dat is zeker onmogelijk.) Of met zestien spelers in vier rondes? (Daarbij kom ik niet verder dan drie rondes.)

En dat is nog zwakker dan jouw aanname dat je met N spelers (N-1)/3 rondes zou moeten kunnen spelen!

Ik ben er niet helemaal uit hoe het werkt, maar ik vermoed dat er een limiet is aan het aantal rondes dat je kunt spelen zonder mensen dubbel te matchen, en dat die limiet onder de gewenste (N-1)/3 zit. Dat zou dan betekenen dat ófwel niet iedereen met iedereen aan tafel zit, óf dat je bepaalde mensen dubbel tegenkomt, of (zoals in jouw geval dus ook voorkwam) een combinatie van beide.

[dailyleaf]

Soultaker schreef op woensdag 24 juni 2009 @ 22:05:
Is het wel waar dit altijd kan? Als je er van uitgaat dat je met N spelers N/4 rondes zou kunnen spelen, hoe werkt dat dan voor vier spelers in twee rondes? (Dat is zeker onmogelijk.)

Meer rondes dan (aantalSpeler-1)/3 zou met een kleine uitbreiding ook mogelijk moeten zijn. Tot aan (aantalSpeler-1)/3 maximaal 1 keer, daarna lijst weer vullen met alle spelers en verder gaan.

Of met zestien spelers in vier rondes? (Daarbij kom ik niet verder dan drie rondes.)

Met het algoritme wat ik nu gebruik kan ie zelfs 5 ronden uitrekenen voor 16 spelers.
6 ronden zou false op moeten leveren, maar daar komt ie niet aan toe omdat ie alles gaat proberen. Dat stijgt explosief.

Ik ben er niet helemaal uit hoe het werkt, maar ik vermoed dat er een limiet is aan het aantal rondes dat je kunt spelen zonder mensen dubbel te matchen, en dat die limiet onder de gewenste (N-1)/3 zit. Dat zou dan betekenen dat ófwel niet iedereen met iedereen aan tafel zit, óf dat je bepaalde mensen dubbel tegenkomt, of (zoals in jouw geval dus ook voorkwam) een combinatie van beide.

Dat gevoel heb ik dus zelf ook. Ik kan het alleen niet wiskundig onderbouwen, en dan blijft het knagen.

[Soultaker]

dailyleaf schreef op woensdag 24 juni 2009 @ 22:17:
Met het algoritme wat ik nu gebruik kan ie zelfs 5 ronden uitrekenen voor 16 spelers.
6 ronden zou false op moeten leveren, maar daar komt ie niet aan toe omdat ie alles gaat proberen. Dat stijgt explosief.

Post eens een indeling voor die vijf ronden dan? Ik kwam er handmatig niet zo 1-2-3 uit.

[dailyleaf]

Soultaker schreef op woensdag 24 juni 2009 @ 22:20:
[...]

Post eens een indeling voor die vijf ronden dan? Ik kwam er handmatig niet zo 1-2-3 uit.

Dit rolt er uit de debugger:

spelersPerRonde[5](
[16](0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15),
[16](0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15),
[16](0,5,10,15,1,4,11,14,2,7,8,13,3,6,9,12),
[16](0,6,11,13,1,7,10,12,2,4,9,15,3,5,8,14),
[16](0,7,9,14,1,6,8,15,2,5,11,12,3,4,10,13))

Maargoed, nog steeds op zoek naar een ander/beter algoritme dus.

[ Voor 6% gewijzigd door dailyleaf op 24-06-2009 22:26 ]

[Nick The Heazk]

Ik denk dat je hier te maken hebt met een herhaald clique probleem (of herhaald 4DM probleem) (en als je ook nog eens een maximaal aantal rondes wilt spelen, zonder conflicten gaat het er heus niet leuker op worden).

Beschouw de grafe waarbij er voor elke speler een knoop voorzien is. Een verbinding tussen twee knopen geeft aan dat een speler nog niet tegen een andere speler heeft gespeeld (in een ronde/tafel/we). Initieel zit je dus met een volledig verbonden grafe. Indien je nu tafels wilt vormen waarbij elk van de spelers nog nooit aan tafel heeft gezeten met elk van de andere spelers, dan kun je dit eenvoudig doen door een 4-clique te zoeken in je grafe. Van zodra je deze gevonden hebt verwijder je de betrokken bogen uit de grafe. Op deze manier kun je iteratief spelers aan tafels toewijzen. Voor praktische doeleinden moet je ook nog eens tijdelijk de knopen die de spelers voorstellen buiten beschouwing laten wanneer je de tafels voor een ronde opstelt (je wilt niet dat eenzelfde speler op meerdere tafels moet spelen in dezelfde ronde). Dit kun je praktisch doen door je knopen te kleuren. De aandachtige lezer merkt hier meteen ook op dat je met een exact set cover (4-sets in dit geval) als deelprobleem zit. Van zodra je geen 4-cliques meer kunt vinden in je grafe kun je zoeken naar kleinere cliques. Dan zul je wel steeds moeten aanvullen met andere spelers. Indien je dit hele proces maar lang genoeg doorzet zal je grafe geen bogen meer bevatten. Vanaf dan maak je er weer een volledig verbonden grafe van en ben je weer bij af.

Heel het bovenstaande is natuurlijk vanuit een theoretisch standpunt erg leuk. Normaliter kun je dit ook praktisch wel relatief eenvoudig implementeren, met behulp van grafen. Bovenstaande geeft eigenlijk ook al aan dat het vrij onwaarschijnlijk is dat je een snel algoritme gaat kunnen vinden voor jouw probleem (wat essentieel het fictieve exact cover by 4-cliques is ).

Als een extra heuristiek denk ik overigens dat je best begint met het zoeken naar 4-cliques tussen de knopen met het minste aantal verbindingen. Immers, als men tot het laatste zou wachten om deze in te delen, dan is de kans groot dat de weinig personen waarmee deze persoon verbonden is, reeds bij een tafel zijn ingedeeld. Om dat efficiënt te implementeren kijk je best eens naar meer geavanceerde datastructuren zoals bijvoorbeeld bionomial, fibonacci of radix heaps.

Door gebruik te maken van bovenstaande heuristiek en een hypothetische implementatie met Fibonacci heaps, kom ik op een tijdscomplexiteit van de orde O(n^4) per ronde, met n het aantal spelers. Het aantal rondes is volgens een eenvoudige afschatting ook gelijk aan n (strikte bovengrens). Het zoeken naar 4-cliques kun je als volgt bewerkstelligen. Selecteer in constante tijd de meest beperkte knoop (deze met het minste aantal links; gebruik een Fibonacci heap). Controleer vervolgens alle C^n_3 mogelijke combinaties van uitgaande bogen. Het enige wat rest is om in constante tijd (rij met directe indexering) na te gaan of er ook nog verbindingen zijn tussen de drie knopen die uitmonden in de geselecteerde bogen. Deze techniek herhaal je maximaal n / 4 keer. Dit alles resulteert in de aangename tijdscomplexiteit n * n * (n-1) * (n-2) / (4!) = O(n^4) per ronde.

[ Voor 36% gewijzigd door Nick The Heazk op 24-06-2009 23:34 ]

[Soultaker]

dailyleaf schreef op woensdag 24 juni 2009 @ 22:25:
Dit rolt er uit de debugger:
spelersPerRonde\[5](
\[16](0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15),
\[16](0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15),
\[16](0,5,10,15,1,4,11,14,2,7,8,13,3,6,9,12),
\[16](0,6,11,13,1,7,10,12,2,4,9,15,3,5,8,14),
\[16](0,7,9,14,1,6,8,15,2,5,11,12,3,4,10,13))

Ah cool! De eerste drie rondes had ik handmatig exact hetzelfde bedacht, maar daarna kwam ik er niet meer uit. Wellicht is (N-1)/3 rondes dan wel mogelijk vanaf 16 spelers (want 8 en 12 kunnen zeker niet) waarbij natuurlijk wel naar beneden moet worden afgerond...

@Nick The Heazk: als ik het goed begrijp ga jij nog steeds uit van een online algoritme (dat wil zeggen: je deelt spelers ronde voor ronde in, zonder te backtracken als je vastloopt), maar ik ben er niet van overtuigd dat het zo simpel is. Je heuristiek helpt misschien wel, maar het is mij niet duidelijk of je daarmee het probleem helemaal oplost...

[Nick The Heazk]

Soultaker schreef op woensdag 24 juni 2009 @ 23:29:
@Nick The Heazk: als ik het goed begrijp ga jij nog steeds uit van een online algoritme (dat wil zeggen: je deelt spelers ronde voor ronde in, zonder te backtracken als je vastloopt), maar ik ben er niet van overtuigd dat het zo simpel is. Je heuristiek helpt misschien wel, maar het is mij niet duidelijk of je daarmee het probleem helemaal oplost...

Klopt. Je moet elke ronde een 4DM (4-Dimensional Match) problem oplossen (op de grafe die ik beschreven heb) en dat is NP-Compleet. Dit exact gaan oplossen zodat je een maximaal aantal ronden kan spelen en in elke ronde het 4DM problem kan oplossen, kun je gerust klassificeren als onmogelijk behalve op heel kleine grafen.

[.oisyn]

Er klopt volgens mij weinig van die (N-1)/3. Sowieso kun je alleen meerdere ronden spelen zonder dat 2 mensen meer dan 1x samen spelen als het aantal groepen deelbaar is door 4.

Bij 16, 32 en 48 spelers kom ik op 5 ronden. Bij 64 spelers kom ik op 21 ronden. Alle overige aantallen (onder de 64) hebben gewoon maar 1 ronde. Op zich is dat vrij logisch als je erover nadenkt. Na de eerste ronde heb je N/4 groepen van mensen die niet meer samen mogen spelen. Stel er zijn 4 groepen, dan kun je dus nog maar maximaal 4 rondes aan combinaties maken waarbij je steeds 1 iemand uit elke 1e-ronde-groep haalt en die bij elkaar zet. Kom je dus op 1+4 = 5 rondes voor 16 mensen.

Gezien het feit dat er dan geen onderlinge combinaties meer mogelijk zijn, zou je deze 16 mensen als een enkele groep kunnen zien (zij zijn immers al allemaal met elkaar geweest). Je hebt dus nog 3 groepen van 16 mensen nodig om weer combinaties te kunnen maken. Dit levert die extra 16 op bij 64 mensen - in totaal 21 rondes.

Dit vormt weer een groep van 64 mensen die al allemaal met elkaar gespeeld hebben. De volgende combinaties die je zou kunnen maken is dus met 4 groepen van 64 mensen, oftewel 256 mensen. Dit geeft 64 extra combinaties bovenop de al bestaande 21, waardoor je dus op 85 rondes uitkomt.

Als jij zegt dat jij de vorige keer met 40 deelnemers 10 rondes gespeeld hebt zonder dat er ooit iemand meer dan eens met dezelfde persoon speelt vraag ik me af hoe je dat in hemelsnaam voor elkaar hebt gekregen, aangezien dat volgens mij gewoon niet mogelijk is

De formule voor N spelers is dus:
∑ 4ⁱ
0 <= i < ⁴log N

@Nick: dit probleem is absoluut niet NP-compleet. Mijn implementatie is momenteel O(n²) (zowel in uitvoertijd als in geheugengebruik). Da's aardig polynomiaal als je 't mij vraagt . Hij lijkt op het algo dat Varan beschrijft bovenin de draad, maar dan met het verschil dat je, in plaats van gewoon 3 spelers te halen uit de lijst van de eerste speler, steeds een nieuwe lijst maakt dat de intersectie vormt van de lijsten van de huidige spelers al in de groep en de nieuwe speler die je erbij zoekt. De volgende speler is dan de eerste speler uit die nieuwe lijst, etc.

code:

foreach(alle groepen)
{
    kies een beschikbare speler die nog niet is geweest, voeg 'm toe aan de groep.
    players := lijst met beschikbare spelers.

    foreach(elke van de overige 3 spelers benodigd voor de groep)
    {
        pik een player uit de 'players' lijst.
            indien lijst leeg, geen groepen meer mogelijk, stop.
        voeg die toe aan de groep.
        intersect 'players' lijst met de spelers waar de nieuwe speler nog niet mee heeft gespeeld.
    }

    haal alle 4 spelers uit elke lijst van alle 4 spelers.
    haal alle 4 spelers uit de lijst met beschikbare spelers.
}

[ Voor 31% gewijzigd door .oisyn op 25-06-2009 10:46 ]

[Nick The Heazk]

.oisyn schreef op donderdag 25 juni 2009 @ 01:07:
@Nick: dit probleem is absoluut niet NP-compleet. Mijn implementatie is momenteel O(n²) (zowel in uitvoertijd als in geheugengebruik). Da's aardig polynomiaal als je 't mij vraagt . Hij lijkt op het algo dat Varan beschrijft bovenin de draad, maar dan met het verschil dat je, in plaats van gewoon 3 spelers te halen uit de lijst van de eerste speler, steeds een nieuwe lijst maakt dat de intersectie vormt van de lijsten van de huidige spelers al in de groep en de nieuwe speler die je erbij zoekt. De volgende speler is dan de eerste speler uit die nieuwe lijst, etc.

Dezelfde opmerking van Soultaker is hier van toepassing. Jij schetst hier een greedy algoritme dat geen enkele mogelijkheid tot backtracking heeft. Stel dat je n spelers hebt. Voor een of andere reden heeft speler 8 alleen nog niet gespeeld met spelers 7,6 en 5. In jouw algoritme is het mogelijk dat eerst spelers 7,6 en 5 ergens aan toegewezen worden in een ronde (logisch, want een greedy algoritme op een NPC probleem geeft je niet de exacte oplossing), waardoor er geen toekenning meer mogelijk is voor speler 8.

Het probleem zit hem in lijn 9. Daar ontdek je inderdaad dat een speler niet kan dienen als beginspeler in een groep. Als je dat op mijn grafe-voorstelling zou voorstellen, wil dat simpelweg betekenen dat er geen 4-clique meer mogelijk is met die speler (met enkel de niet-gekleurde knopen). Deze situatie moet je oplossen door te backtracken over alle mogelijke assignments. Dat lijk je te suggereren met regel 9, maar je tijdscomplexiteit gaat de mist in. In regel 8 zijn er ook meerdere keuzes mogelijk. Ook daar zul je over moeten backtracken (wat niet gebeurt).

Voor zo'n greedy algoritme kun je heel eenvoudig een afschatting bekomen. Je moet alle n! permutaties van de spelers beschouwen. Elk van deze permutaties zal een andere uitkomst geven in jouw algoritme (sommige vallen samen, maar om een ordegrootte reductie te bekomen zul je moeten aantonen dat er O(n^n) samenvallen). Hence om een exacte oplossing te vinden zul je in het slechtste geval n! keer moeten backtracken. Waarschijnlijk zal je iets minder moeten backtracken, maar een volledige analyse daarvan lijkt me niet meteen triviaal.

Verder kan je vrij zeker zijn dat dit een NPC probleem is hoor. Het probleem dat je elke ronde moet oplossen is 4DM op de grafe die ik bescheef. Het bouwen van de grafe is een O(n^2) aangelegenheid. Het is duidelijk dat het oplossen van 4DM in deze grafe (per constructie van de grafe) meteen ook een toewijzing geeft voor alle spelers in één ronde. Bijgevolg hebben we een polynoomtijdtransformatie naar een NPC probleem. Omgekeerd is 4DM ook polynoomtijd-transformeerbaar naar het probleem van de TS (in één ronde). Voor elke knoop in het 4DM probleem voeg je een speler in en voor elke boog in 4DM stel je in het probleem van de TS dat de speler nog niet tegen de andere speler heeft gespeeld. Duidelijk een polynoomtijdtransformatie. Aangezien we nu een polynoomtijdtransformatie van 4DM naar het probleem van de TS hebben, volgt daar uit dat (omdat 4DM een NPC probleem is) het probleem van de TS oplossen in één ronde al NPC is.

[ Voor 10% gewijzigd door Nick The Heazk op 25-06-2009 10:15 ]

[.oisyn]

Nick The Heazk schreef op donderdag 25 juni 2009 @ 10:03:
Het probleem zit hem in lijn 9. Daar ontdek je inderdaad dat een speler niet kan dienen als beginspeler in een groep. Als je dat op mijn grafe-voorstelling zou voorstellen, wil dat simpelweg betekenen dat er geen 4-clique meer mogelijk is met die speler (met enkel de niet-gekleurde knopen). Deze situatie moet je oplossen door te backtracken over alle mogelijke assignments.

Mijn regel 9 klopte niet, ik heb 'm aangepast. Als er geen speler meer is, dan zijn er geen groepen meer mogelijk en stopt het algoritme. Verder gaat het er natuurlijk niet om om alle mogelijke oplossingscombinaties te vinden.

[Nick The Heazk]

De TS is inderdaad niet geïnteresseerd in alle mogelijke oplossingen. Echter, met jouw aanpassing blijft hetzelfde probleem bestaan. Er zijn in regel 8 meerdere mogelijke spelers die in aanmerking komen. Nu stop je indien de lijst leeg is, hetgeen overeenkomt met een slechte keuze van de spelers. In mijn grafe is er dan geen 4-clique met de geselecteerde spelers. Dit sluit het bestaan van een oplossing (in één ronde) echter niet uit.

Indien je regel ook nog eens over regel 8 zou backtracken dan kom je essentieel uit op het, eveneens greedy, algoritme dat ik voorstelde. Backtracken over regel 8 impliceert namelijk backtracken over alle mogelijke combinaties om 3 bogen uit een verzameling van n te selecteren (die n is natuurlijk het slechtste geval; je moet natuurlijk enkel de uitgaande bogen beschouwen van een knoop). Hiermee kom je al op O(n^3).

[ Voor 27% gewijzigd door Nick The Heazk op 25-06-2009 11:10 ]

[.oisyn]

Hmm, ik zie al waar de discrepantie zit, ik maak ergens een verkeerde aanname. Even wat aanpassingen doen

[pedorus]

.oisyn schreef op donderdag 25 juni 2009 @ 01:07:
Als jij zegt dat jij de vorige keer met 40 deelnemers 10 rondes gespeeld hebt zonder dat er ooit iemand meer dan eens met dezelfde persoon speelt vraag ik me af hoe je dat in hemelsnaam voor elkaar hebt gekregen, aangezien dat volgens mij gewoon niet mogelijk is

Ok, wat krijg ik van je?

Round 0 15,18,21,37,    0,3,16,17,      4,8,12,24,      9,23,26,39,     13,19,27
,38,    5,20,31,36,     6,14,22,34,     2,10,30,35,     1,7,11,29,      25,28,32
,33,
Round 1 4,5,16,26,      1,10,13,20,     2,3,33,34,      8,19,23,32,     7,21,31,
39,     14,27,29,30,    6,25,35,37,     18,24,28,38,    9,12,17,22,     0,11,15,
36,
Round 2 0,14,20,37,     3,21,23,36,     1,12,26,34,     6,13,15,30,     9,10,24,
32,     8,11,31,38,     19,29,35,39,    7,16,27,28,     4,18,22,33,     2,5,17,2
5,
Round 3 7,12,23,37,     9,28,29,31,     15,22,27,35,    11,20,21,26,    14,32,38
,39,    0,5,19,33,      3,18,25,30,     2,4,13,36,      1,6,17,24,      8,10,16,
34,
Round 4 12,15,29,33,    17,20,27,34,    2,6,21,28,      1,8,14,35,      16,23,25
,38,    7,13,22,26,     3,4,11,32,      5,24,30,39,     9,19,36,37,     0,10,18,
31,
Round 5 0,13,23,24,     8,15,20,28,     1,19,21,30,     6,10,12,39,     7,18,32,
34,     26,33,35,36,    2,11,16,22,     17,29,37,38,    3,5,9,27,       4,14,25,
31,
Round 6 3,19,26,28,     8,13,21,25,     5,6,7,38,       1,22,36,39,     2,15,24,
31,     9,16,18,35,     10,14,17,33,    4,20,23,29,     11,30,34,37,    0,12,27,
32,
Round 7 13,28,34,35,    3,8,37,39,      6,9,20,33,      0,2,26,38,      10,11,25
,27,    12,14,18,36,    1,5,15,23,      4,7,17,19,      16,21,24,29,    22,30,31
,32,
Round 8 0,4,28,30,      11,13,33,39,    1,16,32,37,     19,20,22,24,    25,29,34
,36,    8,17,18,26,     6,23,27,31,     5,12,21,35,     2,7,9,14,       3,10,15,
38,
Round 9 11,17,23,35,    3,12,13,31,     7,8,30,36,      2,18,20,39,     0,1,9,25
,       24,27,33,37,    4,21,34,38,     5,10,22,28,     14,15,16,19,    6,26,29,
32,

Het probleem was wat te groot om backtracking toe te passen zoals in de TS, dus ik heb het iets anders gedaan:

C#:

        static int players = 40;
        static int tables = players / 4;
        static int rounds = 10;
        int[][] scheme = new int[rounds][];
        int[][] playersOverlap = new int[players][];

        int replaceScore(int round, int tpos, int pos, int playerRem, int playerAdd) {
            int result = 0;
            for (int i = tpos; i < tpos + 4; i++)
                if (i != pos)
                {
                    if (playersOverlap[playerRem][scheme[round][i]] > 1)
                        result--;
                    if (playersOverlap[playerAdd][scheme[round][i]] >= 1)
                        result++;
                }
            return result;
        }

        void printSolution()
        {
            for (int i = 0; i < rounds; i++)
            {
                Console.WriteLine();
                Console.Write("Round " + i);
                for (int j = 0; j < tables; j++)
                {
                    Console.Write("\t");
                    foreach (int player in scheme[i].Skip(j*4).Take(4).OrderBy(a=>a))
                    {
                        Console.Write(player + ",");
       }}}}

        void getSolution() {
            Random random = new Random();

            scheme[0] = Enumerable.Range(0, players).ToArray();
            for (int i = 1; i < scheme.Length; i++)
            {
                scheme[i] = Enumerable.Range(0, players)
                    .OrderBy(a => random.Next()).ToArray();
            }
            for (int i = 0; i < playersOverlap.Length; i++)
            {
                playersOverlap[i] = new int[players];
            }
            int round;
            for (round = 0; round < rounds; round++)
                for (int table = 0; table < tables; table++)
                    for (int pos1 = 0; pos1 < 4; pos1++)
                        for (int pos2 = 0; pos2 < 4; pos2++)
                            if (pos1 != pos2) 
                                playersOverlap[scheme[round][table * 4 + pos1]]
                                    [scheme[round][table * 4 + pos2]]++;
            int score = playersOverlap.Sum(a => a.Sum(b => Math.Max(0, b - 1)))/2;

            for (long iteration=20000000000;iteration>0;iteration--) {
                round = random.Next(rounds); //random.Next(rounds-1)+1 werkt slechter;
                int posA = random.Next(players);
                int posB = random.Next(players);
                int tposA = posA - (posA % 4);
                int tposB = posB - (posB % 4);
                if (tposA == tposB)
                    continue;
                int playerA = scheme[round][posA];
                int playerB = scheme[round][posB];
                int scorediff = replaceScore(round, tposA, posA, playerA, playerB) + 
                    replaceScore(round, tposB, posB, playerB, playerA);
                if ((scorediff <= 0) || (1/Math.Exp(scorediff)*Math.Log(iteration)
                    /5000000>random.NextDouble()))
                {
                    scheme[round][posA] = playerB;
                    for (int i = tposA; i < tposA + 4; i++)
                        if (i != posA)
                        {
                            playersOverlap[playerA][scheme[round][i]]--;
                            playersOverlap[scheme[round][i]][playerA]--;
                            playersOverlap[playerB][scheme[round][i]]++;
                            playersOverlap[scheme[round][i]][playerB]++;
                        }
                    scheme[round][posB] = playerA;
                    for (int i = tposB; i < tposB + 4; i++)
                        if (i != posB)
                        {
                            playersOverlap[playerB][scheme[round][i]]--;
                            playersOverlap[scheme[round][i]][playerB]--;
                            playersOverlap[playerA][scheme[round][i]]++;
                            playersOverlap[scheme[round][i]][playerA]++;
                        }
                    score += scorediff;
                    if (score == 0) break;
        }}}

Het idee hier is Simulated annealing, wat tenminste altijd een oplossing geeft, ook al is de overlap (score) niet 0 op het einde. Hier beginnen we met een willekeurige indeling, en swappen we vervolgens willekeurig steeds 0 of 2 spelers per ronde. Als er verbetering is, dan swappen we altijd. Zo niet, dan hangt het af van de verslechtering, het moment, en een random getal.

De code kan natuurlijk wel beter (playersOverlap bevat dezelfde data 2x, iteraties is hier heel erg hoog, en c ook (20000000000/5000000), System.Random is niet heel efficient, Math.Log hoeft niet iedere iteratie aangeroepen, etc.)

offtopic:
Oh, ik zie dat we hier in de Devschuur zitten ipv in SG, maar die code weghalen is ook weer zoiets..

[.oisyn]

pedorus schreef op donderdag 25 juni 2009 @ 11:26:
[...]

Ok, wat krijg ik van je?

Niets meer, ik had mezelf 2 minuten voor jouw post al ingedekt

[Nick The Heazk]

.oisyn schreef op donderdag 25 juni 2009 @ 01:07:
Bij 16, 32 en 48 spelers kom ik op 5 ronden. Bij 64 spelers kom ik op 21 ronden. Alle overige aantallen (onder de 64) hebben gewoon maar 1 ronde. Op zich is dat vrij logisch als je erover nadenkt. Na de eerste ronde heb je N/4 groepen van mensen die niet meer samen mogen spelen. Stel er zijn 4 groepen, dan kun je dus nog maar maximaal 4 rondes aan combinaties maken waarbij je steeds 1 iemand uit elke 1e-ronde-groep haalt en die bij elkaar zet. Kom je dus op 1+4 = 5 rondes voor 16 mensen.

Gezien het feit dat er dan geen onderlinge combinaties meer mogelijk zijn, zou je deze 16 mensen als een enkele groep kunnen zien (zij zijn immers al allemaal met elkaar geweest). Je hebt dus nog 3 groepen van 16 mensen nodig om weer combinaties te kunnen maken. Dit levert die extra 16 op bij 64 mensen - in totaal 21 rondes.

Dit vormt weer een groep van 64 mensen die al allemaal met elkaar gespeeld hebben. De volgende combinaties die je zou kunnen maken is dus met 4 groepen van 64 mensen, oftewel 256 mensen. Dit geeft 64 extra combinaties bovenop de al bestaande 21, waardoor je dus op 85 rondes uitkomt.

Als jij zegt dat jij de vorige keer met 40 deelnemers 10 rondes gespeeld hebt zonder dat er ooit iemand meer dan eens met dezelfde persoon speelt vraag ik me af hoe je dat in hemelsnaam voor elkaar hebt gekregen, aangezien dat volgens mij gewoon niet mogelijk is

De formule voor N spelers is dus:
∑ 4ⁱ
0 <= i < ⁴log N

Gebaseerd op deze observatie kan je in ieder geval een efficiënt algoritme ontwerpen. Ik ben nog niet helemaal uit de tijdscomplexiteit, maar ik denk dat we op O(n) per ronde komen en aangezien er slechts O(lg n) ronden zijn, zou de totale tijdscomplexiteit op O(n lg n) moeten kunnen uitkomen. (Wat overigens geen contradictie oplevert met het feit dat de algemene vorm van het probleem NPC is; in dit specifieke probleem beginnen we echter altijd van een volle grafe).

Indien deze observatie correct is, kun je op gestructureerde wijze de groepen genereren. Dat zou overigens met een heel elegant algoritme moeten kunnen. Vanavond eens kijken of ik iets werkend kan implementeren.

[ Voor 4% gewijzigd door Nick The Heazk op 25-06-2009 11:43 ]

[.oisyn]

Die observatie klopt dus niet helemaal en was dus gebaseerd op mijn foute aanname. Ik ging er namelijk vanuit dat al gemaakte groepen in de huidige ronde correct waren. Als je die aanname maakt dan hoef je niet te backtracken tijdens het maken van een nieuwe groep. Echter, als er een groep fout gaat, betekent dat niet dat de ronde niet meer kan, maar dat je de eerdere groepen anders moet gaan indelen. Deze laatste stap had ik dus overgeslagen.

Als je die stap niet overslaat, zoals het zou moeten, dan moet je ook gaan backtracken bij het indelen in de groep zelf, en blijft er dus weinig over van mijn algoritme en mijn stelling dat het niet NP-compleet zou zijn . Mea culpa.

Waar mijn observatie feitelijk op gebaseerd is (zonder dat ik dat zelf realiseerde) zijn de gevallen waarbij iedereen precies 1 keer met elke andere speler gespeeld heeft. Dat is mogelijk als er 4^N spelers zijn, en dan is het aantal ronden de formule die ik gaf. En dat probleem is dus niet NP.

[ Voor 15% gewijzigd door .oisyn op 25-06-2009 12:17 ]

[pedorus]

.oisyn schreef op donderdag 25 juni 2009 @ 12:11:
Waar mijn observatie feitelijk op gebaseerd is (zonder dat ik dat zelf realiseerde) zijn de gevallen waarbij iedereen precies 1 keer met elke andere speler gespeeld heeft. Dat is mogelijk als er 4^N spelers zijn, en dan is het aantal ronden de formule die ik gaf. En dat probleem is dus niet NP.

Ik had eerst een andere versie gemaakt ('eerste de beste mogelijke speler'), aan de hand van het voorbeeld met 16 spelers. Die versie was veel minder regels, en werkte heel erg snel, maar die werkte enkel bij 16.. Aanpassen van de heuristiek lukte niet echt. Bij 64 en 256 geeft die ook direct een oplossing (in 0 sec), maar dat zijn ook de bijzondere gevallen. Voor wie wat wil spelen:

C#:

int players = 256;
int tables = players / 4;
int rounds = (players - 1) / 3;
int[,,] playersPerRound = new int[rounds, tables, 4];
bool[,] hadForPlayer = new bool[players, players];

for (int round = 0; round < rounds; round++)
{
    Random random = new Random();
    Console.WriteLine();
    Console.Write("Round " + round + ":");
    bool[] hadThisRound = new bool[players];
    for (int table = 0; table < tables; table++)
    {
        Console.Write("\t");
        bool[] badPlayerAtCurrentTable = (bool[])hadThisRound.Clone();        
        for (int position = 0; position < 4; position++)
        {
            int nextPlayer = 0; //-1
            int bestFreedomLeft = -1;
            int choice=0;//random.Next(badPlayerAtCurrentTable.Count(a => a == false));
            while (badPlayerAtCurrentTable[nextPlayer] || choice-->0) nextPlayer++;
      /*      for (int i = 0; i < players; i++)
            {
                if (!badPlayerAtCurrentTable[i])
                {
                    int freedomLeft = 0;
                    for (int j = 0; j < players; j++)
                    {
                        if (!badPlayerAtCurrentTable[j] && !hadForPlayer[i, j])
                            freedomLeft++;
                    }
                    if (freedomLeft > bestFreedomLeft)
                    {
                        bestFreedomLeft = freedomLeft;
                        nextPlayer = i;
                    }
                }
            } */
            hadThisRound[nextPlayer] = true;
            badPlayerAtCurrentTable[nextPlayer] = true;
            for (int i = 0; i < players; i++)
                if (hadForPlayer[nextPlayer, i]) badPlayerAtCurrentTable[i] = true;
            for (int i = 0; i < position; i++)
            {
                hadForPlayer[playersPerRound[round, table, i], nextPlayer] = true;
                hadForPlayer[nextPlayer, playersPerRound[round, table, i]] = true;
            }
            playersPerRound[round, table, position] = nextPlayer;
            Console.Write(nextPlayer+",");
            nextPlayer++;
        }

[dailyleaf]

Ik moet zeggen dat ik alle reacties met veel bewondering lees.

Helaas is de materie momenteel nog te gecompliceerd voor me.
Ik zit dan nog op school en sommige termen zijn vluchtig behandeld, terwijl anderen (nog) niet ter sprake zijn gekomen.

Voordat jullie de indruk krijgen dat dit een verkapte huiswerk opdracht is, dat is het niet.
Dit probleem speelt al langer, alleen nu we op school bezig zijn met datastructuren en algoritmen leek het me een mooi moment om hiermee aan de slag te gaan.

De eerste reactie van Pedorus is er één om in te lijsten.
Hoewel wij op school geen les c# krijgen en ik de code verre van begrijp, heb ik het wel 1 op 1 kunnen kopiëren en runnen.
Wat Pedorus al zei, het geeft misschien niet een perfecte oplossing, maar sowieso een nagenoeg perfecte oplossing.
(Overigens krijg ik met 40 spelers en 10 ronden geen resultaat.)

edit:
Na een half uur wel. Of de iteraties waren op, niet op gelet.

Ik zal dit topic zeker blijven volgen, maar kan dus niet op niveau meepraten.

[ Voor 4% gewijzigd door dailyleaf op 26-06-2009 12:07 ]

[zoxzo]

Zie onder andere "The Social Golfer Problem":

[pedorus]

zoxzo schreef op vrijdag 26 juni 2009 @ 23:53:
Zie onder andere "The Social Golfer Problem":

Ha, het missende keyword. Oplossingen staan op http://www.cs.st-andrews....golf_by_group_size-4.html .
Blijkbaar zijn er met 40 spelers zelfs 13 rondes mogelijk, enkel de oplossing staat er helaas niet bij... Verder nog redelijk wat open problemen (36 speler, 44 spelers, enz). En als je ook een schema wil maken voor 41 spelers, met zo min mogelijk afwisselende kant-zitters, dan is dat ook nog redelijk open, of ik kan het niet zo snel vinden.

dailyleaf schreef op vrijdag 26 juni 2009 @ 01:28:
Hoewel wij op school geen les c# krijgen en ik de code verre van begrijp, heb ik het wel 1 op 1 kunnen kopiëren en runnen.

Even een uitleg dan over mijn eerst-geposte programma. Ik gok dat het probleem vooral zit in LINQ/lambda-functies, want die hebt je in c++ (normaal gesproken) niet. Ik gebruik ze in de functie getSolution(), die trouwens beter iets als createSolution() had kunnen heten, omdat er niets wordt teruggegeven. In die functie wordt allereerst een startoplossing gemaakt, en die vervolgens wordt er met willekeurig verwisselen geprobeerd om die oplossing beter te maken.

Het begint gelijk bij de eerste regel, bij de indeling van ronde 0, hoewel je dat ook nog wel in c++ kan maken.

C#:

            scheme[0] = Enumerable.Range(0, players).ToArray();

Met wat langere code is dat gewoon vullen met 0,1,2,...,players-1:

C#:

            scheme[0] = new int[players];
            for (int player = 0; player < players; player++)
                scheme[0][player] = player;

De volgende rondes worden willekeurig ingedeeld. Ik gebruik daar nu OrderBy van LINQ en een lamda-functie voor, maar in andere talen kan dat bijvoorbeeld met een Fisher–Yates shuffle (voorbeeldcode daar).

En dan volgt er iets om playersOverlap te zetten, en de score te berekenen. Dat laatste gaat weer met LINQ;

C#:

            int score = playersOverlap.Sum(a => a.Sum(b => Math.Max(0, b - 1)))/2;

Maar je kan exact hetzelfde resultaat krijgen door gebruik te maken van for-loopjes, en de symmetrie van die tabel:

C#:

            int score = 0;
            for (int i = 0; i < players; i++)
                for (int j = 0; j < i; j++)
                    if (playersOverlap[i][j] > 1)
                        score += playersOverlap[i][j] - 1;

Hierna is de initiele oplossing gedaan. Dan volgt het daadwerkelijke simulated annealing:

C#:

            for (long iteration=20000000000;iteration>0;iteration--) { 

20000000000 is een getal dat ik even voor 40/10 heb neergezet, maar waarschijnlijk iets te hoog. Wat het beter kan zijn, daar zul je wat voor moeten uitproberen(, of een algoritme voor in moeten zetten dat dat voor je doet). Het beste getal zal ook nog eens van het probleem afhangen. Hetzelfde geld voor de 5000000 op regel 70, je moet die twee in combinatie zien.

Wat ook wel gebeurd is dat er 2 for-loopjes worden gebruikt, een buitenste voor de 'temperatuur', en 1 binnenste met gewoon een aantal duizend subiteraties bij die temperatuur. In dat geval hoef je "Math.Log(iteration)/5000000" veel minder vaak te berekenen.

Dan volgt er een stukje waarin willekeurig 2 plekken om te verwisselen worden gekozen:

C#:

                round = random.Next(rounds); //random.Next(rounds-1)+1 werkt slechter;
                int posA = random.Next(players);
                int posB = random.Next(players);

Regel 58 kan beter pas na de continue staan, want anders trek je af en toe overbodige random nummers, en dat kost onnodig tijd. System.Random kan trouwens beter vervangen worden door iets snellers en iets met een langere periode (voorbeeld, maar kan vast nog sneller).

Ik had eerst bedacht dat de eerste ronde beter gewoon 1,2,3,... zou kunnen blijven, maar in de praktijk bracht dat in het geval van 40 spelers en 10 ronden niet de beste oplossing. Misschien dat voor het afdrukken van de oplossing nog even een omnummering moet plaatsvinden dus.

Dan is de kern van het overnemen van een nieuwe oplossing te vinden op regel 69:

C#:

               if ((scorediff <= 0) || (1/Math.Exp(scorediff)*Math.Log(iteration)
                    /5000000>random.NextDouble()))

scorediff, het verschil aan score met de huidige oplossing, is berekend met behulp van replaceScore voor de efficiency. Betere, of gelijke oplossingen worden altijd geaccepteerd (gelijke valt over te discussieren of dat altijd een goed idee is). Bij slechtere oplossingen hangt het af van een random getal, en de huidige 'temperatuur'(hier: iteration). In het begin wordt sneller voor een slechtere oplossing gekozen.

Als een oplossing wordt overgenomen, dan worden scheme en playersOverlap aangepast. Omdat playersOverlap dezelfde data 2 keer bevat, roept dat de vraag op of dat niet efficienter kan. Of dat echt sneller is, kom je achter door testen. Als je playersOverlap aanpast, moet replaceScore natuurlijk ook worden aangepast.

Dan is er hier nog een belangrijke regel (stoppen als het niet beter kan):

C#:

                    if (score == 0) break;

Daar kan beter iedere betere oplossing dan tot dan toe gezien is worden opgeslagen, en/of afgedrukt. Het is namelijk niet perse zo dat de eindoplossing van het algoritme ook echt de beste geziene oplossing is.