On Tue, 20 May 2003, Frank Heckenbach wrote:
Emil Jerabek wrote:
On Fri, May 16, 2003 at 07:14:46PM +0200, Frank Heckenbach wrote:
Emil Jerabek wrote:
For n small:
A := []; for j := 1 to n do begin repeat r := Random(MaxN) until not (r in A); Include (A, r) end;
I agree. Also, on a second look, the first algorithm ("for n small") gives O(n) as well, even for n as big as MaxN/2 (the expected number of calls to Random is 1.386 n).
Yet, Frank, Emil, I'm uncomfortable with this repeat r := Random (MaxN) until not (r in A) ...
I get a feeling that this cripples linearity of generated set, and I suspect p(n in A), n in [0..MaxN-1] is no longer constant and equal to n/MaxN ...
Besides, consider the overhead if the set is near-full, and desired n/MaxN is for example 0.95 ... At the end of filling set we'd end to 20 calls to Random (MaxN) for each next bit.
IMHO, the
for i:= 0 to MaxN-1 do if Random (MaxN) <= n then Include (A, i);
(I think Frank suggested it) is better, even though it's perhaps slower. It has guaranteed O(n), at least, and it's very easy to parametrize set with p=n/MaxN probability of each bit being set.
We can also have Monte-Carlo-ized
for i:= 0 to MaxN-1 do if Random (MaxN)/MaxN <= F(i) then Include (A, i);
To get a non-uniform p distribution.
Frank wrote:
Here's another way to get independent bits, each with probability p=k/2^m, with smaller overhead.
But this one relies on the internal representation again. My point was to get rid of it.
Why I still want to have something "internal" generating random sets of numbers is that I'd like a common user that might lack your knowledge on the matter to be able to use them, for example, for statistical purposes, or as a source of random data for program testing ...
I think they might deserve a function or two in RTS, or at least function or two in a unit.
Mirsad