[futurebasic] Re: Random File List

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : October 1999 : Group Archive : Group : All Groups

From: Jay Reeve <jktr@...>
Date: Mon, 4 Oct 99 02:06:00 -0500
>Yours is a brilliantly 
>fast and simple recipe for "random" 
>shuffling a deck of cards.
>
>However I cannot quite convince myself that you
>have produced a perfectly shuffled deck.
>Have you an argument to prove that it is?
>
>The order 1,...,320 does play a definite r^ole
>in the shuffling so why not some r^ole in the result?

Hi Larry,

I couldn't get this to go through privately, so I'm sending it to the 
list. Perhaps it will interest someone else, too.

First, the (admittedly brilliant) recipe is not mine. I don't recall 
where I learned it, but I used a much more complex procedure until I 
discovered this somewhere.

There's nothing I can offer as concrete "proof," but here are some 
arguments and illustrations that may persuade you.

Take six cards, say the Ace thru 6 of spades, and lay them out in order. 
Assign an index number (1-6) to each position. Roll a die 6 times. On the 
first roll, swap the card in the position shown on the die with the card 
in position 1. (If the die shows a 1, don't move anything.) On second 
roll, swap the position indicated by the die with  position 2, and so 
forth for the six cards. 

You'll note that the card chosen for swapping is not always the card that 
started out in that position, but that each position in the deck is 
filled by a card chosen completely at random. The fact that the same card 
could conceiveably end up in its original position, either by being 
"swapped" only with itself, or by a series of swaps into other positions, 
further illustrates the randomness.

When you're done, think about how the position of any card could have 
been predicted without knowing the dice rolls. It can't. The card that is 
put in each position is chosen randomly from the entire deck. Whether it 
stays there or gets moved again is also decided randomly. It's actually 
far more random than the physical (standard) shuffling of a deck of 
cards, because the initial positions do have some effect on a standard 
shuffle.

The only effect the sequence has on the procedure is to make sure each 
card gets chosen randomly. That's why the example Jonathan offered was 
ambiguous. It had no way of establishing when all of the positions in the 
deck had been addressed.

As another exercise, run the short demo below. You can add your own 
routines if you like, to store the results and subject them to 
statistical analyses for randomness. (I assume such analyses exist--I'm 
not familiar with them.) You'll find the results appear intuitively to be 
random. Try it with only 2 cards, or with 9. If you see a suspect 
pattern, run it again and see if it recurs.

Remark out the FN makeDeck line in the main loop and run again. It 
doesn't matter whether you start with a "new" deck, or the one you ended 
up with on the last shuffle.

This fascinates me, so I could go on, but I think that's 'nuff for now. 
Let me know if your doubts persist.
 0"0
 =J= a  y
  "

=======================

_cardsInDeck = 6                          '2 to 9 best for this demo
_trials      = 50

DIM gDeck(_cardsInDeck)
END GLOBALS

LOCAL FN printDeck
  POKE @deck$,_cardsInDeck
  FOR c = 1 TO _cardsInDeck
    POKE @deck$+c, _"0"+gDeck(c)
  NEXT
  PRINT ,deck$
END FN

LOCAL FN makeDeck
  FOR c = 1 TO _cardsInDeck
    gDeck(c) = c
  NEXT
END FN

LOCAL FN shuffleDeck
  FOR c = 1 TO _cardsInDeck
    SWAP gDeck(c), gDeck(RND(_cardsInDeck))
  NEXT
END FN

WINDOW 1,"Shuffle test",(0,0)-(200,610)
FN makeDeck
PRINT

FOR t = 1 TO _trials
  FN makeDeck        'Remove this line & try again
  FN shuffleDeck
  FN printDeck
NEXT
PRINT:PRINT ,"Click to end."

DO
UNTIL FN BUTTON

======================