Instantly share code, notes, and snippets.

# hakank/gist:945167 Created Apr 27, 2011

Simulation of Coupon Collector's problem in K (Kona)
 / Coupon collector's problem / E.g. how many times is required to throw a die / until all 6 values has been shown. / / Or: How many coupons must be bought to get the the complete collection. / / http://en.wikipedia.org/wiki/Coupon_collector%27s_problem / Let's simulate the die version. / Define some helper functions: / frequency table table:{b@#?p;(p,:1?6)];p}[]}'!100) / Sample result: / (6 1 / 7 3 / 8 5 / 9 7 / 10 5 / 11 10 / 12 10 / 13 6 / 14 9 / 15 8 / 16 5 / 17 7 / 18 7 / 19 4 / 21 1 / 22 3 / 23 3 / 24 1 / 27 2 / 29 2 / 49 1) / The average value is about 14... / Here for 100 simulations am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !100) / Sample result: 14.9 / Here for 10000 simulations am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !10000) / Sample result: 14.7029 am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !10000) / Sample result: 14.6794 / 100000 runs should be more accurate. am ({#{p:();while[6>#?p;(p,: 1 ? 6)];p}[]}' !100000) / Sample result: 14.70257 / Some explanations: / while[condition; do something] / where the condition is false if 0, and true 1 / The condition is thus: / 6>#?p / / ?p / is the number of unique values in the vector p. / / #?p / is the number of unique values / / p is first assigned to an empty list / p:() / and is then in the while clause appended with the / selected (randomized) number: / (p,:1?6) / / In short, we append p until we have got all different values / 0..5 / The last / {...} '!100 / means that we run the function { ... } for 100 times. /
to join this conversation on GitHub. Already have an account? Sign in to comment