programming challenge

[Wacky]

Originally Posted by c00ler

Ok, we must use 52 time-based seeds and/or hardware PRNG.
The way to do it is to choose the seed just before generating the next random number.

No, it is not necessary to have that many seeds. All that is required is that the entropy of the random source have enough bits to exceed 52!. Certainly using 52 seeds, if they have at least 6 bits, is a way to do it. However, you can also use each seed more than once, provided that you never use any given seed more times than its entropy supports. For example, if a seed has 64 bits of entropy, the first could be used 10 times. A second could be used to generate the next 10 numbers. At that point, we have only 32 cards remaining. The final 3 seeds need support only 11 numbers each, although they could easily support 12 or more.

[Fusion_power]

There's nothing like a spirited discussion (think fists, blood, and cursing) to get you going in the morning!

The oldest and arguably most effective trick in the world is to prime the random number generator from a pseudo random source. Using the internal clock as I did above is reasonably effective. There are also tricks that can be used to set sound wave generators on a relatively fast cycle and then read the numeric level of the volume and use that number to prime the random number generator.

That said, this has become a fairly interesting thread. I will point out a minor flaw with some of the routines above.

for i = 1 to 52
generate random number, r, such that i <= r <= 52
swap the cards i and r
next i

This routine yields a fairly high probability that some cards remain in their original order. The routine I use as above would roughly translate as:

for i = 52 to 1 step -1
Generate a random number, r, such that i <= r <= 52
move the card r to new array in position i
move all higher cards down 1 .... or replace card r with i in NickGlover's version.
next i

The result is that the next card selected can never be one of the previous selected cards because those cards are in another array. This significantly increases the randomization effectiveness.

Fusion - who hasn't had time to finish up his program, too much to do!

One more note, one of the major uses for huge prime numbers is as seeds in random number generators. The larger the prime, the greater the probability of random results!

[Wacky]

Originally Posted by Fusion_power

I will point out a minor flaw with some of the routines above.

for i = 1 to 52
generate random number, r, such that i <= r <= 52
swap the cards i and r
next i

This routine yields a fairly high probability that some cards remain in their original order.

The result is that the next card selected can never be one of the previous selected cards because those cards are in another array. This significantly increases the randomization effectiveness.

I think that you should re-examine Nick's procedure. At each step, i, he selects one of the previously unselected cards. The card that was in position i is moved into the unselected region and the selected card is then moved to position i. At the end of the iteration, position i now holds a selected card and is no longer considered in future selections.

As a result, I believe that the sequence generated is perfectly random if the random number generator is truely random.

I cannot support your assertion that

This routine yields a fairly high probability that some cards remain in their original order.

[Fusion_power]

Wackerbarth,

I did look at it again and you are correct. It is highly random. The only issue is just how random is random. Unfortunately, my routine has the same concern.

Fusion