Eri vaihtoehtojen lukumäärien laskeminen käsin on suhteellisen hidasta. Esitän tässä, miten käytin Python ohjelmointikieltä pienen käytännön ongelman ratkaisemiseen. Samalla kerron miten minun aivoni pikkuhiljaa kehittivät parempia ratkaisuja ongelman ratkaisuun.

Ongelman kuvailu

Ystäväni, kutsutaan häntä vaikka nimellä Jussi, pyysi minua auttamaan erään konferenssin järjestelyissä. Ilmoittautumisen yhteydessä osallistujilta oli kysytty mihin kahteen työpajaan he haluaisivat ilmoittautua kahdeksasta eri vaihtoehdosta. Konferenssitilassa on neljä huonetta, niinpä nuo kahdeksan työpajaa järjestetään siten, että ensin on samaan aikaan neljä rinnakkaista työpajaa ja sen jälkeen loput neljä. Työpajojen väliajalla osallistujat voivat tietysti vaihtaa huonetta. Jussi oli laskenut ilmoittautumisista, millaisia valintoja osallistujat olivat tehneet ja kuinka monta kutakin valintaa oli. Nyt Jussi halusi tietää, mikä olisi paras vaihtoehto eli kokousohjelma, järjestää nuo kahdeksan työpajaa neljän ryhmissä. 

Jussi antoi minulle valinnat Excel-tiedostona, esitän tässä luvut Pythonin listoina muodossa [ensimmäinen valinta, toinen valinta, lukumäärä]. Kahdessa ensimmäisessä alkiossa olevat luvut ovat työpajojen numeroita 1, …, 8. Jos ensimmäinen luku on nolla, niin osallistuja oli valinnut vain yhden vaihtoehdon.

[0, 1, 2], [0, 2, 1], [0, 3, 1], [1, 2, 26], [1, 3, 2], [1, 4, 15], [1, 5, 3], [1, 6, 1], [1, 7, 16], [2, 4, 9], [2, 5, 1], [2, 7, 17], [2, 8, 1], [3, 4, 1], [3, 5, 6], [3, 6, 2], [3, 7, 3], [4, 5, 6], [4, 6, 2], [4, 7, 6], [5, 6, 3], [5, 7, 6], [5, 8, 5], [6, 7, 4], [6, 8, 1], [7, 8, 2]

ensimmäinen ratkaisu käsin

Kun sain kyseisen Excel-taulukon, otin avukseni kynän ja paperia. Hetken lukuja tuijotettuani, aloin järkeilemään suurin piirtein näin. Eniten on valintoja 1 ja 2. Niinpä niiden tulee olla eri aikaan.

1
2

Seuraavaksi eniten on 2 ja 7 eli 7 pitää olla eri puolella kuin 2.

1	7
2

Seuraavaksi eniten on 1 ja 7, mutta ne ovat jo taulukossa. Seuraavaksi on 1 ja 4, niinpä 4 tulee alemmalle riville.

1	7
2	4

Näin jatkaen päädyin taulukkoon

1	7	5	6
2	4	3	8

Laskin kuinka monta osallistujaa voi tällä tavoin järjestettynä osallistua haluamiinsa työpajoihin ja sain tulokseksi 98. Kokeilin muutamalla muulla eri tavalla ja en keksinyt parempaa valintaa.

Mieltäni jäi kuitenkin vaivaamaan, että jos sittenkin olisi jokin toinen kombinaatio, jossa saisi työpajat sopimaan suuremmalle osallistujamäärälle.

lukumäärän laskeminen

Päätinpä siis alkaa koodaamaan. Ensin laskin eri vaihtoehtojen lukumäärän. Samalla hahmottelin ohjelmaa päässäni. Jos raa’alla voimalla tekisi jokaisen mahdollisen ”lukujärjestyksen”, niin niitä tulisi olemaan 8! = 40320. Toki koneella laskien tuo onnistunee nopeasti, mutta ohjelmoidessa saa ja tulee käyttää myös järkeä. 

Loppujen lopuksihan on sama missä järjestyksessä kumpikin rivi on. Ensimmäisen rivin työpajat voivat olla jälkimmäisenä ja toisen rivin ensimmäisenä. Toisaalta ensimmäisen rivin jäsenet voivat olla missä järjestyksessä tahansa. Tällä tavoin ajatellen jos valitaan ensin kaikki mahdolliset neljän mittaiset kombinaatiot, niin näitä tulee nCr(8, 4) = 70 kappaletta ja jos jokaiseen liitetään jäljellä olevista luvuista permutaatiot joita on 4! = 24, niin eri vaihtoehtoja tulee olemaan 70*24 = 1680 kappaletta.

python koodin eka suunnitelma

Tein mielessäni ja paperilla suunnitelman Python ohjelmasta.

• tuota vaihtoehdot
  • luo permutaatiot ekaksi riviksi taulukossa
  • määritä jäljelle jäävä nelikko joukko-opillisena erotuksena 
  • luo kombinaatiot alemmaksi riviksi
  • yhdistä yhdeksi listaksi
• määrät listaksi
• luo summa muuttuja
• laske määrät summaan
  • tähän tulee hankala if-lause
• luo tuloslista

Avasin Anaconda/Spyder-ohjelmoitiympäristön. Googlettelin aika paljon, jotta löysin tarvittavat apuohjelmat ja komennot, mutta muutamassa tunnissa ohjelma tuotti 1680 tulosta, joiden avulla pystyi valitsemaan parhaat aikataulut. Hankalin vaihe oli keksiä tarvittava if-lause, jonka avulla sai pääteltyä, pääseekö molempiin valitsemiinsa ohjelmiin. Alla on kyseinen for-silmukka, jolla varsinainen lasku suoritettiin. 

for j in range(1680):
    for li in maarat:
        if(((li[0]==0 or (li[0] in listojenlista[j][0])) and (li[0]==0 or (li[1] in listojenlista[j][1]))) or ((li[0]==0 or (li[1] in listojenlista[j][0])) and (li[0]==0 or (li[0] in listojenlista[j][1]))) ):
        summa[j]+=li[2]

Oma alkuperäinen kynällä ja paperilla tuotettu aikatauluni oli tasapisteissä parhaana. Niinpä lähetin eri vaihtoehtojen lukumäärät Jussille. Tehtävä suoritettu.

aivotoimintaa

Jotenkin mieleeni jäi kaihertamaan, että olisi tuon voinut tehdä elegantimminkin. Pari päivää myöhemmin illalla, aloin pohdiskelemaan ongelmaa ja vilkaisin tuottamaani koodia. Ajattelin, että tuo if-lausehirvitys pitäisi sieventää nätimmäksi ihan harjoituksen vuoksi. Mutta sitten telkkarista tuli jotain tärkeää ja unohdin asian. Seuraavana yönä heräsin ja tajusin, että koko jutun voi tehdä paljon helpommin. 

Aikataulunhan määrää nuo ensimmäisen rivin luvut. Toisella rivillä ovat ne luvut, jotka eivät ole ensimmäisellä rivillä. Näin tutkittavia listoja tulee olemaan vain 70 kappaletta. Kirjoitin ajatukseni muistiin aamulla, mutta en palannut asiaan, kun oli kaikkia muita kiireitä, pitäähän opettajan käydä koululla opettamassa. Pari päivää myöhemmin aamusuihkussa oivalsin yksinkertaisemman tavan, miten if-lause kannattaa kirjoittaa. Ihmisen aivot toimivat kummallisesti.

lopullinen koodi

Näytän alla lopullisen koodin ilman kommentointia, kommentoin rivejä koodin lopussa.

rivit 1-5: Spyderin tuottamaa metatietoa

rivi 7: Goolettamalla löysin tiedon, että kombinaatiot saa tuotettua itertools-kirjaston combinations funktiolla.

rivi 9: range(1,9,1) tuottaa listan [1, 2, …, 8], combinations(range(1,9,1),4) tuottaa näistä listan, jossa ovat kaikki 70 kombinaatiota tyyliin [(1, 2, 3, 4), (1, 2, 3, 5), …, (4, 6, 7, 8), (5, 6, 7, 8)].

rivi 10: map(list, ekattuplet) muuntaa monikot (tuplet) (1, 2, 3, 4) listoiksi. Combinations-komennon jäljiltä edellä esitetty lista on tyypiltään iterable (mitähän tämä on suomeksi), se muuttuu todelliseksi listaksi tyyliin [[1, 2, 3, 4], …, [5, 6, 7, 8]] list-funktiolla. Map on saman tyyppinen komento kuin GeoGebran Zip, sillä saa toistettua komennon syötelistan jokaiselle alkiolle. Koodin olisi saanut toimimaan, vaikka listan alkiot olisivat olleet monikkoja, mutta halusin testata map-komentoa :o)

rivi 11-14 Valinnat ja vastaavat määrät, kuten luvussa ”Ongelman kuvailu” on esitetty. Kenoviiva katkaisee rivin.

rivit 16-18: Luodaan summa-lista = [0, 0, 0, …0]. Sinne kerrytetään ekatlistan alkioihin sopivien osallistujien lukumäärien summat.

rivit 20-21: Sisäkkäiset silmukat, jossa käydään läpi jokainen ekatlistan alkio ja lasketaan niille kullekin, miten maaratlistan valinnat sopivat.

rivi 22-23: Jos maarat-listassa on 0, niin valinta kelpaa, lisätään osallistujien määrä summaan.

rivi 24-27: Varsinainen ehtorivi. Tässä selvitetään, onko vain jompikumpi valinnoista ekassa listassa. Ehtolause on ehkä hieman paremmin luettavissa, jos sen rivittää eri riveille

rivit 29-31: Yhdistetään ekatlistan järjestykset ja niitä vastaavat summat yhdeksi, jotta ne saa järjestettyä suuruusjärjestykseen. Metodi append lisää listan perään alkioita.

rivi 33: Järjestetään tuloslista summien mukaiseen järjestykseen.

rivit 35-36: Tulostetaan lopputulos.

Koodin tuottama lopputulos on tämän tarinan lopussa.

jatkopohdintaa

Tällaiset pienet ongelmat pitävät ainakin minun aivoni virkeinä. Tätä kirjoitettaessa tuli mieleen, parikin uutta pohdinnan aihetta. Mitä jos kaikki 148 osallistujaa olisivat tehneet valintansa satunnaisesti, mikä tällöin olisi ollut parhaan aikataulun osallistujien lukumäärä ja vastaavasti heikoimman. Pitänee tehdä simulointi tai sitten yrittää laskea todennäköisyyslaskennan avulla.

Lähteet

Itertoolsin komennot, combinations https://docs.python.org/2/library/itertools.html

Map-komento https://docs.python.org/3/library/functions.html#map

Hyvät esimerkit Mapistä https://www.w3schools.com/python/ref_func_map.asp

Sorting How to https://docs.python.org/3/howto/sorting.html

Koodi Replissä https://repl.it/@MikkoRahikka/jussinongelma#main.py

Ohjelman tuotos

([1, 3, 7, 8], 98)

([1, 5, 6, 7], 98)

([2, 3, 4, 8], 98)

([2, 4, 5, 6], 98)

([1, 2, 5, 6], 96)

([1, 5, 7, 8], 96)

([2, 3, 4, 6], 96)

([3, 4, 7, 8], 96)

([1, 6, 7, 8], 95)

([2, 3, 4, 5], 95)

([1, 3, 4, 8], 93)

([1, 3, 5, 7], 93)

([1, 5, 6, 8], 93)

([2, 3, 4, 7], 93)

([2, 4, 6, 8], 93)

([2, 5, 6, 7], 93)

([1, 3, 6, 7], 92)

([2, 4, 5, 8], 92)

([1, 3, 6, 8], 91)

([1, 4, 7, 8], 91)

([2, 3, 5, 6], 91)

([2, 4, 5, 7], 91)

([1, 3, 5, 6], 90)

([1, 4, 6, 8], 90)

([2, 3, 5, 7], 90)

([2, 4, 7, 8], 90)

([1, 2, 3, 5], 89)

([1, 4, 5, 6], 89)

([2, 3, 7, 8], 89)

([4, 6, 7, 8], 89)

([1, 2, 5, 8], 88)

([1, 3, 4, 7], 88)

([1, 3, 5, 8], 88)

([2, 4, 6, 7], 88)

([2, 5, 6, 8], 88)

([3, 4, 6, 7], 88)

([1, 3, 4, 6], 87)

([1, 4, 5, 8], 87)

([2, 3, 6, 7], 87)

([2, 5, 7, 8], 87)

([1, 2, 3, 6], 86)

([1, 2, 3, 8], 86)

([1, 4, 5, 7], 86)

([2, 3, 6, 8], 86)

([4, 5, 6, 7], 86)

([4, 5, 7, 8], 86)

([1, 2, 6, 8], 85)

([1, 4, 6, 7], 85)

([2, 3, 5, 8], 85)

([3, 4, 5, 7], 85)

([1, 3, 4, 5], 84)

([2, 6, 7, 8], 84)

([1, 2, 4, 5], 70)

([3, 6, 7, 8], 70)

([1, 2, 3, 4], 68)

([5, 6, 7, 8], 68)

([1, 2, 4, 6], 67)

([1, 2, 4, 8], 67)

([1, 2, 5, 7], 67)

([3, 4, 6, 8], 67)

([3, 5, 6, 7], 67)

([3, 5, 7, 8], 67)

([1, 2, 3, 7], 61)

([4, 5, 6, 8], 61)

([1, 2, 6, 7], 60)

([1, 2, 7, 8], 60)

([3, 4, 5, 6], 60)

([3, 4, 5, 8], 60)

([1, 2, 4, 7], 36)

([3, 5, 6, 8], 36)