On Fri, May 16, 2003 at 07:14:46PM +0200, Frank Heckenbach wrote:
Emil Jerabek wrote:
Still not sure what you mean by uniform here. Anyway, it is possible to fix the `Include (SetA, Random (MaxN))' method so that it always produces a set of size n.
For n small:
A := []; for j := 1 to n do begin repeat r := Random(MaxN) until not (r in A); Include (A, r) end;
For n bigger:
A := []; for j := 0 to n-1 do begin r := Random (MaxN - j); { find the r-th element of A's complement: } k := 0; repeat if not (k in A) then Dec (r); if r < 0 then break; Inc (k) until False; Include (A, k) end;
For n > MaxN/2, generate a set of size MaxN-n, and take its complement.
That's O(n^2). O(n) is possible by using the "card deck shuffling" algorithm. (If you really want exactly n elements -- I think it's sufficient and easier to treat the elements independently.)
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).
I wrote:
If p is an integral multiple of a power of 2, say p=k/2^m, you may generate one bit from m Random() bits by
for j := 0 to MaxN-1 do if Random(1 shl m) < k then Include(A, j);
With some extra shuffling, 32 bits per Random() call may be used, which will make it reasonably fast. For example, if m divides 32:
q1 := (1 shl m) - 1; q2 := (BitSizeOf (MedCard) div m) - 1; for j := 0 to MaxN-1 do begin if (j and q2) = 0 then rnd := Random (High (MedCard)); if (rnd and q1) < k then Include (A, j); Shr (rnd, m) end;
The loops should go from 0 to MaxN, not MaxN - 1. Random (High (MedCard)) is also off by one, both here and in Mirsad's original example. Random (High (MedCard) + 1) is likely to fail miserably on 64-bit machines with MedCard=LongestCard, but I'll continue to use it here for simplicity.
Here's another way to get independent bits, each with probability p=k/2^m, with smaller overhead.
{ assume 0 < k < 2^m } while not Odd (k) do begin Shr (k, 1); Dec (m) end; A := []; for i := 1 to m do begin if Odd (k) then for j := 0 to (MaxN + 1) div SetWordSize - 1 do Or (Bar[j], Random (High (MedCard) + 1)) else for j := 0 to (MaxN + 1) div SetWordSize - 1 do And (Bar[j], Random (High (MedCard) + 1)); Shr (k, 1) end;
Emil