mercredi 15 novembre 2017

generate s random numbers, without duplicates, in O(1) space, O(s) time

Generate a stream of s uniformly-distributed random numbers, without duplicates, in O(1) space, O(s) time

Clearly ruled out:

  • Any sort of Knuth/Fisher-Yates shuffle
  • Rejection sampling

After some thought, I'm not even sure if such a solution is possible.




Aucun commentaire:

Enregistrer un commentaire