<<<

S49. MATCHES.83P

>>>

De rij {1, 2, ..., N} in L1 wordt geschud. De geschudde rij zetten we in L2. Schudden is als het ware de inverse van ordenen. Goed schudden lijkt gemakkelijker dan het is. Bij een grote rij is je computertje al gauw een hele tijd bezig voordat er een beetje resultaat is. Een redelijk principe (maar vast niet het beste principe) bij grote waarden van N is dan het telkens verwisselen van een paar getallen:
Lbl 0
randInt(1,N)->X: randInt(1,N)->Y
L2(X)->Z: L2(Y)->L2(X): Z->L2(Y)
Goto 0
Bij kleinere rijen (n kleiner dan ongeveer 15) wordt er beter en sneller geschud door uit te gaan van een randomrij van N getallen en telkens te onderzoeken of er nog getallen ontbreken:
Lbl 0
randInt(1,N)->R
If sum(L2=R)=0
Then
T+1->T:R->L2(T)
End
If T<N:Goto 0
De verwachting dat een getal op zijn plaats blijft is 1/n; aangezien er n getallen zijn is het totaal aantal verwachte matches gemiddeld n.1/n = 1.

De formule voor m matches op n posities luidt:

p(m|n)=1/m!.(1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)^(n-m) / (n-m)!)