FB II Compiler

PG PRO

Debugging

Memory

System

Mathematics

Resources

Disk I/O

Windows

Controls

Menus

Mouse

Keyboard

Text

Fonts

Drawing

Sound

Clipboard

Printing

Communication

ASM

Made with FB

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 (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
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 start-up 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