Randomization algortihms 
Author Message
 Randomization algortihms

Hello

I am looking for some information, be it a flow chart, description, or VI
that will randomize a series of strings. Sort of like shuffling a deck of
cards. I am trying to run a series of test scripts which are executed by
typing in a list scripts. There would be between two and ten scripts in
list. I would like to execute them in a random order. I am trying to keep
this as simple as possible using only labview (no CIN's or dll calls) any
help would be appreciated.



Mon, 09 Jul 2001 03:00:00 GMT  
 Randomization algortihms
Randomizing an array of anything is really quite simple.

Connect Array to input Shift Register of While Loop.
Inside While Loop
   Feed Input Shift Register to two Index Arrays and daisy chain two
              Replace Array Element functions and then to the output Shift
              Register.
   Generate two random indexes (IA & IB) between 0 and array size.
   Index array with indexes (DA & DB)
   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.

I hope this helps.
Bob Hopkins

Quote:

>Hello

>I am looking for some information, be it a flow chart, description, or VI
>that will randomize a series of strings. Sort of like shuffling a deck of
>cards. I am trying to run a series of test scripts which are executed by
>typing in a list scripts. There would be between two and ten scripts in
>list. I would like to execute them in a random order. I am trying to keep
>this as simple as possible using only Labview (no CIN's or dll calls) any
>help would be appreciated.



Tue, 10 Jul 2001 03:00:00 GMT  
 Randomization algortihms

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."

Greg McKaskle



Wed, 11 Jul 2001 03:00:00 GMT  
 Randomization algortihms


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."



Thu, 12 Jul 2001 03:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Randomization Algorithms

2. Randomization Code

3. Randomization Algorithm

4. Need Help: Randomization in Prolog

5. "ANTI-RANDOMIZATION" function.

 

 
Powered by phpBB® Forum Software