Generating k Random Numbers
Tagore
I want to generate k different random numbers between 1 to n. (k<n).
One of the appraoch is calling random function again and again. and
checking wheter new generated number had already been generated. but
its complexity is O(n^2).....Is there any better mthod?
PS:1,k and n are all integers.
Chris McDonald
Investigate the many, and simple, algorithms for drawing cards from a
deck of cards.
--
Chris.
Ben Bacarisse
> I want to generate k different random numbers between 1 to n. (k<n).
> One of the appraoch is calling random function again and again. and
> checking wheter new generated number had already been generated. but
> its complexity is O(n^2).....Is there any better mthod?
You multi-posted. See my reply in comp.lang.c with followups here.
--
Ben.
rossum
Set up an array containing the numbers 1 to n. Shuffle the array as
far as the k'th entry using algorithm P in Knuth section 3.4.2. Take
the first k elements of the array.
rossum
Ben Bacarisse
... or use algorithm S from the page before which does not need O(n)
auxiliary storage. Alternatively, Floyd's algorithm is exercise 17 in
the same section.
[I am just keep the two treads synchronised in case anyone searches
for this later. it would have been neater if the OP had not
multi-posted.]
--
Ben.
Beej Jorgensen
>Set up an array containing the numbers 1 to n. Shuffle the array as
>far as the k'th entry using algorithm P in Knuth section 3.4.2.
This is actually one of my favorite "demo" problems for people who are
new to programming, or who are non-computer scientists. The obvious
solution is also obviously inefficient, and the good solution is still
completely simple and easy to comprehend--it's just a different way of
thinking about it. Plus it's easy to see the relative complexity of the
two approaches.
-Beej
Gene
If I recall, Jon Bentley discusses this in Programming Pearls for the
case where n is large and k is comparatively small. For example, take
the task of drawing a random sample of a thousand people to survey
from a population of 10 million. Filling an array with 10 million
values just to draw 1,000 is overkill: O(n) in time and space.
Instead, begin by assuming items are numbered 1 to n. To draw item i
for i = 1 to k, generate a random number p in 1 .. (n - i - 1). This
p is effectivly an "index" into the list of remaining items not yet
drawn, except you don't want to implement this list explicitly. To get
the item itself, you need only to know how many items, let's say c, of
the (i - 1) already drawn are less than p. Then the item is p + c.
The quantity c is an order statistic, It can be efficiently found --
for example -- by keeping the items already drawn in a BST where each
node contains a count of its descendants. The complete algorithm has a
complexity of O(k log k) rather than O(n). Of course you can
substitute a sorted array for the BST, which makes for very simple
implementation, but decreases performance to O(k^2).