choice.nim

import mersenne, tables, sequtils, algorithm

var rng = newMersenneTwister(1)

proc random(m: int): int =
  rng.getNum mod m

proc randomChoice(k, n: int): seq[int] =
  # Fisher-Yates with a hash table.
  result = @[]
  var work = initTable[int, int]()
  for i in countdown(n, n-k+1):
    let r = random(i)+1
    if work.hasKey(r):
      add(result, work[r])
    else:
      add(result, r)
    work[r] = i
  sort(result, cmp[int])

var tab = newTable[seq[int], int]()

for i in 1..100000:
  let t = randomChoice(3, 10)
  if not tab.hasKey(t):
    tab[t] = 1
  else:
    tab[t] = tab[t] + 1

echo tab