Quote:

>> Randomizing an array of anything is really quite simple.

>...

>> Feed DA into Replace array element using IB as index.

>> Feed DB into Replace array element using IA as index.

>> Execute while loop at least 30 time the number of elements.

>> The output shift register will be a randomized array of whatever the

>> original data was.

>This approach will work, but you don't have to shuffle that many times

>to have the deck randomized. One of the pieces of trivia that they

>force CS students to learn is something called the perfect shuffle

>algorithm. They ask you to prove that a given algorithm is sufficient

>to randomize a deck of cards. I'll skip the proof, because its not the

>sort of thing I tend to remember, and go straight to the algorithm.

>The perfect shuffle works much like the already described code, a

>while loop with a pair of shift registers. The shift register

>carries the working array, and is initialized with the non-random

>array. Inside the loop Select one random number that ranges between

>IndexA and IndexB. The key is to move IndexA forward by one each

>iteration of the loop; so it isn't random, it uses the iteration

>counter of the loop.

>The first iteration swaps item 0 with a random item between 1 and N.

>The second iteration swaps item 1 with a random item between 2 and N.

>...

>The last iteration swaps the next to last and the last element.

>This is called the perfect shuffle because it randomizes the cards with

>N-1 shuffles and is guaranteed to finish in a constant amount of time for

>a given size array, and it doesn't require a second buffer or the array,

>it operates inplace with only enough storage to swap two elements of the

>array.

>This doesn't model the way that a dealer would shuffle a deck of cards; so

>if you are making a blackjack game, you may want to try something different.

>If you think through an example with a small array size like 2, 3, or 4,

>you can see that it does a good job, or if you wish to have a proof, I'll

>take a cue from my old textbooks, and "the rigorous proof is left as an

>exercise for the reader."

I believe that the "perfect shuffle" does model "shuffling" correctly. You can

view the array as divided into two parts, the deck cards, and the dealt cards.

After each iteration, the number of "dealt" cards increases, while the nunber

of "deck" cards decreases. The odds of a card being drawn from from the

remaining "deck" in 1 out of the total number of cards left in the deck. It is

eqivalent to a dealer taking an ordered deck, and drawing a random card out of

the deck and dealing it (if you assume true randomness). The originally

proposed algorithm does not model it correctly, because after a "card" is

selected, it is not removed from the "deck". It models a situation where a

card is drawn, and then returned to the deck.

http://www.enteract.com/~dsolomon/

"No amount of planning will ever replace dumb luck."