Otteluohjelman laadintaongelma

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Pienoinen probleemi otteluohjelmakaavioiden laadinnassa, tosin aivan akateeminen, sillä ratkaisulla en oikeastaan tee mitään, kunhan rupesi askarruttamaan ja olen liian kiireinen (laiska) paneutumaan siihen itse.

Tietty määrä joukkueita, joilla kaikille täytyy järjestää tietty määrä otteluluita kullekin. Esimerkiksi 12 joukkuetta ja kaikille joukkueille pitää järjestää neljä ottelua. Kyseessä pitää olla eri ottelut. Sama ottelupari ei saa esiintyä kuin kerran. (Me-Te käy, mutta ei enää Te-Me)

Millaisella yleisellä laskukaavalla saan kaikkien erilaisten mahdollisuuksien lukumään selville?

A = joukkueitten määrä
B = jokaiselle tulevien otteluiden määrä

X = Kaikki eri (ainutkertaiset) permutaatiot

Kommentit (12)

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

Tuota voisi lähteä purkamaan havainnollistamalla asiaa symmetrisellä matriisilla, jonka alkiot ovat 0 tai 1 sen mukaan, ottelevatko annettua riviä ja saraketta vastaavat joukkueet keskenään vain eivät. Diagonaalille tulee pelkkiä nollia, sillä joukkue ei voi otella itseään vastaan.

Kysymys kuuluu siis: kuinka monta sellaista {0,1}-alkioista, 0-diagonaalista ja symmetristä A*A matriisia on olemassa, jonka jokaisen rivin (ja myös sarakkeen) 1-alkioiden määrä on B?

Binomikertoimillahan tuota muuten lähtisi laskemaan, mutta symmetrisyys pitää myös saada jotenkin hallintaan.

We're all mad here.

Vierailija

Tämä taitaakin olla aika vaikea ongelma...

Koitin miettiä generoivia funktioita yms. mutta ne antavat vastauksia vähän eri kysymyksiin.

Tuosta voi generoida äärellisen pitkän boolean lauseen, jolloin kysymys kuuluu että kuinka monella tavalla se voidaan toteuttaa. Harmi vain että bittejä on f(n) = n * (n - 1) / 2 kpl, jolloin totuustauluun tulee rivejä (helpoimmalla toteutuksella) 2^f(n) kpl.

Toisaalta tuon hakuavaruuden voisi ajatella binääripuuna jossa on f(n) tasoa, josta pitäisi laskea että kuinka monta lasta siihen kaikkiaan kuuluu. Ehkä sen voisi ratkaista järkevässä ajassa.

Toivottavasti tähän on keksitty joku simppeli ja elegantti ratkaisu

Vierailija

Kelpaako neuroverkko tai ehkä ennemminkin geneettinen algoritmi jollain sopivalla fitnessfunkkarilla. Sillä vois lähtee tekee.

Vierailija

Erilaisia ottelupareja on A-1 + A-2 + ... + 2 + 1 = (A-1)*(1+ A-1)/2 = A*(A-1)/2
Näistä voidaan valita B kappaletta A*(A-1)/2 yli B = (A*(A-1)/2)! / (B!*(A*(A-1)/2 - B)!) eri tavalla.

Olisiko näin?

Vierailija

Tuossa on vasta se että kuinka monta erilaista valintaa yksi joukkue voi tehdä, ei siis kaikkien erilaisten turnauksien määrä.

edit: Eikun niitä yhden joukkueen vaihtoehtoja on tietysti n yli B:n. Periaatteessa turnauksia voisi valita n * (n - 1) / 2 yli n*B:n, mutta tuosta pitäisi vielä poistaa ne missä yksi joukkue pelaisi liikaa / liian vähän pelejä.

edit2: hmm tuokin taitaa olla väärin :/

Vierailija

Hmm tein C++:lla iteroivan ratkaisun.

[code:1lni9lcz]7 teams, 1 matches: 0
7 teams, 2 matches: 465
7 teams, 3 matches: 0
7 teams, 4 matches: 465
7 teams, 5 matches: 0
7 teams, 6 matches: 1[/code:1lni9lcz]

[code:1lni9lcz]8 teams, 1 matches: 105
8 teams, 2 matches: 3507
8 teams, 3 matches: 19355
8 teams, 4 matches: 19355
8 teams, 5 matches: 3507
8 teams, 6 matches: 105
8 teams, 7 matches: 1[/code:1lni9lcz]

Jos nuo on oikein niin voisi kokeilla optimoida siitä fiksumman.

Vierailija

Voisi olla oikein.

Ensiksi hämäsi tuo, että 7 joukkuetta ja 1 peli antoi tulokseksi nollan, mutta onhan se oikein.

Jännä juttu tuo peilikuvamaisuus. Jos tuohon 8 joukkueen sarjaan lisää 0 ottelua yksi kierros, niin sen huomaa vielä selvemmin.

Eilen tutkin tuota hieman aikaa manuaalisesti ja huomasin saman, minkä noistakin voi päätellä. Ottelumäärään vaikuttavat joukkueiden määrät, pelien määrät ja näiden kahden erotus. Siitä tuo peilikuvamaisuus.

[code:q3gjcef7]8 teams, 3 matches: 19355
8 teams, 4 matches: 19355[/code:q3gjcef7]

Kahdeksan joukkuetta eli jokaisella 7 vastusta eli 3+4 tai 4+3.

Tuosta voisi jotain yleistystä lähteä hakemaan. Ensi viikolla on aikaa keskittyä tuohon, nyt ei vielä aika riitä.

Laskepa 5 teams tulos. Sen oikeellisuus on helpohko tarkistaa manuaalisesti kynätestillä.

Vierailija

Muutama lisätulos:

[code:32vi0e9g]5 teams, 1 matches: 0
5 teams, 2 matches: 12
5 teams, 3 matches: 0[/code:32vi0e9g]

[code:32vi0e9g]10 teams, 1 matches: 945
10 teams, 2 matches: 286884
10 teams, 3 matches: 1.11808e+007
10 teams, 4 matches: 6.64626e+007[/code:32vi0e9g]

Noissa 10 joukkueen laskelmissa rupeaa kestämään jo yli vuorokausi jos haluaa 2 - 5 ottelun tulokset.

Vierailija
msdos464
Muutama lisätulos:

[code:24yznls2]5 teams, 1 matches: 0
5 teams, 2 matches: 12
5 teams, 3 matches: 0[/code:24yznls2]




Jommalla kummalla täytyy nyt jossain olla virhe. Käsin kun tein tuon 5 teams, 2 matches sain tulokseksi 10 uniikkia matsia. Seuraava kaavio saattaa selventää asiaa
[code:24yznls2]
|*|123456|123456|123456|123456|123456|

|1|******|111***|111***|111***|111***|
|2|111***|******|1**11*|1**11*|1**11*|
|3|1**11*|1**11*|******|*1*1*1|*1*1*1|
|4|*1*1*1|*1*1*1|*1*1*1|******|**1*11|
|5|**1*11|**1*11|**1*11|**1*11|******|

|-|D-----|------|------|---D--|---D--|
[/code:24yznls2]

Taulukko on jaettu kuuden kierroksen blokkeihin. Ensimmäisessä blokissa joukkue 1 pelaa kaikkia muita joukkueita vastaan. Ykköset merkkaavat peliä ja asteriskit ei-peliä. Kakkosblokissa kotijoukkue on numero kaksi etc. Noin laskien otteluita tulee kaikenkaikkiaan 30. Näistä uniikkeja on 1/3. Alimmalla rivilla on merkattuna D-kirjaimella tuplat [malliksi vain yhdestä kierroksesta].

Yleistä laskukaavaa en ole ehtinyt miettiä, seuraavista luvuista se pitäisi jollain lailla vääntää.

Joukkueiden määrä 5
Mahdollisten vastuksien määrä 4
Pelien määrä 2
Vapaiden paikkojen määrä 5-2=3

Tällä ongelmalla [tai sen ratkaisulla] voisi sellainen käytännön sovellus, että turnausjärjestelijä voisi valita ne otteluparit, joita ei lopullisessa ottelukaaviossa saa olla. Tällainen tilanne tulee esimerkiksi junnujääkiekkoturnauksissa, joissa Helsinkiin on matkustanut kolme Tamperelaisjoukkuetta ja kolme Turkulaisjoukkuetta ja loput Helsingistä ja ympäri maata. Ei ole järkevää, että että Trelaiset matkustavat 150 kilometriä Helsinkiin pelatakseen keskinäisiä otteluita.

Tämän voisi toteuttaa vaikkapa Excell -makrolla, joka hakisi kaikki ne ohjelmavaihtoehdot, joissa ehdot täyttyvät ja järjestäjä valitsisi niistä jonkin [parhaimman].

Säästyisi monelta haukulta ja hammastenkiristelyltä.

Vierailija

Tässä kaikki vaihtoehdot:

[code:iwj5l39x]combination 1
...XX
..X.X
.X.X.
X.X..
XX...

combination 2
...XX
..XX.
.X..X
XX...
X.X..

combination 3
..X.X
...XX
X..X.
.XX..
XX...

combination 4
..X.X
..XX.
XX...
.X..X
X..X.

combination 5
..XX.
...XX
X...X
XX...
.XX..

combination 6
..XX.
..X.X
XX...
X...X
.X.X.

combination 7
.X..X
X..X.
...XX
.XX..
X.X..

combination 8
.X..X
X.X..
.X.X.
..X.X
X..X.

combination 9
.X.X.
X...X
...XX
X.X..
.XX..

combination 10
.X.X.
X.X..
.X..X
X...X
..XX.

combination 11
.XX..
X...X
X..X.
..X.X
.X.X.

combination 12
.XX..
X..X.
X...X
.X..X
..XX.

5 teams, 2 matches: 12[/code:iwj5l39x]

Jänniä koukeroita

Vierailija
Phony
Tämän voisi toteuttaa vaikkapa Excell -makrolla,

Onko koti/vieras asetelmalla merkitystä?
Entä pelikenttien määrä ja pelistä peliin tauko?

Joukkueet
He, Ta1, Ta2, Tu1, Tu2, Va

Heti neljännessä pelissä tulee mietittävää ilman taukojakin.

Uusimmat

Suosituimmat