Random BASIC shuffling revisited.

In a previous article, I wrote a BASIC program that simulated pulling marbles out of a bag. I described my thought process, including how I initially thought I would have to randomize the virtual marbles in the virtual bag. I realized this would be unnecessary, but still offered a demonstration of a simple way to randomly shuffle an array of items, as one might do with a deck of playing cards:

NOTE: I had a bug on line 40 and was only counting from 0 to 24 (25 letters) instead of 0 to 25 (26 letters of the alphabet). Fixed here:

10 REM shuffle.bas
20 REM CREATE ALPHABET ARRAY
30 DIM A$(25)
40 FOR A=0 TO 25
50 A$(A)=CHR$(65+A)
60 NEXT

70 REM DISPLAY ARRAY
80 GOSUB 190

90 REM SWAP EACH ONE RANDOMLY
100 FOR A=0 TO 25
110 S=RND(26)-1
120 SV$=A$(S)
130 A$(S)=A$(A)
140 A$(A)=SV$
150 NEXT

160 REM DISPLAY ARRAY
170 GOSUB 200

180 END

190 REM DISPLAY ARRAY
200 FOR A=0 TO 25
210 PRINT A$(A);
220 NEXT
230 PRINT
240 RETURN

That would display the 26 letters of the alphabet, then shuffle them and display the results. My shuffle routine went through each position (0 to 25) and swapped it with another random position (0 to 25).

However, adding to the flaw in the simulation that article was about, there was another flaw in my shuffling examples.

In a comment, James Jones added:

Actually, to get a random shuffle with all permutations equally likely, you have to do something like this:

FOR i:= 1 to n-1
j:=i+INT(RND(n+1-i))
temp:=a(i)\a(i):=a(j)\a(j):=temp
NEXT i

i.e. at each step you swap a(i) with a(j) where j is a randomly chosen number between i and n inclusive.

James Jones

His program logic uses ‘n’ as the number of elements we are shuffling, which is 26 for my example.

The for/next loop of ‘i’ will count from 1 to n-1, so 1 to 25 in this example.

‘j’ will be the randomly selected target element to swap with the element at ‘i’. It is chosen using the random number generator. I it looks like his rnd(26) would return 0-25, so the result of j for each count of 1 to n-1 would be

i = 1 -> j = 1 + rnd(26 + 1 - 1) -> j = 1 + rnd(26) -> j = 1 to 26
i = 2 -> j = 2 + rnd(26 + 1 - 2) -> j = 2 + rnd(25) -> j = 2 to 26
i = 3 -> j = 3 + rnd(26 + 1 - 3) -> j = 3 + rnd(24) -> j = 3 to 26
...
i = 23 -> j = 23 + rnd(26 + 1 - 23) -> j = 23 + rnd(4) -> j = 23 to 26
i = 24 -> j = 24 + rnd(26 + 1 - 24) -> j = 24 + rnd(3) -> j = 24 to 26
i = 25 -> j = 25 + rnd(26 + 1 - 25) -> j = 25 + rnd(2) -> j = 25 to 26

It then uses a temporary variable to swap the position of a(i) with a(j).

My original version randomly swapped each position with any of the 26 positions. James’ code swaps each position with only positions after it.

With apologies to James for down-porting his logic to Microsoft BASIC, here is my original example updated to take this approach. To keep it as close to my original example as possible, I’ll adjust my array to use 1-26 (instead of 0-25). Color BASIC arrays are base-0, but for this example we’ll just ignore the zero. I’ll try to bold the changes from the original.

10 REM jjshuffle.bas
20 REM CREATE ALPHABET ARRAY
25 N=26
30 DIM A$(N)
40 FOR A=1 TO N
50 A$(A)=CHR$(64+A)
60 NEXT

70 REM DISPLAY ARRAY
80 GOSUB 190

90 REM SWAP EACH ONE RANDOMLY
100 FOR I=1 TO N-1
110 J=I+INT(RND(N+1-I)-1)
120 TEMP$=A$(I)
130 A$(I)=A$(J)
140 A$(J)=TEMP$
150 NEXT

160 REM DISPLAY ARRAY
170 GOSUB 200

180 END

190 REM DISPLAY ARRAY
200 FOR A=1 TO N
210 PRINT A$(A);
220 NEXT
230 PRINT
240 RETURN

And to convert this back to my first example using base-0 arrays:

10 REM shuffle2.bas
20 REM CREATE ALPHABET ARRAY
30 DIM A$(25)
40 FOR A=0 TO 24
50 A$(A)=CHR$(65+A)
60 NEXT

70 REM DISPLAY ARRAY
80 GOSUB 190

90 REM SWAP EACH ONE RANDOMLY
100 FOR A=0 TO 25
110 S=A+RND(26-A)-1
115 PRINT A,S
120 SV$=A$(S)
130 A$(S)=A$(A)
140 A$(A)=SV$
150 NEXT

160 REM DISPLAY ARRAY
170 GOSUB 200

180 END

190 REM DISPLAY ARRAY
200 FOR A=0 TO 25
210 PRINT A$(A);
220 NEXT
230 PRINT
240 RETURN

Any other random thoughts?

Until next time…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.