[ALG] Optimale teamindeling berekening

[bodiam]

Beste mensen,

Ik was vandaag bezig met een programma om hockeypoules te genereren. Helaas is mijn wiskunde kennis niet zo geweldig, vandaar deze post. Het programma is overigens geschreven in Java, maar dat maakt voor de aard van het probleem niet heel veel uit.

Ik moet hockeypoules genereren aan de hand van een X aantal teams. X is altijd 18 of hoger (daaronder liggen allemaal uitzonderingssituaties). Bij 18 en daarboven moeten de teams ingedeeld worden in poules van 6 tot 8. Een gelijkmatige verdeling is gewenst, maar niet noodzakelijk.

Een voorbeeld:
Als er 18 teams aangeboden worden, worden er 3 (6 + 6 + 6) poules gemaakt.
Zijn er 19 teams, dan 3 poules (6 + 6 + 7).
Bij 29 teams 4 poules ( 6 + 7 + 8 + 8 )
etc.

Nu is het me wel gelukt om het te maken (zie onder), maar ik kan ook wel zien dat dit niet de meeste geweldige implementatie is. Ik hoopte daarom dat iemand mij hiermee kan helpen.

Java:

public static void createPoules(int teamCount)
{
  System.out.println("Creating poules for " + teamCount + " teams.");
                                                  //  19           22
  int pouleCount = teamCount / 6;                 // = 3          = 3
  int restTeams  = teamCount % 6;                 // = 1          = 4

  int[] poules = new int[pouleCount];             // 3 arrays     3 arrays
  for(int i = 0; i < poules.length; i ++)
  {  poules[i] = 6;
  }

  int fullTeams    = restTeams / 2;// 3  // = 0          = 1
  int notFullTeams = restTeams % 2;// 3  // = 1          = 1

  for( int i = 0; i < poules.length; i ++ )
  {if( i < fullTeams )
    { poules[i]+=2;
    }
    else
    {poules[i]+= notFullTeams;
      break;
    }
  }

  System.out.println("Created poules");
  for(int i = 0; i < poules.length; i ++)
  {  System.out.print( poules[i] + ", ");
  }
}

Alvast bedankt. Erik.

[orca]

je kan natuurlijk ook een tabel maken voor de verschillende teams aantallen.

je zal meer met de wedstrijden in een poule bezig zijn dan met de onderverdeling..

dan kan je even met de hand invullen hoe de poules ingevuld moeten worden van 18 teams tot het aantal dat je wilt, dit werk hoef je maar eenmalig te doen..

[bodiam]

Hoi Orca, bedankt voor je antwoord, maar ik heb geen limiet van het maximaal aantal teams. Je oplossing gaat dus niet echt op. Daarnaast ben ik ook gewoon erg benieuwd naar het antwoord, of ik het echt nodig zou hebben of niet.

[Eelis]

.

[ Voor 99% gewijzigd door Eelis op 18-02-2015 19:10 ]

[.oisyn]

Ik zou het op dezelfde manier aanpakken zoals jij nu gedaan hebt, hoewel het verdelen van de restteams in de pools verkeerd gaat. Bij 21 teams wil je 3 poules van 7, jij geeft echter poules van resp. 8, 7 en 6.

Bedenk dat je bij een poule pas 2 teams extra in kan delen als alle overige poules ook minimaal 1 team extra krijgen. Anders krijg je een poule van 8 en een van 6, wat meteen al betekent dat je dat beter kunt verdelen door er één van die 8 in de poule van 6 in te delen. Ergo, er zijn een aantal poules die 1 team meer krijgen dan de rest van de poules. Dat zijn er precies restTeams % pouleCount. Nou moet je alleen nog bedenken hoeveel alle teams er nou bij krijgen: moet je gewoon bij de vollere teams 1 optellen, of juist 2 en krijgt de rest er 1 bij? Het antwoord daarop is vrij simpel, je kunt overal 1 bij tellen als je minstens zoveel restteams hebt als dat er poules zijn.

[ Voor 3% gewijzigd door .oisyn op 12-09-2004 21:28 ]

[bodiam]

Okee, bedankt iedereen. Ik heb je wijziging ook meegenomen .oisyn. Het heeft de code echt tot een minimum beperkt. Het is erg duidelijk zo. Ik ga nu een 2de versie er in bouwen die een zo klein mogelijk aantal poules maakt (%8) ipv een zo groot mogelijk aantal.

Thanks!

[Verwijderd]

Eerst een opmerking: als je als voorwaarde stelt dat pools uit 6 t/m 9 man bestaan zijn er geen uitzonderingssituaties, bij 6 t/m 8 man vormt enkel 17 teams of minder dan 12 teams een probleem.

Hier een generieke oplossing die probeert zo min mogelijk pools te genereren, als je liever meer pools hebt moet je de v-variabele lus laten oplopen ipv. aflopen (in C++, maar eenvoudig om te zetten, std::cout is niet meer dan een print):

C++:

#include <iostream>

const int MIN_PER_POOL= 6;
const int MAX_PER_POOL= 8;

int main()
{
    for(int teams= MIN_PER_POOL * 3; teams <= 100; ++teams) {
        int verdeel= 0;
        int overschot= teams;
        for(int v= MAX_PER_POOL; v >= MIN_PER_POOL; --v) {
            int pools= teams / v;
            int over= teams % v;
            if(v == MAX_PER_POOL && over != 0) continue;
            if(over <= pools) {
                int alt= pools - over;
                if(over > alt) over= alt;
            }
            if(over < overschot) {
                overschot= over;
                verdeel= v;
            }
        }
        int pools= teams / verdeel;
        overschot= teams % verdeel;
        std::cout << teams << " teams:";
        for(; pools; --pools) {
            int v= verdeel;
            if(overschot > 0) {
                ++v;
                --overschot;
            }
            std::cout << ' ' << v;
        }
        std::cout << '\n';
    }
    return 0;
}

edit: bale klopt toch niet helemaal, als de teams deelbaar zij door 8 gaat het fout, ff klooien.
edit2: nu klopt het

[ Voor 23% gewijzigd door Verwijderd op 13-09-2004 00:11 ]