Re: Pieni kesäpähkinä 2

[vastaus aiempaan viestiin]

Viime viestissäni totesin mm.
> Marjut ratkaisi tehtävän.
...
> Marjutin ratkaisu ei kuitenkaan ole mielestäni yksinkertaisin.
> On siis sijaa vielä toisellekin ratkaisijalle ja luvassa edelleen
> mittaamaton määrä kunniaa!

Koska viikon sisällä ei muita ehdotuksia ole ilmaantunut,
kerron nyt, miten tehtävä ratkeaa Survolla helpoiten.
Alku on sama kuin Marjutilla eli luodaan riittävän tilavaan
(esim. REDIM 60000,400) toimituskenttään luvun 190 kaikki
sellaiset partitiot, jotka koostuvat "osista" 1,2,5,10,20,50
eli aktivoidaan

COMB P,CUR+1 / P=PARTITIONS,190  PARTS=1,2,5,10,20,50

Tällöin saadaan peräti 55862 ositusta, joista useimmat eivät täytä
ehtoa "korkeintaan 5 kpl. kutakin lajia" vaan lista esim. alkaa
puhtaalla ykkösrivillä
1 1 1 1 1 1 1 ... (190 kpl).

Tehtävänä on karsia turhat partitiot.
Marjut teki tämän muuntamalla koko listan datatiedostoksi. Käyttämällä
mm. toistuvasti VARSTAT-komentoa hän sai näin oikean ratkaisun
tyylikkäästi.

Kelvottomat vaihtoehdot saa pois kuitenkin helposti suoraan toimitus-
kentästä aktivoimalla listan yläpuolella seuraavat viisi LINEDEL-
komentoa:

LINEDEL CUR+1,END,"1 1 1 1 1 1 "
LINEDEL CUR+1,END,"2 2 2 2 2 2 "
LINEDEL CUR+1,END,"5 5 5 5 5 5 "
LINEDEL CUR+1,END,"10 10 10 10 10 10"
LINEDEL CUR+1,END,"20 20 20 20 20 20"

eli tämä on tarkoittamani yksinkertaisin ratkaisu.
Nämä komennot poistavat kaikki ne rivit, joissa jokin kolikko/seteli
esiintyy kuudesti tai useammin.
/KUNNIAA Survolle :)

                   * * *

Yhdistelmä COMB+LINEDEL on kätevä monissa muissakin kombinatoorisissa
ongelmissa, joissa esiintyy rajoituksia.

Esimerkki:
Muodosta sellaiset numeroiden 1,2,3,4,5,6,7,8 permutaatiot, joissa
peräkkäiset numerot eivät esiinny peräkkäin.
Siis esim.
1 3 2 4 6 5 8 7  ja  8 7 6 5 4 3 2 1 ovat sallittuja, mutta
1 3 2 4 6 5 7 8  ja  8 7 5 6 4 3 1 2 eivät.

Permutaatioiden kokonaismäärä on 8! eli fact(8)=40320.
Ne listataan esim. 41000-riviseen toimituskenttään komennolla
.......................................................................
COMB P,CUR+1 / P=PERMUTATIONS,8
Permutations of 8 elements: N[P]=40320
1 2 3 4 5 6 7 8
1 2 3 4 5 6 8 7
1 2 3 4 5 7 6 8
...
.......................................................................
Nyt turhat rivit karsitaan listan eteen asetetuilla LINEDEL-komennoilla

LINEDEL CUR+1,END,"1 2"
LINEDEL CUR+1,END,"2 3"
LINEDEL CUR+1,END,"3 4"
LINEDEL CUR+1,END,"4 5"
LINEDEL CUR+1,END,"5 6"
LINEDEL CUR+1,END,"6 7"
LINEDEL CUR+1,END,"7 8"

jolloin listan alku- ja loppupää näyttävät seuraavilta:
1 3 2 4 6 5 8 7
1 3 2 4 6 8 5 7
1 3 2 4 6 8 7 5
1 3 2 4 7 5 8 6
...
8 7 6 5 3 2 4 1
8 7 6 5 4 1 3 2
8 7 6 5 4 2 1 3
8 7 6 5 4 3 2 1

Laskemalla listan rivien lukumäärä todetaan, että
sallittuja permutaatioita on 16687 kpl.

Tässä tarkasteltiin tapausta n=8. Arvoilla n=1,2,...,8
sallittujen permutaatioden lukumääriksi P(n) tulevat

n     1 2 3  4  5   6    7     8
P(n)  1 1 3 11 53 309 2119 16687

Mikä mahtaa olla P(n):n yleinen lauseke? Tätä lukujonoa ei
Reijo Sundin Survo-ohjelma NTERM (ainakaan vielä) tunnista.
Apua löytyy sivuilta

http://www.research.att.com/~njas/sequences/index.html 

joille Neil Sloane ja kumppanit ovat keränneet 1960-luvulta
lähtien kokonaislukujonojen tietopankkia.

Kun P(n)-jonon edellä olevat termit annetaan siellä herätteeksi,
syntyy liuta vastauksia, joista tärkein on rekursiokaava

P(n) = (n-2)*P(n-2) + (n-1)*P(n-1), P(1)=P(2)=1.

Sääntö on yllättävän yksinkertainen. Esim. 6*309+7*2119=16687
(kts. ylläolevaa taulukkoa ja kokeile kosketuslaskennalla).
Mitään suoraa lauseketta ei tunneta.

On hieman yllättävää, että juuri tämä tulkinta on havaittu ilmeisesti
vasta lokakuussa 2001 (Len Smiley). Jo aikaisemmin on todettu saman
lukujonon tulevan esiin eräissä muissa (kombinatoorisissa) tehtävissä.

-Seppo

Luettelo keskustelunaiheista

Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!