«

Juha Laiho <> wrote:
> said:
> > (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

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB

said:
>Juha Laiho <> 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)

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.
Use shuffle algorithm instead.
-Joe