Noppaa heitetään 20 kertaa. Tuloksista muodostetaan 20-numeroinen luku liittämällä numerot yhteen, esim. 24312534121134563421. Mikä on todennäköisyys, että saatu 20-numeroinen luku tulkittuna merkkijonoksi sisältää ainakin yhden seuraavista osamerkkijonoista, eli luvusta löytyy seuraavat numerot peräkkäin:
123456
112233
445566
111222
333444
555666
111111
222222
333333
444444
555555
666666
Yritin inkluusio-ekskluusioperiaatteetta, mutta sekosin laskuissani.
Vaikea kombinatoriikan tehtävä
enosaatätä
36
578
Vastaukset
- Kanootti3
On tosiaan aika hankala. Lähdin tietokoneavusteisesti ratkomaan. Tein Markovin ketjun, jossa on tiloina kaikki noiden osamerkkijonojen alukkeet, näitä tuli 46kpl:
prefixes = ['1', '11', '111', '1111', '11111', '1112', '11122', '112', '1122', '11223', '12', '123', '1234', '12345', '2', '22', '222', '2222', '22222', '3', '33', '333', '3333', '33333', '3334', '33344', '4', '44', '444', '4444', '44444', '445', '4455', '44556', '5', '55', '555', '5555', '55555', '5556', '55566', '6', '66', '666', '6666', '66666' ]
ja lisäksi tyhjä lähtötila "" sekä absorboiva tila, johon päädyttäessä jokin halutuista osamerkkijonoista on tullut ja sitten ketju jää tähän tilaan. Siirtymätodennäköisyydet katsoin siten, että jokaiseen alukkeeseen (ja tyhjään lähtötilaan) lisätään vuorollaan kukin merkki '1', '2',..,'6' ja sitten
JOKO:
Jos näin saatu merkkijono on joku halutuista osamerkkijonoista lisätään 1/6 siirtymää absorboivaan tilaan
TAI:
Katsotaan mikä on pisin aluke joka näin saadun merkkijonon lopusta voidaan lukea, ja lisätään 1/6 siirtymää tähän kyseiseen alukkeeseen.
Näin saadaan 48x48 siirtymämatriisi Q ja kysytty todennäköisyys on tn. että ketju on 20 siirtymän jälkeen absorboivassa tilassa eli matriisin Q^20 alkio vasemmassa alanurkassa [48][1] (kun lähtötila "" on asetettu ensimmäiseksi tilaksi ja absorboiva viimeiseksi).
Se on likimain 0,0035471102445.
Simulointi tukee tätä tulosta, joten luullakseni tuo ketjun muodostaminen meni oikein. Tiedä sitten tarkasta arvosta. Senkin kyllä saisi, kun käyttäisi tarkkoja rationaalilukuja matriisissa, mutta minulla ei ollut sellaista kirjastoa valmiina.- Anonyymi
Miksi on riittävää tutkia 46 tilaa? Minusta osamerkkijonon alkuja on 59 kpl:
finalstates = ['123456',
'112233',
'445566',
'111222',
'333444',
'555666',
'111111',
'222222',
'333333',
'444444',
'555555',
'666666']
print(finalstates)
states = []
for j in range(len(finalstates)):
for i in range(len(finalstates[j]) 1):
states.append(finalstates[j][:i])
states = list(set(states))
print(len(states))
tulostaa 59 - Anonyymi
Anonyymi kirjoitti:
Miksi on riittävää tutkia 46 tilaa? Minusta osamerkkijonon alkuja on 59 kpl:
finalstates = ['123456',
'112233',
'445566',
'111222',
'333444',
'555666',
'111111',
'222222',
'333333',
'444444',
'555555',
'666666']
print(finalstates)
states = []
for j in range(len(finalstates)):
for i in range(len(finalstates[j]) 1):
states.append(finalstates[j][:i])
states = list(set(states))
print(len(states))
tulostaa 59Mitään kokonaista finalstatea ei tarvitse ottaa tilaksi, vaan ne voi yhdistää yhdeksi "jokin final on tullut". Eli jätetään vain 1 pois riviltä
for i in range(len(finalstates[j]) 1):
Tulee 47 ja sitten lisätään se yksi absorboiva tila, niin saadaan tuo mainittu 48.
(Niissä 46 "alukkeessa" ei oltu taidettu laskea mukaan sitä tyhjää tilaa.)
- 3kj46h
Kysyttyjä yhdistelmiä on 12 kpl. Todennäköisyys saada nopanheitossa jokin tietty kuuden numeron mittainen yhdistelmä kuudella peräkkäisellä heitolla on (1/6)^6. Kukin kuuden numeron mittainen yhdistelmä kahdenkymmenen heiton sarjassa voi saada alkunsa heitoilla 1-15 eli alkusijainti koko merkkijonossa voi olla mikä tahansa positioista 1-15.
Todennäköisyys, että jokin näistä kahdestatoista yhdistelmästä alkaa ensimmäisestä positiosta = 12* (1/6)^6. Sama pätee positioiden 2-15 suhteen, joten mahdollisia positioita merkkijonon sijainnille on 15 kpl. Koska nämä kaikki ovat toisistaan riippumatomia, kysytty tod.näk = 15*12*(1/6)^6 = 0,003858024.- pedantikko
"Koska nämä kaikki ovat toisistaan riippumatomia,"
Mutta kun eivät ole. - 3kj46h
pedantikko kirjoitti:
"Koska nämä kaikki ovat toisistaan riippumatomia,"
Mutta kun eivät ole.Ovat.
- hieman_ajattelua
Jos olisi yksisivuinen noppa (joka heitolla luku 1) ja kysyttäisiin millä todennäköisyydellä n pituisessa jonossa on m pituinen jono pelkkää ykköstä niin ilmiselvästi vastaus olisi 1 kun m<=n. Sinun laskukaava antaisi kuitenkin esimerkiksi tapauksessa n=7 ja m=6 tulokseksi 2 joka on selvästi virheellinen tulos.
- pedantikko
3kj46h kirjoitti:
Ovat.
Olkoon kuusi ensimmäistä vaikkapa 123451. Sinun riippumattomuushypoteesistasi seuraa, että todennäköisyys positiosta kaksi alkavan yhdistelmän osumisesta olisi myös 12* (1/6)^6. On kuitenkin selviö, että tn on nolla, josten perättäiset sajat eivät ole riippumattomia,
- Kanootti3
Laskin nyt kokonaisluvuilla ja sain seuraavat arvot n:n pituisille merkkijonoille (tn. saadaan jakamalla 6^n:llä) n=1,2,3....
[0, 0, 0, 0, 0, 12, 138, 1224, 9714, 72498, 520268, 3633165, 24867610L, 167613033L, 1116096436L, 7358932150L, 48126778830L, 312594178184L, 2018532445956L, 12968797058271L, 82957185658624L,...] (L perässä tarkoittaa vain että luku on long-tyyppiä).
Kahdeskymmenes on 12968797058271, joten kysytty tn. on
12968797058271 / 6^20
= 480325816973/ 135413275557888
= 0,003547110244502319 - Kanootti3
Tein Python-koodin, jolla voi ratkaista vastaavan tehtävän halutuille osamerkkijonoille (ja käytettäville symboleille ja sananpituudelle):
http://tpcg.io/GkDnZI
Käyttöohje:
Viimeinen koodirivi
print(getProbSomeSeqIsSub([0,1], ["000", "111"], 7, True))
tulostaa todennäköisyyden halutuille symboleille, osamerkkijonoille, sananpituudelle (ja halutaanko tarkka rationaaliluku vai floating-point luku, aseta True tai False). Noilla arvoilla se ratkaisee kolmen putken esiintymistodennäköisyyden 7 pituisessa binäärijonossa.
Tämän muokkaamisen jälkeen paina "execute" vasemmasta ylänurkasta ja tuloksen pitäisi ilmestyä oikean puoleiseen konsoliin (sivu saattaa tietenkin olla jokaisella ehkä erinäköinen).
Koodi on melko sotkuinen mutta kyllä se näyttäisi toimivan, ainakin tuolle kolmen putki -ongelmalle (sen komplementille) antaa ihan oikeita vastauksia.
Ihan vaan, jos joku haluaa testailla :-).- Kanootti3
Yhden pituisille osajonoille ei taida tuollaiseltaan toimia, mutta näyttäisi korjutuvan, kun muuttaa kohdan (rivillä 53)
if stateStr str(i) in seqs:
paikalle
if stateStr str(i) in seqs or str(i) in seqs:
eli lisää jokaisesta tilasta siirtymä tn:ää absorboivaan tilaan jokaista yhden merkin pituista osamerkkijonoa kohti. - Kanootti3
Kanootti3 kirjoitti:
Yhden pituisille osajonoille ei taida tuollaiseltaan toimia, mutta näyttäisi korjutuvan, kun muuttaa kohdan (rivillä 53)
if stateStr str(i) in seqs:
paikalle
if stateStr str(i) in seqs or str(i) in seqs:
eli lisää jokaisesta tilasta siirtymä tn:ää absorboivaan tilaan jokaista yhden merkin pituista osamerkkijonoa kohti.Siis rivillä 50 (muuttui itsellä kun muokkasin siellä jo alkupäässäkin jotain).
- enosaatätä
Hieno tarkaisu. Täytyy opetella enemmän Pythonia ja Markovin ketjuja, jotta ymmärrän kaiken. Mutta näyttäisi toimivan!
- Kanootti3
Tajusinkin juuri, että eihän tuo algoritmi toimi kaikenlaisille osajonolistoille ollenkaan. Jos esim yksi jono on toisen alku, niin sitä ei huomata eikä mennä absorboivaan tilaan, jos ollaan "kartuttamassa" sitä pitempää osajonoa.
Voisikohan tuota korjata sillä että poistaa aluksi osajonolistasta yksi kerrallaan sellaiset jonot, joista löytyy sisältä jokin toinen osajono? - Kanootti3
Kun tilasta lisätään siirtymä tietyllä symbolilla pitää tietenkin tarkastaa saadaanko muodostettua mistään asti luettuna jokin päätösosajono. Tämä käsittelee myös "yhdenpituiset osajonot" -tapaukset. Eikä sitten tuota osajonolistan "siivoustakaan" tarvitse tehdä. Mutta antaa sen olla; hyvähän se on jos niitä saadaan karsittua pois.
Korjattu versio:
http://tpcg.io/JUVcIw
Toimineekohan tuo sitten kaikilla :-D - Kanootti3
Joo, nyt se taitaa toimia. Tein satunnaisia testejä aika paljon ja katsoin tuleeko sama tulos kuin brute-force -metodilla.
Testit mukana:
http://tpcg.io/D8cZzv
- YxVain
Todennäköisyys on 10 %
- Anonyymi
0,0001540702...
- Anonyymi
tn = 15*12*6^14/6^20 =5/6^4 = 0,00385802.....
- Anonyymi
Huomasin jo että kommenttini/ 04:28 on täyttä puppua.
- Anonyymi
Kuinka pitkä tuon merkkijonon pitää olla, jotta kysytty todennäköisyys olisi suurempi kuin 0,1?
Vinkki: Todennäköisyys on tuolloin
tn = 31837618718...4782 / 318065396940...1216
Aikaa laskentaan kului Pythonilla (PyPy) n. 18 s.453
Laskitko kaikki pituudet tuohon asti? Senhän voi tehdä puolitushaulla (aluksi tuplaa niin pitkään kunnes menee yli ja sitten lähtee hakemaan sieltä välistä). Itse sain tuon tällä tavoin ihan käsipelissä kokeilemalla (en nyt tismalleen tuplaillut ja puolitellut vaan lisäsin aluksi satasia ja silleen...)- Anonyymi
minkkilaukku kirjoitti:
453
Laskitko kaikki pituudet tuohon asti? Senhän voi tehdä puolitushaulla (aluksi tuplaa niin pitkään kunnes menee yli ja sitten lähtee hakemaan sieltä välistä). Itse sain tuon tällä tavoin ihan käsipelissä kokeilemalla (en nyt tismalleen tuplaillut ja puolitellut vaan lisäsin aluksi satasia ja silleen...)Pythonilla on helppo laskea ihan tarkasti vaikka kuinka pitkälle ilman mitään ymmärräystä matematiikan vaikeuksista ihan vaan kansakoulun lyhyen oppimäärän (4 v) tiedoilla. Riittää hallita kokonaislukujen yhteenlasku ja 10:llä jakaminen! Missään vaiheessa ei tarvita mitään merkkijonoja.
Kysehän on vain kuusinumeroisista kymmenjärjestelmän luvuista, joissa esiintyy vain numeroita 1...6. Tehdään niitä varten suoraan indeksoitava lista, jossa on jokaista lukua varten tyhjä lista.
Muodostetaan kaikki ehdot täyttävät luvut silmukassa ja suodatetaan pois 12 haettavaa lukua (111111, ...666666).
Jokaisesta näistä luvuista voidaan muodostaa 6 tai 5 lukua jakamalla luku 10:llä ja lisäämällä siihen silmukassa 100000. Haetut 12 lukua suodatetaan pois. Lisätään muodostetut 6 tai 5 lukua alkuperäisellä luvulla indeksoitavan listan alilistaan.
Kaikki tämä riittää tehdä vain kerran. Muodostetussa kaksitasoisessa listassa on kaikki tarvittava tieto. Aluksi kaikkia lukua oli vain 1 (gnk = [1]*666667). Lisätään muodostettujen lukujen lukumäärät indeksoitavaan summalistaan (gns) ja kopsataan se lopuksi uudeksi kerroinlistaksi gnk. Tätä voidaan toistaa silmukassa ikuisesti, kunnes tietokoneen muisti loppuu.
Lyhyt kertakäyttökoodi. Korvaa jokainen alaviiva (_) kahdella blankolla editorissa. Ja jälkimmäisen silmukan n:n arvo halutuksi.
No = [123456,112233,445566,111222,333444,555666,111111,222222,333333,444444,555555,666666]
gl = []
for i in range(0,666667): gl.append([])
for a in range(111111,666667):
__s = a
__for i in range(0,5):
____if s==0 or s>6: break
____s = s//10
____if s>6: continue
____if a in No: continue
____for i in range(1,7):
______b = a//10 i*10**5
______if b in No: continue
______gl[a].append(b)
gnk = [1]*666667
for n in range(7,100):
__c1 = 0
__gns = [0]*666667
__for z in range(111111,666667):
____if len(gl[z])==0: continue
____for y in gl[z]: gns[y] = gnk[z]
__for z in range(111111,666667): c1 = gns[z]
__gnk = gns[:]
__print(n,6**n - c1)
__print(n,6**n)
Tulostus (lopun printit) pitää muuttaa itselle sopiviksi ihan tarpeen mukaan. Näyttäisi toimivan ilman Pypyäkin ihan riittävän nopeasti. Aika kuluu isoilla n:n arvoilla monisatanumeroisen lukujen summaamisessa. Tulostuksesta näkee lukujen aluista halutut kohdat ihan paljain silmin. Vähän päässälaskua ja laskimella varmistus. - Anonyymi
Anonyymi kirjoitti:
Pythonilla on helppo laskea ihan tarkasti vaikka kuinka pitkälle ilman mitään ymmärräystä matematiikan vaikeuksista ihan vaan kansakoulun lyhyen oppimäärän (4 v) tiedoilla. Riittää hallita kokonaislukujen yhteenlasku ja 10:llä jakaminen! Missään vaiheessa ei tarvita mitään merkkijonoja.
Kysehän on vain kuusinumeroisista kymmenjärjestelmän luvuista, joissa esiintyy vain numeroita 1...6. Tehdään niitä varten suoraan indeksoitava lista, jossa on jokaista lukua varten tyhjä lista.
Muodostetaan kaikki ehdot täyttävät luvut silmukassa ja suodatetaan pois 12 haettavaa lukua (111111, ...666666).
Jokaisesta näistä luvuista voidaan muodostaa 6 tai 5 lukua jakamalla luku 10:llä ja lisäämällä siihen silmukassa 100000. Haetut 12 lukua suodatetaan pois. Lisätään muodostetut 6 tai 5 lukua alkuperäisellä luvulla indeksoitavan listan alilistaan.
Kaikki tämä riittää tehdä vain kerran. Muodostetussa kaksitasoisessa listassa on kaikki tarvittava tieto. Aluksi kaikkia lukua oli vain 1 (gnk = [1]*666667). Lisätään muodostettujen lukujen lukumäärät indeksoitavaan summalistaan (gns) ja kopsataan se lopuksi uudeksi kerroinlistaksi gnk. Tätä voidaan toistaa silmukassa ikuisesti, kunnes tietokoneen muisti loppuu.
Lyhyt kertakäyttökoodi. Korvaa jokainen alaviiva (_) kahdella blankolla editorissa. Ja jälkimmäisen silmukan n:n arvo halutuksi.
No = [123456,112233,445566,111222,333444,555666,111111,222222,333333,444444,555555,666666]
gl = []
for i in range(0,666667): gl.append([])
for a in range(111111,666667):
__s = a
__for i in range(0,5):
____if s==0 or s>6: break
____s = s//10
____if s>6: continue
____if a in No: continue
____for i in range(1,7):
______b = a//10 i*10**5
______if b in No: continue
______gl[a].append(b)
gnk = [1]*666667
for n in range(7,100):
__c1 = 0
__gns = [0]*666667
__for z in range(111111,666667):
____if len(gl[z])==0: continue
____for y in gl[z]: gns[y] = gnk[z]
__for z in range(111111,666667): c1 = gns[z]
__gnk = gns[:]
__print(n,6**n - c1)
__print(n,6**n)
Tulostus (lopun printit) pitää muuttaa itselle sopiviksi ihan tarpeen mukaan. Näyttäisi toimivan ilman Pypyäkin ihan riittävän nopeasti. Aika kuluu isoilla n:n arvoilla monisatanumeroisen lukujen summaamisessa. Tulostuksesta näkee lukujen aluista halutut kohdat ihan paljain silmin. Vähän päässälaskua ja laskimella varmistus.Jos yläpuolen kertoo tuhannella (1000*(6**n-c1)/6**n) , oikean kohdan löytää Python 2:llakin suoraan myös kokonaisluvuilla laskien ilman turhaa tulostusta. Muuttuu 100:ksi ensimäisen kerran. (Python 3 osaa jakaa kokonaislukuja kokonaisluvuilla ja muodostaa myös desimaaliosan ilman liukulukumuunnosta ja sen rajoitusta.)
Yli 0,5 todennäköisyys saavutetaan kun n = 2950 ja 0,6 kun n = 3898 ja 0,7 kun n = 5121 ja 0,8 kun n = 6843 ja 0,9 kun n = 9788 ja 0,95 kun n = 12733 ja 0,99 kun n = 19571.
Lopussa n kasvoi yhdellä n. 0,3 sekunnissa. Muistia kului n. 1,3 Gtavua ja aikaa n. tunti.
On tietysti täysin typerää laskea monituhatnumeroisilla kokonaisluvuilla näin turhaa laskua. Varmasti löytyisi joku toistuva jaksotus ja paljon symmetriaa, joilla laskennan saisi murto-osaan ja voisi jakaa homman useille eri ytimille. Anonyymi kirjoitti:
Pythonilla on helppo laskea ihan tarkasti vaikka kuinka pitkälle ilman mitään ymmärräystä matematiikan vaikeuksista ihan vaan kansakoulun lyhyen oppimäärän (4 v) tiedoilla. Riittää hallita kokonaislukujen yhteenlasku ja 10:llä jakaminen! Missään vaiheessa ei tarvita mitään merkkijonoja.
Kysehän on vain kuusinumeroisista kymmenjärjestelmän luvuista, joissa esiintyy vain numeroita 1...6. Tehdään niitä varten suoraan indeksoitava lista, jossa on jokaista lukua varten tyhjä lista.
Muodostetaan kaikki ehdot täyttävät luvut silmukassa ja suodatetaan pois 12 haettavaa lukua (111111, ...666666).
Jokaisesta näistä luvuista voidaan muodostaa 6 tai 5 lukua jakamalla luku 10:llä ja lisäämällä siihen silmukassa 100000. Haetut 12 lukua suodatetaan pois. Lisätään muodostetut 6 tai 5 lukua alkuperäisellä luvulla indeksoitavan listan alilistaan.
Kaikki tämä riittää tehdä vain kerran. Muodostetussa kaksitasoisessa listassa on kaikki tarvittava tieto. Aluksi kaikkia lukua oli vain 1 (gnk = [1]*666667). Lisätään muodostettujen lukujen lukumäärät indeksoitavaan summalistaan (gns) ja kopsataan se lopuksi uudeksi kerroinlistaksi gnk. Tätä voidaan toistaa silmukassa ikuisesti, kunnes tietokoneen muisti loppuu.
Lyhyt kertakäyttökoodi. Korvaa jokainen alaviiva (_) kahdella blankolla editorissa. Ja jälkimmäisen silmukan n:n arvo halutuksi.
No = [123456,112233,445566,111222,333444,555666,111111,222222,333333,444444,555555,666666]
gl = []
for i in range(0,666667): gl.append([])
for a in range(111111,666667):
__s = a
__for i in range(0,5):
____if s==0 or s>6: break
____s = s//10
____if s>6: continue
____if a in No: continue
____for i in range(1,7):
______b = a//10 i*10**5
______if b in No: continue
______gl[a].append(b)
gnk = [1]*666667
for n in range(7,100):
__c1 = 0
__gns = [0]*666667
__for z in range(111111,666667):
____if len(gl[z])==0: continue
____for y in gl[z]: gns[y] = gnk[z]
__for z in range(111111,666667): c1 = gns[z]
__gnk = gns[:]
__print(n,6**n - c1)
__print(n,6**n)
Tulostus (lopun printit) pitää muuttaa itselle sopiviksi ihan tarpeen mukaan. Näyttäisi toimivan ilman Pypyäkin ihan riittävän nopeasti. Aika kuluu isoilla n:n arvoilla monisatanumeroisen lukujen summaamisessa. Tulostuksesta näkee lukujen aluista halutut kohdat ihan paljain silmin. Vähän päässälaskua ja laskimella varmistus.Mielenkiintoinen strategia, joo sen voi noinkin tosiaan. En tiedä tuliko mulla kopioidessa virhe vai miksi minulla tuo koodi ei toiminut (gl jäi tyhjäksi, loppuosa toimi kyllä). Mistä nuo merkit , muuten tuli riville
____if s==0 or s>6: break
No sain tuon toimimaan itselläni kun muokkasin vähän sitä koodia. Saanko ehdottaa tällaista versiota:
https://repl.it/@minkkilaukku2/subseq2
Siinä tarkastellaan vain lukuja jotka koostuu 1-6:sta eikä kaikkia kymmenjärjestämän lukuja väliltä 111111-6666666 ja käytetään dict:iä (onkohan tämä miten paljon listaa hitaampi/epätehokkaampi?)- Anonyymi
minkkilaukku kirjoitti:
Mielenkiintoinen strategia, joo sen voi noinkin tosiaan. En tiedä tuliko mulla kopioidessa virhe vai miksi minulla tuo koodi ei toiminut (gl jäi tyhjäksi, loppuosa toimi kyllä). Mistä nuo merkit , muuten tuli riville
____if s==0 or s>6: break
No sain tuon toimimaan itselläni kun muokkasin vähän sitä koodia. Saanko ehdottaa tällaista versiota:
https://repl.it/@minkkilaukku2/subseq2
Siinä tarkastellaan vain lukuja jotka koostuu 1-6:sta eikä kaikkia kymmenjärjestämän lukuja väliltä 111111-6666666 ja käytetään dict:iä (onkohan tämä miten paljon listaa hitaampi/epätehokkaampi?)Kokeilin eilen ja nyt uudstaan. Kyllä tuo koodi toimii ihan copy-pastella _ replace sekä Python 2:lla ja 3:lla ja Pypyillä. Pitää tietysti poistaa ne ihme-merkit. Kirjoitin tuon rivin käsin editoriini uudestaan ilman mitään virhepainalluksia, tallensin tiedoston ja kopsasin tuon rivin uudestaan tänne. Katsotaan sainko tehtyä nuo erikoismerkit vahingossa jotenkin vai muodostaako Suomi24:n editori ne.
____if s==0 or s>6: break
Teen tälläiset kertakäyttökoodit aina ilman ilman (hidastavia) kirjasto-ohjelmia, jotta voisi vapaasti käyttää eri Pypy-versioita. Nykyisin monet kirjasto-ohjelmat alkavat jo toimia Pypyilläkin, mutta niiden Pypy-versiot on ladattava erikseen tietokoneelle. Nyt yli 99,9 % ajasta kuluu yli 1000...15000 -numeroisten lukujen typerään ynnäämisessä, joten koodin pieni optimointi ei vaikuta mitenkään lopputulokseen. Listoja tarkkailemalla löytyy symmetriota, joita hyödyntäen laskenta-ajan saisi murto-osaan muutaman päivän työllä.
Jos haluaa nopeutta isoilla n:n arvoilla, niin sitä käyttämällä gmpy2:n liukuluja tai taskulaskinta. Riittää laskea c1:n arvo (21853993454719232) kun n=21. Sen jälkeen kasvuvauhti (k) on käytännössä ihan vakioita. k = mpfr(5.998587939741517).
c1 = mpfr(21853993454719232*k**(n-21))
Esim. jos n=19571, niin todennäköisyys on 0,9900012309059978. Taskulaskimellakin laskettuna. - Anonyymi
Anonyymi kirjoitti:
Kokeilin eilen ja nyt uudstaan. Kyllä tuo koodi toimii ihan copy-pastella _ replace sekä Python 2:lla ja 3:lla ja Pypyillä. Pitää tietysti poistaa ne ihme-merkit. Kirjoitin tuon rivin käsin editoriini uudestaan ilman mitään virhepainalluksia, tallensin tiedoston ja kopsasin tuon rivin uudestaan tänne. Katsotaan sainko tehtyä nuo erikoismerkit vahingossa jotenkin vai muodostaako Suomi24:n editori ne.
____if s==0 or s>6: break
Teen tälläiset kertakäyttökoodit aina ilman ilman (hidastavia) kirjasto-ohjelmia, jotta voisi vapaasti käyttää eri Pypy-versioita. Nykyisin monet kirjasto-ohjelmat alkavat jo toimia Pypyilläkin, mutta niiden Pypy-versiot on ladattava erikseen tietokoneelle. Nyt yli 99,9 % ajasta kuluu yli 1000...15000 -numeroisten lukujen typerään ynnäämisessä, joten koodin pieni optimointi ei vaikuta mitenkään lopputulokseen. Listoja tarkkailemalla löytyy symmetriota, joita hyödyntäen laskenta-ajan saisi murto-osaan muutaman päivän työllä.
Jos haluaa nopeutta isoilla n:n arvoilla, niin sitä käyttämällä gmpy2:n liukuluja tai taskulaskinta. Riittää laskea c1:n arvo (21853993454719232) kun n=21. Sen jälkeen kasvuvauhti (k) on käytännössä ihan vakioita. k = mpfr(5.998587939741517).
c1 = mpfr(21853993454719232*k**(n-21))
Esim. jos n=19571, niin todennäköisyys on 0,9900012309059978. Taskulaskimellakin laskettuna.Nyt tuo rivi kopioitui oikein, eli olin vahingossa painanut editoidessa tuolla rivillä joitain erikoisnäppäimiä. Todennäköisesti vasta Suomi24:n editorissa kopioinnin jälkeen, sillä Python tai Pypy ei noita näkymättömiä virhemerkkejä havainneet. Copy-paste ei tee virheitä.
- Anonyymi
minkkilaukku kirjoitti:
Mielenkiintoinen strategia, joo sen voi noinkin tosiaan. En tiedä tuliko mulla kopioidessa virhe vai miksi minulla tuo koodi ei toiminut (gl jäi tyhjäksi, loppuosa toimi kyllä). Mistä nuo merkit , muuten tuli riville
____if s==0 or s>6: break
No sain tuon toimimaan itselläni kun muokkasin vähän sitä koodia. Saanko ehdottaa tällaista versiota:
https://repl.it/@minkkilaukku2/subseq2
Siinä tarkastellaan vain lukuja jotka koostuu 1-6:sta eikä kaikkia kymmenjärjestämän lukuja väliltä 111111-6666666 ja käytetään dict:iä (onkohan tämä miten paljon listaa hitaampi/epätehokkaampi?)Kopsasin sen gl:n alustuksen alkuperäisestä tiedostosta uudestaan mitään muuttamatta.
gl = []
for i in range(0,666667): gl.append([])
Mikähän tuossa voisi olla väärin? Pitäisi kyllä toimia Python 2:lla ja 3:lla ongelmitta. Jos ei toimi, jossakin on joku näkymätön piilomerkki. Kokeile noita kahta riviä ihan puhtaassa ympäristössä. Jos ei toimi, kirjoita käsin uudestaan muutaman merkin erissä. Kyllä se piilomerkki jossakin vaiheessa häviää!
Minulla on vanhat Python 2.7.12 ja 3.5.2 versiot. Anonyymi kirjoitti:
Kopsasin sen gl:n alustuksen alkuperäisestä tiedostosta uudestaan mitään muuttamatta.
gl = []
for i in range(0,666667): gl.append([])
Mikähän tuossa voisi olla väärin? Pitäisi kyllä toimia Python 2:lla ja 3:lla ongelmitta. Jos ei toimi, jossakin on joku näkymätön piilomerkki. Kokeile noita kahta riviä ihan puhtaassa ympäristössä. Jos ei toimi, kirjoita käsin uudestaan muutaman merkin erissä. Kyllä se piilomerkki jossakin vaiheessa häviää!
Minulla on vanhat Python 2.7.12 ja 3.5.2 versiot.Siis jokainen gl[i] jää tyhjäksi tarkoitin. Kokeilin myös täällä (Python 3.8.1): https://repl.it/@minkkilaukku2/subseq3 ja sama virhe toistuu.
Hetkonen, eikös tuo johdu siitä että, kun
for a in range(111111,666667):
s = a #puuttuuko tästä jotain?
for i in range(0,5):
if s==0 or s>6: break
asetetaan s = a niin tuohan breikkaa aina kun a on tuolta väliltä. Pitäisikö s:n olla a:n ensimmäinen numero (ja sitten luupissa i:s numero tai vastaavaa?
No mutta kuitenkin kyllähän tuo toimii, kun gl:n saa oikein muodostettua. Tulkitsenkohan oikein kun ajattelen, että se on niinkuin Markovin ketju, joka pitää tilana merkkijonon viimeisintä kuutta merkkiä?minkkilaukku kirjoitti:
Siis jokainen gl[i] jää tyhjäksi tarkoitin. Kokeilin myös täällä (Python 3.8.1): https://repl.it/@minkkilaukku2/subseq3 ja sama virhe toistuu.
Hetkonen, eikös tuo johdu siitä että, kun
for a in range(111111,666667):
s = a #puuttuuko tästä jotain?
for i in range(0,5):
if s==0 or s>6: break
asetetaan s = a niin tuohan breikkaa aina kun a on tuolta väliltä. Pitäisikö s:n olla a:n ensimmäinen numero (ja sitten luupissa i:s numero tai vastaavaa?
No mutta kuitenkin kyllähän tuo toimii, kun gl:n saa oikein muodostettua. Tulkitsenkohan oikein kun ajattelen, että se on niinkuin Markovin ketju, joka pitää tilana merkkijonon viimeisintä kuutta merkkiä?Aaa, nyt tajusin: se pitää olla
s (prosentti) 10 jne.
sillähän ne erikoismerkit tuli
ja lisäksi luupin for i in range(0,5): sisällä on vaan kaksi riviä. (Korjasin ne nyt itselleni tuonne replittiinkin.)
Keksin approksimatiivisen kaavan
1 - a*b^n
missä
a = 1.0011546714408708
b = 0.9997646566235854
Sain tämän diagonalisoimalla siirtymämatriisin ja ottamalla vain kaksi itseisarvoltaan suurinta ominaisarvoa mukaan. Siihen voi ottaa lisääkin ja tietysti jos kaikki ottaa niin saa itse asiassa tarkan kaavan. Jos ottaa ei-reaalisia ominaisarvoja, niin lausekkeesta pitää sitten ottaa reaaliosa. Tai siinä käy varmaan silleen, että jos ottaa myös konjugaatti-ominaisarvon (näissä pareissahan ne tulee, koska karakteristinen polynomi on reaalikertoiminen), niin imaginaariset osat kumoutuu laskuissa.
En mene kyllä vannomaan miten tarkat nuo arvot on. Jotain se Sage herjasi, että ominaisvektoreista mudostetun matriisin konditio-luku on pieni ja laskuissa saattaa esiintyä epätarkkuutta (onneksi koko matriisia ei tarvitse kääntää vaan inverssin viimeinen sarake riittää, jotta saadaan haluttu elementti laskettua diagolisoinnista).
Koodini on täällä:
https://github.com/minkkilaukku/sub-sequence-markov/blob/master/subseq_probs2.py
Muodostan siirtymämatriisin tekemällä ensin annetuista osamerkkijonoista Trie-puun ( https://en.wikipedia.org/wiki/Trie ) ja sen avulla katsotaan mihin kustakin tilasta pudotaan takaisin.- Anonyymi
Nyt kun kaikki toimii hyvin, niin laske kysytty todennäköisyys n:n arvolla 20, jos annetut 12 kuusinumeroista lukua ovat satunnaisia ja erisuuria (ja niissä on vain numeroita (1,2,3,4,5,6)).
Sain todennäköisyydeksi 0,0038511.
Toistin 5000 kertaa. Anonyymi kirjoitti:
Nyt kun kaikki toimii hyvin, niin laske kysytty todennäköisyys n:n arvolla 20, jos annetut 12 kuusinumeroista lukua ovat satunnaisia ja erisuuria (ja niissä on vain numeroita (1,2,3,4,5,6)).
Sain todennäköisyydeksi 0,0038511.
Toistin 5000 kertaa.Tässä versiossa varmaan riippumattomuusoletus tulee pätemään ja vastaus olisi
15*12*6^14/6^20 =5/6^4 = 0,00385802- Anonyymi
minkkilaukku kirjoitti:
Tässä versiossa varmaan riippumattomuusoletus tulee pätemään ja vastaus olisi
15*12*6^14/6^20 =5/6^4 = 0,00385802Vastaus on simuloimalla n. 0,00385107.
Nopea simuloida, jos muuntaa nuo numerot ensin kuusijärjetelmään eli nopassa numerot (0,1,2,3,4,5) ja näin muodostetun luvun arvon kymmenjärjestelmään. Mikään ei muutu matemaattisesti ajatellen. Riittää siis käydä läpi lukualuetta 0...6^6-1 (0...46655). Seuravat luvut saadaan jakamalla tuo (kymmenjärjestelmän) luvut 6:lla ja ja lisäämällä niihin 6^5. Kaikki yksinkertaistuu ja ohjelma lyhenee ja nopeutuu.
Alkuperäisen kysymyksen luvut olisivat siis
Nl = [1865, 266, 28259, 43, 18705, 37367, 0, 9331, 18662, 27993, 37324, 46655]
Satunnainen lista saadaan nopeasti suoraan randint(0,46655):lla ja if not in Nl:.
Riittää laskea kokonaismäärä vain n:n arvolla 20 ja summata noita arvoja. Tutulostuksessa summan voi jakaa toistojen 10000:n tai 100000:n määrällä päässälaskuna. Ja ohjelmaa voi ajaa useilla eri ytimillä useita kertoja ja summata luvut copy-pastella taskulaskimella.
Mitään "riippumattomuusoletuksia"? ei tarvitse miettiä. Ei varsinkaan, jos laskettu tulos ei vastaa simulointia. Ei 12 satunnaislukua ole (juuri koskaan?) täysin riippumattomia tässä tehtävässä. Jos nuo luvut olisivat kuusijärjestelmässä 2 merkkisiä, niitä olisi 4 kpl ja n olisi esim. 8, niin ei olisi mitään ongelmaa käydä läpi joka ikinen vaihtoehto. Kokeile. Saattaa paljastua jotain matemaattisesti mielenkiintoista. Ihan paperillakin laskien. Anonyymi kirjoitti:
Vastaus on simuloimalla n. 0,00385107.
Nopea simuloida, jos muuntaa nuo numerot ensin kuusijärjetelmään eli nopassa numerot (0,1,2,3,4,5) ja näin muodostetun luvun arvon kymmenjärjestelmään. Mikään ei muutu matemaattisesti ajatellen. Riittää siis käydä läpi lukualuetta 0...6^6-1 (0...46655). Seuravat luvut saadaan jakamalla tuo (kymmenjärjestelmän) luvut 6:lla ja ja lisäämällä niihin 6^5. Kaikki yksinkertaistuu ja ohjelma lyhenee ja nopeutuu.
Alkuperäisen kysymyksen luvut olisivat siis
Nl = [1865, 266, 28259, 43, 18705, 37367, 0, 9331, 18662, 27993, 37324, 46655]
Satunnainen lista saadaan nopeasti suoraan randint(0,46655):lla ja if not in Nl:.
Riittää laskea kokonaismäärä vain n:n arvolla 20 ja summata noita arvoja. Tutulostuksessa summan voi jakaa toistojen 10000:n tai 100000:n määrällä päässälaskuna. Ja ohjelmaa voi ajaa useilla eri ytimillä useita kertoja ja summata luvut copy-pastella taskulaskimella.
Mitään "riippumattomuusoletuksia"? ei tarvitse miettiä. Ei varsinkaan, jos laskettu tulos ei vastaa simulointia. Ei 12 satunnaislukua ole (juuri koskaan?) täysin riippumattomia tässä tehtävässä. Jos nuo luvut olisivat kuusijärjestelmässä 2 merkkisiä, niitä olisi 4 kpl ja n olisi esim. 8, niin ei olisi mitään ongelmaa käydä läpi joka ikinen vaihtoehto. Kokeile. Saattaa paljastua jotain matemaattisesti mielenkiintoista. Ihan paperillakin laskien.Joo, ei se tarkasti tuo riippumattomuudella oletettu kaava pädekään. Kokeilin itsekin pienillä arvoilla ja antoi aika eri tuloksen tuo riippumattomuus-kaava. En mitään kaava kyllä niissä tarkoissa arvoissakaan huomannut (aika rajoitettuahan se on minkä kokoiset tapaukset pystyy kaikki enää tarkasti laskemaan).
Mutta onhan tuo arvo aika lähellä, niin kai siinä jotain sellaista tapahtuu, että ne riippuvuudet "kumoaa toisiaan" kun lasketaan keskiarvoa kaikkien mahdollisten kaksitoistikoiden yli.- Anonyymi
minkkilaukku kirjoitti:
Joo, ei se tarkasti tuo riippumattomuudella oletettu kaava pädekään. Kokeilin itsekin pienillä arvoilla ja antoi aika eri tuloksen tuo riippumattomuus-kaava. En mitään kaava kyllä niissä tarkoissa arvoissakaan huomannut (aika rajoitettuahan se on minkä kokoiset tapaukset pystyy kaikki enää tarkasti laskemaan).
Mutta onhan tuo arvo aika lähellä, niin kai siinä jotain sellaista tapahtuu, että ne riippuvuudet "kumoaa toisiaan" kun lasketaan keskiarvoa kaikkien mahdollisten kaksitoistikoiden yli.Muuta tehtävän sanamuoto toiseksi. Varmasti joku 1800-luvun matemaatikko on tätä miettinyt ja oeis.org:sta löytyy sitten kaavoja ja listoja eri tapauksille. Vähän mielikuvitusta! Voisi olla 2-numeroisia 5-järjestelmän lukuja 5 kpl ja n = 5.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
24h Kirppis
Olen muuttamassa paikkakunnalle ja mietin olisiko tälläiselle liikkeelle tarvetta alueella?133808Kerotakaa joensuun kontiolahden paiholan laitoksesta jotain
Mun kaveri joutuu paiholan laitokseen nyt lähi aikoina niin voisko ihmiset kertoa minkälaista siellä on tarinoita jne ja283123Suomessa eletään liian pitkään
"Ihmisten on kuoltava" Asiantuntija varoittaa: Suomi ei ole valmis siihen, että niin moni elää pitkään: ”Kaiken täytyy2812982Deodoranttiteollisuus
Annan ilmaisen vinkin. Kyseinen teollisuus voisi alkaa valmistaa kuolleen ruumiin hajua. Olisi varma hittituote, ainakin81990- 2401707
Voitaisko olla kavereita?
Haluaisin aloittaa puhtaalta pöydältä sinun kanssasi, tabula rasa. Minä lopetan sinun perääsi haikailun, ja sitten sinäk61510- 751301
Martinan mies on Suomessa.
Siellä se on Martinan instassa ja täällä on jo ero tullut. Voi että kun huvittaa...2081295Maistaisitko sinä näitä valmisruokia?
Terhi Kinnari ja Kinnarin tila voitti Suomalainen menestysresepti -kisan. Makuja Kinnarin tilan kaurapohjaisissa aterioi351096Rukoilimme Länsimuurilla 2000 vuoden jälkeen, Jumalamme oli antanut meille kaiken takaisin
Western Wall, In our Hands. 55th Para. https://www.youtube.com/watch?v=u4BJAppyCSo https://en.wikipedia.org/wiki/55th_41081