MATHEMATICS
Shuffle an array
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 (16) 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 existI'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.
_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
Jay
It is important _not_ to reseed a random number generator on the fly. In most systems, the seed is generated from reading a clock, so that repeated seedings give strongly correlated starting values, or even the same value. Reseeding does not increase randomness; it _reduces_ it.
In FB^3, for instance, RANDOM[IZE] seeds the random number generator from the MacOS seconds counter:
gFBRndSeed& = [_Time] //Seed Random number generator
Since [_Time] changes only every second, the hazard of reseeding within a program should be obvious.
Use RANDOM[IZE] at most once in your program, at startup time.
Robert Purves
I have an alphabetic order list of file names which I need to randomize.
If I have, say, 320 files, how do I create a random list of numbers from 1 to 320 such that every number from 1 to 320 appears once and only once in the randomized sequence?
If I use RND(320) I believe some individual numbers will be generated more than once...
If I do something like:
CLEAR LOCAL
LOCAL FN okToAddRandom(aRandom%, CurrCount%)
DIM okToAdd%, count%
FOR count% = 1 TO CurrCount%
LONG IF gRandom%(count%) = aRandom%
okToAdd% = _false
count% = CurrCount%
XELSE
okToAdd% = _true
END IF
NEXT count%
END FN = okToAdd%
CLEAR LOCAL
LOCAL FN getRandomSequence(fileCount%)
DIM CurrTime&, mySeed%, count%, okCount%
' fileCount% <= 320
' dim gRandom%(320%) done in GLOBALS file
CurrTime& = [_time]
mySeed% = CurrTime&/(256*256)
mySeed% = ABS(mySeed%)
RANDOM mySeed%
okCount% = 0
WHILE count% < fileCount% + 1
myrandom% = RND(fileCount%)
LONG IF okCount% = 0
gRandom%(1) = myrandom%
okCount% = 1
count% = 1
XELSE
'at least one myrandom% has been added to gRandom%(count%)
LONG IF FN okToAddRandom(myrandom%, count%) =_true
count% = count% + 1
gRandom%(count%) = myrandom%
END IF
END IF
WEND
END FN
I can see that certain sequences for 320 numbers would take a long, long time, some thing like 320*320 (102,400) passes to produce a fully populated, random sequence?
Is there a better way?
Michael Evans
1. Create an array : DIM Array$(320)
2. Put a value into each slot :
_MaxItems = 320
for a = 1 TO _MaxItems
Array$(a) = MID$(STR$(a),2)
next a
3. Jumble them up as much as you want :
for a = 1 TO 1000
Pointer1 = RND(_MaxItems)
Pointer2 = RND(_MaxItems)
swap Array$(Pointer1),Array$(Pointer2)
next a
Voila !! (French for "there's a bug here somewhere but I haven't found it yet)
Phil
Try this:
' will run "as is"
COMPILE 0,_dimmedVarsOnly
DIM gEnd
DIM gCount
DIM gA(320)
END GLOBALS
'
LOCAL FN buildWind
WINDOW 1,"Fill random array",(0,0)(500,500),_doczoom
END FN
'
LOCAL FN checkArray
DIM i
gEnd = _true
FOR i = 1 TO 320
LONG IF gA(i) = 0
gEnd = _false
i = 321
END IF
NEXT
END FN
'
LOCAL FN fillArray
DIM a
a = RND(320)
LONG IF gA(a) = 0
gA(a) = gCount
INC(gCount)
END IF
END FN
'
"MAIN"
DIM i
DIM a$
FN buildWind
gCount = 1
gEnd = _false
WHILE gEnd = _false
FN fillArray
FN checkArray
WEND
FOR i = 1 TO 320
PRINT "(";gA(i);")";
NEXT
PRINT
INPUT "Enter anything to end";a$
END
Tedd
This code does _almost_ what Jonathan2 suggests, but by swapping every element with a randomly chosen element, it's all done in one pass.
DIM gRandomArray(320)
FOR r = 1 TO 320
gRandomArray(r)=r
NEXT
LOCAL FN randomizeArray
FOR r = 1 TO 320
SWAP(gRandomArray(r),gRandomArray(RANDOM(320)
NEXT
END FN
Using an int array makes it fast, then you can use members of this array as pointers to your string array.
FOR r = 1 to 320
PRINT files$(gRandomArray(r))
NEXT
Jay
Try this function that is really drawing randomly without replacement..
LOCAL FN randomList
DIM I
DIM finish
DIM index
DIM listLength
DIM A(320)
'
listLength=320
finish=listLength
FOR I = 1 TO listLength
A(I)=I
NEXT
FOR I = 1 TO listLength
index=RND(finish)
SWAP A(index),A(finish)
DEC(finish)
NEXT
'
END FN
Steve
