K random numbers

[Tagore]

hi,
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?

 

[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?

This is more suitable for comp.programming and I have set followups.

I am not sure about your Big O. It depends on the what you are
measuring, but there is no obvious upper bound for the algorithm you
describe.

There is an elegant algorithm by Floyd for this. It was published in
the CACM's Programming Pearls column and subsequently in Jon Bentley's
second book "More Programming Pearls"[2]. It uses O(k) calls to the
random number generator (in fact it uses exactly k calls to it). It
is fun to think this through, so I have put it below the footnotes.
Don't read the spoiler if you want to try to re-discover it.

[1] Volume 30, Issue 9 (September 1987) pp 754-757.
[2] "More Programming Pearls: Confessions of a Coder", Addison Wesley,
1988.





SPOILER ALERT:


S = {} /* The empty set */
for j = n - k + 1 to n do
t := rand_in(1, j)
if t in S then
S := S + {j}
else S := S + {t}

 

[Richard Tobin]

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?

If you had a randomly shuffled array of the integers 1..n, you could
just take the first k of them. And there is a well-known, very
simple, O(n) algorithm for shuffling. What's more, if you stop the
algorithm after k steps, you will have k random numbers, so you
can easily make it O(k). But it does use O(n) space, which may be
a problem if k << n.

See http://en.wikipedia.org/wiki/Fisher?Yates_shuffle for the
algorithm.

-- RIchard

 

[Richard Tobin]

I didn't see anything about shuffling there.

Sorry, I didn't notice that the URL contained a Unicode en dash, and
when I posted in Latin-1, emacs converted it to a question mark.

Let's see if this works:

http://en.wikipedia.org/wiki/Fisher–Yates_shuffle

-- Richard

 

[Richard Tobin]

Let's see if this works:

Actually, it seems to work perfectly well with an ASCII hyphen:

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

-- Richard

 

[James Dow Allen]

hi,
  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?

To give a proper answer, I think your question
needs to be more focused:
(1) What's the (approx) largest n you'll encounter?
(2) Given that n, what's the (approx) largest k?
(3) Do you want the combination elements in
sorted order? Or do you want one of its k! permutations,
each equally likely?

The Floyd's algorithm posted by Ben Bacarisse may be
to be good enough for you but does suffer two disadvantages:
(a) it uses O(k^2) time, assuming the test "t in S"
takes O(|S|) time.
(b) the elements end up in *neither* sorted order, *nor*
as a uniformly-distributed permutation.

The "Fisher-Yates" shuffle avoids both these problems, but at
the cost of needing O(n) storage.

So ... O(n) storage *or* O(k^2) time? Is there a way to avoid
*both* of these undesireables? I know of a way which requires
you to generate a subset of Pascal's triangle: that would be
O(k*n) storage but at least it would be read-only storage!

James Dow Allen

 

[Ben Bacarisse]

The Floyd's algorithm posted by Ben Bacarisse may be
to be good enough for you but does suffer two disadvantages:
(a) it uses O(k^2) time, assuming the test "t in S"
takes O(|S|) time.

That's an odd assumption. In the cases I've programmed it in C, the
set was a bit map so it used O(n) extra space and was O(1) time[1],
but if n is really huge surely one would use a hash map for the set?
I would not assume worse than O(log n) the set lookup.

(b) the elements end up in *neither* sorted order, *nor*
as a uniformly-distributed permutation.

The "Fisher-Yates" shuffle avoids both these problems, but at
the cost of needing O(n) storage.

So ... O(n) storage *or* O(k^2) time? Is there a way to avoid
*both* of these undesireables?

Yes, the other algorithm I posted in comp.programming. Knuth names it
Algorithm S. O(1) space and time. It is O(1) space because it does
not represent the result. Floyd's algorithm is often the right one
because it does that efficiently.

I know of a way which requires
you to generate a subset of Pascal's triangle: that would be
O(k*n) storage but at least it would be read-only storage!

Often you need the result to be stored somewhere, so Floyd's algorithm
can be a big winner because the result is the set you want represented
in way that is efficient for your particular case. The shuffle method
can be impractical if n >> k.

[1] Using the usual casual assumption about Big O. In particular that
everything about integers is O(1)!

 

[bartc]

To give a proper answer, I think your question
needs to be more focused:
(1) What's the (approx) largest n you'll encounter?
(2) Given that n, what's the (approx) largest k?
(3) Do you want the combination elements in
sorted order? Or do you want one of its k! permutations,
each equally likely?

The Floyd's algorithm posted by Ben Bacarisse may be
to be good enough for you but does suffer two disadvantages:
(a) it uses O(k^2) time, assuming the test "t in S"
takes O(|S|) time.

I think S is a Pascal-type set. The test needn't take more than a few
machine instructions. There is no search needed.

(b) the elements end up in *neither* sorted order,
*nor* as a uniformly-distributed permutation.

I had a go at this (as the code maps 1:1 to one of my toy languages). The
output with N=1000 and K=20 was:

S=[ 26, 77, 119, 175, 250, 271, 313, 322, 328, 480, 559, 647, 650, 652..653,
656, 658, 661, 664, 775..776, 804, 815..816, 902..903, 906..908, 912, 914,
917, 920, 923, 932, 935]

That looks sorted to me. Of course the output with N=K=1000 would just be
[1..1000]; any randomness in creation order is not recorded.