Velocity Reviews > Perl > Using rand(), how to I avoid repeats?

# Using rand(), how to I avoid repeats?

ctcgag@hotmail.com
Guest
Posts: n/a

 07-24-2004
Juha Laiho <(E-Mail Removed)> wrote:
> http://www.velocityreviews.com/forums/(E-Mail Removed) said:
> >(E-Mail Removed) (Scott Stark) wrote:
> >> All I can think of is keeping a list of used numbers, and having some
> >> kind of "if used, next" statement, which seems lame.

> ...
> >> (Theoretically that could keep going forever, if it randomly kept
> >> selecting the same numbers.) Any thoughts?

> >
> >If your random number generator degenerates thus, then in that case you
> >are pretty much screwed regardless.

>
> Not so -- think of a situation where your number space is f.ex.
> 1000 numbers, and you don't want repetitions. You'll end up with a
> significant and inreasing possibility of retries for each new number.

Increasing, but for the most part trivial.

> For the last number, there's only a 1/1000 chance that the random
> algorithm comes up with the desired number. I made a small script
> to test this; even with range of 3 (create randomised list of numbers
> of 1 to 3) I got with short testing 12 "false guesses" in generating
> the list. With larger ranges the number of false guesses got
> significantly worse -- with just range of 1000, the worst results I got
> had over 3000000 false guesses. Results with less than 1000000 false
> guesses seemed to be rare.

You clearly did something wrong. It rarely takes over 15,000 tries to get
all numbers from 1 to 1,000. The odds against needing 1,000,000 tries are
beyond astronomical.

If your random number generator is so defective that you can't get the
numbers you need from it using the hash method, then neither can you trust
its use in your shuffling procedure.

>
> So, for a list of random numbers without repetitions, the shuffled list
> algorithms are definitely better.

That is true as long as it is possible to enumerate all possible numbers
within the domain and you want to sample a large fraction of that domain
(as I said myself in the paragraph you snipped).

If we are talking about general methods, I'd rather have a method that
works in general and is slightly suboptimal in a special case, than a
method that fails in general but works in one special case.

Xho

--
Usenet Newsgroup Service \$9.95/Month 30GB

Juha Laiho
Guest
Posts: n/a

 07-25-2004
(E-Mail Removed) said:
>Juha Laiho <(E-Mail Removed)> wrote:
>> with just range of 1000, the worst results I got had over 3000000
>> false guesses. Results with less than 1000000 false guesses seemed to
>> be rare.

>
>You clearly did something wrong. It rarely takes over 15,000 tries to get
>all numbers from 1 to 1,000. The odds against needing 1,000,000 tries are
>beyond astronomical.

Thanks for the correction; my previous test snippet apparently did have
some dire problem -- now I seem to get repetitions in the range of 5000
when generating numbers 1..1000 - so looks like I can agree with your
results.

Apologies for criticizing your method on false grounds.
--
Wolf a.k.a. Juha Laiho Espoo, Finland
(GC 3.0) GIT d- s+: a C++ ULSH++++\$ P++@ L+++ E- W+\$@ N++ !K w !O !M V
PS(+) PE Y+ PGP(+) t- 5 !X R !tv b+ !DI D G e+ h---- r+++ y++++
"...cancel my subscription to the resurrection!" (Jim Morrison)

Joe Smith
Guest
Posts: n/a

 07-25-2004
Juha Laiho wrote:

> Not so -- think of a situation where your number space is f.ex.
> 1000 numbers, and you don't want repetitions. You'll end up with a
> significant and inreasing possibility of retries for each new number.
> For the last number, there's only a 1/1000 chance that the random
> algorithm comes up with the desired number.

If you have 1000 numbers available, and have used 999 of them,
then the last number is *NOT* random! Using rand() to return
the one and only possible number is not the way to do things.
-Joe

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Edward A. Falk C Programming 1 04-04-2013 08:07 PM aks_java Java 30 03-25-2010 11:48 AM Roger23 ASP .Net 2 10-12-2006 10:54 PM Shan McArthur ASP .Net Building Controls 2 06-30-2005 02:37 PM Alexander Malkis C++ 8 04-13-2004 11:23 PM