How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N
Posted
by tucuxi
on Stack Overflow
See other posts from Stack Overflow
or by tucuxi
Published on 2008-10-01T17:21:30Z
Indexed on
2010/03/21
18:31 UTC
Read the original article
Hit count: 286
The question gives all necessary data: what is an efficient algorithm to generate a sequence of K non-repeating integers within a given interval. The trivial algorithm (generating random numbers and, before adding them to the sequence, looking them up to see if they were already there) is very expensive if K is large and near enough to N.
The algorithm provided here seems more complicated than necessary, and requires some implementation. I've just found another algorithm that seems to do the job fine, as long as you know all the relevant parameters, in a single pass.
© Stack Overflow or respective owner