Lottery Number Generator Part 2

posted at Tue, 20 Nov 2001 17:44:41 :-

Quote:

>> To generate M different balls drawn at random from a set of 1..N, where

>> N<=255 (* h'mmm - how about a zero ball? *), there is no need to perform

>> o(N) operations.

>> <URL: http://www.*-*-*.com/ #Draw> :

>> type RandomSet = set of 1..MaxN ;

>> { Generate M non-repeating random numbers from 1 to N }

>> procedure GenerateRandomSet(M, N : Integer ; var aSet : RandomSet) ;

>> var J : Integer ;

>> begin

>> if M < 1 then aSet := []

>> else begin

>> GenerateRandomSet(M - 1, N - 1, aSet) ;

>> J := Random(N) + 1 { J is in [1..N] } ;

>> if J in aSet then Include(aSet, N) else Include(aSet, J) ;

>> end ;

>> end {GenerateRandomSet} ;

>> It seems to work, & DR is trustworthy.

>> I believe I have understood it.

>Very clever! How about a non-recursive version:

>aSet := [];

>for K=N-M+1 to N do

>begin

> J:=Random(K)+1;

> if J in aSet then aSet := aSet + [K] else aSet := aSet + [J];

>end;

>I think i got that right...

I think you did. In translating it into Javascript - formally, JS does

not have Sets, but an array with elements that may or may not be defined

can be used for a Set - ISTM that the long line can be replaced by

if J in aSet then J := K ;

aSet := aSet + [J] ;

which seems clearer and possibly gives better code.

--

<URL: http://www.*-*-*.com/ ; FAQ for comp.lang.javascript by Jim Ley.

<URL: http://www.*-*-*.com/ ; JS maths, dates, sources.

<URL: http://www.*-*-*.com/ ; TP/BP/Delphi/JS/&c., FAQ topics, links.