2

In search for a faster weighted sampling without replacement, the following question came up:

Is there an algorithm that implements random sampling without replacement with unequal selection probabilities using linear time in the size of the input? An O(n log n) implementation has been suggested in an answer to this question -- can this be improved?

Community
  • 1
  • 1
krlmlr
  • 25,056
  • 14
  • 120
  • 217
  • I imagine one should be able to modify a [Knuth shuffle](http://en.wikipedia.org/wiki/Knuth_shuffle#The_modern_algorithm) for this purpose, but it probably won't be easy. – Bernhard Barker Feb 27 '13 at 16:01
  • Google `Pareto sampling` and `Conditional Poisson Sampling`. You'll eventually reach this: http://books.google.com/books/about/Sampling_Algorithms.html?id=2auW1rVAwGMC – Ferdinand.kraft Apr 06 '13 at 22:30
  • Alright, I'm clearly missing something. Constructing a roulette wheel for selection is a linear operation. Searching is an O(log n) operation. Searching and then reconstructing the wheel ought to take O(n + log n) = O(n) time. What am I missing? – Ryan Marcus Aug 13 '13 at 18:37
  • @RyanMarcus: It's about sampling `n` items, essentially a permutation. – krlmlr Aug 14 '13 at 04:37
  • Consider asking cs-related questions in [cs.stackexchange.com](http://cs.stackexchange.com). – Realz Slaw Oct 14 '13 at 02:10

0 Answers0