Keskustelu: Ohjelmointikysymykset: Python: Miten VB5 ohjelma Pythonilla?

Minulla on toimiva VB5-ohjelma:

Sub laske()
  n = txtN
  ReDim k(1 To n), p(1 To n)
  m = 0: o = 0
  Do
    For i = 1 To n
      p(i) = i
    Next
    i = 1
    Do
      j = Int(1 + n * Rnd)
      a = p(j)
      p(j) = p(n)
      If a = i Then
        o = o + 1
        Exit Do
      End If
      n = n - 1: i = i + 1
    Loop Until n = 0
    n = txtN
    m = m + 1: r = r + 1
    If r = 10000 Then
      r = 0
      txtTn = Format(o / m, "0.000 %")
      DoEvents
    End If
  Loop Until m > 1000000
  txtTn = Format(o / m, "0.000 %")
  cmdL.Enabled = True
End Sub

Ohjelma antaa suurilla n-arvoilla liian pienen tuloksen ja epäilen satunnaislukugeneraattoria. Yritin toteuttaa saman Pythonilla, mutta ei vaan onnistu millään. Voisiko joku Pythonia käyttänyt näyttää miten onnistuu. Minulla on Python 3.1.4.

Tässä vielä tämän hetkinen viritelmä:

# -*- coding: utf-8 -*-
import random
for k in range(99999):

  n = 100
  luvut = range(1,n)
  for i in range(1,n):
    j = random.randint(1,n)
    a = luvut(i)
    if a == j:
      o += 1
      break

    n -= 1
  m += 1
o/m

Valittaa ainakin rivistä a = luvut(i)

Tuossa koodissa on joitakin epäilyttäviä kohtia, mutta tässä teknisesti toimivaksi paikattu. Loogisesta oikeellisuudesta en mene takuuteen, koska en pienellä vaivalla hahmota mitä koodilla halutaan laskea.

# -*- coding: utf-8 -*-
import random

o = 0
m = 0

for k in range(99999):
    n = 100
    luvut = range(n)
    for i in range(n):
        j = random.randint(0, n - 1)
        a = luvut[i]
        if a == j:
            o += 1
            break
        n -= 1
    m += 1

print(o / m)

m on turha muuttuja, koska sama arvo on muuttujassa k. Samoin luvut-lista on turha, koska i on yhtä suuri kuin luvut[i].

Chiman ilmeisesti paikkaili Python-koodia. Itse en viitsinyt sitä katsoakaan, koska näyttää, että koodi ei oikein korreloi VB-version kanssa.

Käänsin sen sijaan koodin VB:stä Pythoniksi ja siistin hieman, ja sain tällaisen tuloksen:

import random
def laske(n):
  o = 0
  for m in range(1, 1000002):
    p = list(range(n))
    for i in range(n):
      j = random.randrange(n - i)
      if p[j] == i:
        o = o + 1
        break
      p[j] = p[n - i - 1]
    if m % 10000 == 0:
      print("%.3f" % (o / m), end = "\r")
  print("%.3f" % (o / m))
laske(100)

Luvut näyttävät samalta kuin VB-versiosta FreeBASICilla tulevat. Python-versio on kuitenkin tolkuttoman hidas.

Epäilemättä ongelmaan olisi ylipäänsä jokin järkevämpi ratkaisu, jos ongelma olisi tiedossa. Tuosta koodista en oikein alkuperäistä ajatusta hahmota.

Sorry kun jätin sen pois. VB5-hjelmaan sisältyi alkuun myös kommenttiriivit:
'sijoitetaan luvut 1...n satunnaisesti lokeroihin 1...n
'millä todennäköisyydellä ainakin yksi luku osuu oikeaan lokeroon.
Varmaan C tai C++ olisi tehokkaampi mutta sitä en hallitse edes sen vertaa kuin Pythonia, jolla joskus sentään sain toimivankin sovelluksen.

Lisäys:

Chiman kirjoitti:

m on turha muuttuja, koska sama arvo on muuttujassa k. Samoin luvut-lista on turha, koska i on yhtä suuri kuin luvut[i].

Tosiaan m on turha mutta listasta on tarkoitus poistaa aina kertaalleen arvottu luku jolloin listan sisältö ei enää vastaa järjestysnumeroa.

setä kirjoitti:

VB5-hjelmaan sisältyi alkuun myös kommenttiriivit:
'sijoitetaan luvut 1...n satunnaisesti lokeroihin 1...n
'millä todennäköisyydellä ainakin yksi luku osuu oikeaan lokeroon.

Pythonilla tuo kohta hoituisi esim. näin:

import random

hits = 0
n = 100
lista = list(range(n))
for k in range(99999):
    random.shuffle(lista)
    if any(i == x for i, x in enumerate(lista)):
        hits += 1
print("%.3f" % (hits / k))  # 0.635

Sain Metbolixin koodin toimimaan hieman muunneltuna. Mutta hidashan se tosiaan on. Suurilla luvuilla vastauksen pitäisi olla 1 - 1/e = 0,63212
Kun n=99, tulee 0.6322 ja 100 antaa 0.6316. Tulos hyppelehtii oikean arvon molemmin puolin siten, että parittomilla tulos on hieman yli ja parillisilla hieman ali. Chimanin koodi antaa hieman liian suuren arvon joten ilmeisesti koodi ei tee juuri sitä mitä tarkoitin.
Kiitokset avusta molemmille.

setä kirjoitti:

Chimanin koodi antaa hieman liian suuren arvon joten ilmeisesti koodi ei tee juuri sitä mitä tarkoitin.

Kyllä oman koodinikin tulos heittelee tuon mainitsemasi oikean arvon molemmin puolin. Tässä neljä peräkkäistä 999998 kierroksen tulosta, n = 100:
0.63254
0.63146
0.63173
0.63244

Askartelin tehtävään tällaisen funktion:

def f(n, m = 0):
  if n <= m:
    return 0
  return 1 / n + m / n * f(n - 1, m) + (n - m - 1) / n * f(n - 1, m + 1)

Rekursiota voi optimoida lisäämällä funktioon muistitaulukon jo kohdatuista parametreista. Toisaalta koodin saa myös nopeaan silmukkamuotoon:

def f(n):
  t = [0, 0]
  for i in range(1, n + 1):
    t = [1 / i + j / i * t[j] + (i - j - 1) / i * t[j + 1] for j in range(min(i, n - i + 1))] + [0, 0]
  return t[0]

Testiksi laskin ensimmäisiä tuloksia sekä mainitulla kaavalla 1-1/e raja-arvon.

for i in range(1, 20):
  print("f(%d) = %f" % (i, f(i)))

import math
print("lim   = ", 1 - 1 / math.e)

f(1) = 1.0
f(2) = 0.5
f(3) = 0.6666666666666666
f(4) = 0.625
f(5) = 0.6333333333333333
f(6) = 0.6319444444444444
f(7) = 0.6321428571428571
f(8) = 0.6321180555555554
f(9) = 0.6321208112874779
...
f(19) = 0.6321205588285577
lim   = 0.6321205588285577

setä kirjoitti:

'sijoitetaan luvut 1...n satunnaisesti lokeroihin 1...n
'millä todennäköisyydellä ainakin yksi luku osuu oikeaan lokeroon.

En ole varma, onko kyseessä ohjelmointiharjoitus vai pelkästään ongelman ratkaisu keinolla millä hyvänsä. Tehtävän ratkaisu onnistuu myös ilman tietokonetta: http://fi.wikipedia.org/wiki/Rencontre-ongelma

Tehtävä ratkeaa kyllä ilman tietokonetta ja ratkaisu oli tiedossa. Halusin itse testata tulosta simulaatiolla jonka toteutin VB5:llä koska juuri muita kieliä en osaa. Koska simulaation tulos suurilla luvuilla poikkesi jo yli prosentin alaspäin aloin epäillä VB:n satunnaislukugeneraattoria. Siksi halusin kokeilla Pythonilla, koska sellainen kehitysympäristö on koneellani ja olen joskus sitä käyttänytkin mutta todella vähän. Siksi pyysin apuja täältä. Kiitän avusta ja asia selvisi. VB:n satunnaislukugeneraattori on epäluotettava kun satunnaislukujen määrä ylittää generaattorin jakson hieman yli 15 miljoonaa.
Jaskan esittämän linkin tehtävä käsittelee hieman eri todennäköisyyttä. Metabolixin ratkaisu on aivan oikea.

setä kirjoitti:

Jaskan esittämän linkin tehtävä käsittelee hieman eri todennäköisyyttä.

Kyllä nuo mielestäni ovat saman tehtävän eri muotoiluja. Okei, olisi pitänyt tarkkaan ottaen mainita, että tuossa Wikipedian artikkelissa on laskettu postaamasi tehtävän komplementtitapahtuman todennäköisyys, joka on siis (-1)^0/0!+...+(-1)^52/52!.

Aivan, siinähän oli laskettu todennäköisyys ettei ainutkaan osu omaan lokeroon.
VB5:n simulaatiokin antaa oikean tuloksen kun n on noin parin kymmenen luokkaa. Tietysti hajontaa on toistettaessa simulaatiota. Mutta tosiaan arvoilla noin 1000 tulos putoaa reilun prosentin alle oikean arvon. Python antaa oikean arvon suurillakin n:n arvoilla mutta on silloin todella hidas.
Simulaatiolla hain edes likimääräistä ratkaisua koska en matemaattista ratkaisua itse löytänyt.