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 (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.
_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
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 generatorSince [_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 start-up time.
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 FNI 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?
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 a3. 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 aVoila !! (French for "there's a bug here somewhere but I haven't found it yet)
'--- 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
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 FNUsing 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
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