/* 

  Distinct number draws in Picat.

  https://brainstellar.com/puzzles/probability/208
  """
  Given the set of numbers from 1 to n: {1, 2, 3 ... n}. We draw n 
  numbers randomly (with uniform distribution) from this set (with replacement). 
  What is the expected number of distinct values that we would draw?

  Answer: E(n) = n[1-(1-1/n)^n]
  """

  Cf my Gamble model gamble_distinct_number_draws.rkt

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import ppl_distributions, ppl_utils.
import util.

main => go.

theoretical(N) = N*(1- (1-1/N)**N).
/*

  n = 6,theoretical = 3.99061]
  var : num distinct
  Probabilities:
  4: 0.5054500000000000
  3: 0.2296000000000000
  5: 0.2280500000000000
  2: 0.0200500000000000
  6: 0.0165500000000000
  1: 0.0003000000000000
  mean = 3.99055


  [n = 10,theoretical = 6.51322]
  var : num distinct
  Probabilities:
  7: 0.3556500000000000
  6: 0.3473000000000000
  8: 0.1368000000000000
  5: 0.1246000000000000
  4: 0.0180500000000000
  9: 0.0166500000000000
  3: 0.0005000000000000
  10: 0.0004000000000000
  2: 0.0000500000000000
  mean = 6.5184


  [n = 100,theoretical = 63.3968]
  var : num distinct
  Probabilities (truncated):
  64: 0.1252000000000000
  63: 0.1227000000000000
  65: 0.1148500000000000
  62: 0.1134000000000000
  .........
  52: 0.0003000000000000
  76: 0.0000500000000000
  75: 0.0000500000000000
  51: 0.0000500000000000
  mean = 63.3676

*/
go ?=>
  member(N,[6,10,100]),
  println([n=N,theoretical=theoretical(N)]),
  reset_store,
  run_model(20_000,$model(N),[show_probs_trunc,mean]),
  nl,
  % show_store_lengths,nl,
  fail,
  nl.
go => true.
  

model(N) =>

  Draws = random_integer1_n(N,N),
  NumDistinct = Draws.remove_dups.len,
  
  add("num distinct",NumDistinct).