Shuffling An Array

Anything Sinclair ZX Basic related; history, development, tips - differences between BASIC on the ZX80 and ZX81
MrVertigo
Posts: 105
Joined: Fri May 27, 2022 9:06 pm

Shuffling An Array

Post by MrVertigo »

I’ve been trying to shuffle a string array using ZX81 BASIC. Is this method I’ve come up with over complicated? I begin with a string array in memory called W$, which contains five elements. At the end, I have a string array called J$, which contains the same five elements, randomly shuffled. This is how I get there:

Code: Select all

10 Dim J$(5,9)
20 Dim S$(5)
30 LET A$=“12345”
40 FOR N=5 TO 1 STEP -1
50 LET X=INT (RND*5)+1
60 LET S$(N)=A$(X)
70 LET B$=A$(1 TO X-1)
80 LET C$=A$(X+1 TO LEN A$)
90 LET A$=B$+C$
100 NEXT N
110 FOR M=1 TO 5
120 LET Y=VAL S$(M)
130 LET J$(M)=W$(Y)
140 NEXT M
Is there a better and/or simpler way to do this? It seems cumbersome. (I know I also need RAND in there to make it more random).
MrVertigo
Posts: 105
Joined: Fri May 27, 2022 9:06 pm

Re: Shuffling An Array

Post by MrVertigo »

Coming at it from another angle, here is an attempt using a flag array, still with W$ in memory containing five elements, and again ending with J$ as the shuffled version of W$:

Code: Select all

5  DIM J$(5,9)
10 DIM A(5)
20 DIM F(5)
25 DIM J(5)
30 FOR N=1 TO 5
40 LET X=INT (RND*5)+1
50 IF F(X)=1 THEN GOTO 40
60 IF F(X)=0 THEN LET F(X)=1
70 LET A(N)=X
80 NEXT N
90 FOR M=1 TO 5
100 LET Y= A(M)
110 LET J$(M)= W$(Y)
120 NEXT M
Last edited by MrVertigo on Wed May 17, 2023 2:03 am, edited 1 time in total.
User avatar
Flatulentia
Posts: 93
Joined: Sun May 14, 2023 3:58 pm
Location: Cambridgeshire, UK

Re: Shuffling An Array

Post by Flatulentia »

That looks much tidier and is far more humanly readable. Have you compared execution times?
ZX81 with ZiLOG Z84 CMOS Z80, 32KB battery-backed Toshiba 55257 SRAM with charge status LED, Wilf's "Why Wait?" mod and switch-mode 5V regulator. 50/60Hz mode switch, composite video output with Zigg's back porch mod and 1080p60 HDMI output.
MrVertigo
Posts: 105
Joined: Fri May 27, 2022 9:06 pm

Re: Shuffling An Array

Post by MrVertigo »

I’d originally avoided the flag method because I thought the execution time would be longer if it got stuck in a GOTO loop, but with five elements execution is about the same speed for both methods. Maybe the flag method would be slower with more elements, if it kept getting stuck returning the same random number. But is my first method limited to a maximum of nine array elements maybe, because of the string method?

With five elements the flag method takes about 2.5 seconds. With twenty elements it takes about 8 seconds, so it soon starts to struggle.
User avatar
Flatulentia
Posts: 93
Joined: Sun May 14, 2023 3:58 pm
Location: Cambridgeshire, UK

Re: Shuffling An Array

Post by Flatulentia »

I'd be joining in this experiment if I hadn't misplaced my ZX81 PSU. A "new" one should be arriving any day now. 8-)
ZX81 with ZiLOG Z84 CMOS Z80, 32KB battery-backed Toshiba 55257 SRAM with charge status LED, Wilf's "Why Wait?" mod and switch-mode 5V regulator. 50/60Hz mode switch, composite video output with Zigg's back porch mod and 1080p60 HDMI output.
User avatar
XavSnap
Posts: 1940
Joined: Sat May 10, 2008 4:23 pm
Location: 'Zx81 France' Fb group.

Re: Shuffling An Array

Post by XavSnap »

Hi,
The better way to shuffling an array is to reduce its length if the value is selected...
Only 5 loops to get a string.
Have a look to : https://www.sinclairzxworld.com/viewtop ... 938#p47938

The int(RND*5)+1, and put a space on the value, was a very bad purpose and loop many time on the same value !
RND=1,2,2,5,1,1,5,3,2,1,3,1,3,3,4 ( 15 times )


This purpose only chose unselected values: 4,2,3,1,5 ( 5 times )

Code: Select all

   100 LET P=6
   110 LET CN=0
   112 LET T=13*P
   115 DIM C(T)
   
   120  FOR N=1 TO T
   150  LET C(N)=N
   170  NEXT N

  7000 LET V=INT ((RND*T)+1)
  7010 LET CN=CN+1
  7050 LET R=C(V)
  7100 IF V<>T THEN LET C(V)=C(T)
  7110 LET T=T-1
  7120 PRINT R;";";
  7130 IF T<>0 THEN GOTO 7000
  7200 PRINT "END OF ";CN;" VALUES"
  
Strings: (about 3 seconds for 5 values)

Code: Select all

10 LET S$=""
20 LET A$="12345"
23 LET L=LEN A$
26 LET B$=A$
30 LET T=L+1
40 LET T=T-1
50 LET X=INT (RND*T)+1
60 LET S$=S$+B$(X)
65 IF X=1 THEN LET B$=B$(X+1 TO)
70 IF X=L THEN LET B$=B$(1 TO X-1)
80 IF X>1 AND X<L THEN LET B$=B$(1 TO X-1)+B$(X+1 TO)
90 IF T>1 THEN GOTO 40
100 PRINT "VALUE : ";S$
(about 6 seconds for 20 values)
20 LET A$="12345678901234567890"
(about 12 seconds for 40 values)
(about 24 seconds for 80 values...)

... in slow mode ...

But no more wasted loop !
With a ramdom value, it will take between 40 and 60 seconds per shuffling process.
Xavier ...on the Facebook groupe : "Zx81 France"(fr)
MrVertigo
Posts: 105
Joined: Fri May 27, 2022 9:06 pm

Re: Shuffling An Array

Post by MrVertigo »

This looks promising!
MrVertigo
Posts: 105
Joined: Fri May 27, 2022 9:06 pm

Re: Shuffling An Array

Post by MrVertigo »

Yes, that’s brilliant. Line 7100 is ingenious. I could never have come up with that.

So for my original purpose, all I need to do is DIM J(5) at the beginning, then insert a line after 7050 to build an array of the random numbers: LET J(CN)= R.

Thank you!
User avatar
XavSnap
Posts: 1940
Joined: Sat May 10, 2008 4:23 pm
Location: 'Zx81 France' Fb group.

Re: Shuffling An Array

Post by XavSnap »

Better, 8 seconds...
(String 40 characters)

Code: Select all

10 LET S$=""
20 LET A$="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmn"
23 LET L=LEN A$
26 LET B$=A$
30 LET T=L+1
40 LET T=T-1
50 LET X=INT (RND*T)+1
60 LET S$=S$+B$(X)
70 LET B$(X)=B$(T)
80 IF T>1 THEN GOTO 40
100 PRINT "VALUE : ";S$
Use 'CODE' function to get integer 0 to 63.
Xavier ...on the Facebook groupe : "Zx81 France"(fr)
MrVertigo
Posts: 105
Joined: Fri May 27, 2022 9:06 pm

Re: Shuffling An Array

Post by MrVertigo »

How do you get the lower-case letters in the string on ZX81?
Post Reply