+Larry Posted November 6, 2015 Share Posted November 6, 2015 Has anyone seen a program or an algorithm (preferably in BASIC) that compares two lists to find the differences? What subset is in both lists (A and B)? What subset is in A but not B? What subset is in B but not A? Thanks, Larry Oops -- see I butchered ALGORITHM! Quote Link to comment Share on other sites More sharing options...
fujidude Posted November 6, 2015 Share Posted November 6, 2015 Don't happen to have any. It sounds like a good programming project for you perhaps. As to the topic title, if you asked Al nicely, he might be willing to change it. Quote Link to comment Share on other sites More sharing options...
JamesD Posted November 6, 2015 Share Posted November 6, 2015 (edited) I'd start with sorted lists and then you can keep track of where to start searching for the next iteration.The basic algorithm involves nested loops.k starts the inner loop with where the last loop found a match +1, remove k if you don't have sorted sets and start the inner loop at 0This is just pseudo code without any optimizations.Make the larger set indexed by the inner loop. Every element in c that is equal to one matches an element in set a, everything zero in c is unique in set ad and b work the same wayThis assumes there are no duplicates in a or b setsIn C you would use exit to break out of the inner loopdim a[x], b[y] : REM setsdim c[x], d[y] : REM flags for set matches. zeros are no match, ones are a match k=0 REM set values in arrays a, b, and clear flag array d herefor i=0 to x step 1 :REM counter for set a c = 0 :REM clear flag indicating a match between sets for first arrayfor j=k to y step 1 :REM counter for set b if a = b[j] then c= 1: d[j]= 1 : j=y : k=j+1: REM set flags, exit loop if found and start next inner loop at next array element next j next i Edited November 6, 2015 by JamesD Quote Link to comment Share on other sites More sharing options...
+Larry Posted November 6, 2015 Author Share Posted November 6, 2015 Thanks. Yes, basically what I had in mind. I've done a few similar things, but not exactly like this. I remembered that I needed to do something similar when I doing a little TBXL project some years ago. I need to research that one in my ATR's. I'm probably going to use Basic XL or XE since they support string arrays and this seems to lend itself to that. But I had thought I might get lucky, and someone else would have plowed this field before. Also hoped that I might find something easily on the web, but didn't find anything remotely close. -Larry Quote Link to comment Share on other sites More sharing options...
JamesD Posted November 7, 2015 Share Posted November 7, 2015 I would have done it in Atari BASIC but I didn't grow up with an Atari and have no idea of how to deal with the arrays. Quote Link to comment Share on other sites More sharing options...
Shawn Jefferson Posted November 7, 2015 Share Posted November 7, 2015 (edited) I'd be tempted to brute force it. I was typing out a long explanation... but basically, I'd just run two loops checking one list against the other... if the lists aren't two large it might not be too slow. If they are large, you would need to start optimizing by pre-sorting, removing duplicates, etc... Edited November 7, 2015 by Shawn Jefferson Quote Link to comment Share on other sites More sharing options...
fujidude Posted November 7, 2015 Share Posted November 7, 2015 I would have done it in Atari BASIC but I didn't grow up with an Atari and have no idea of how to deal with the arrays. If you plan to redistribute your program in some way, you might want to consider Turbo BASIC XL. It is free, and also offers compiler and run time. On the other hand, a lot of people are emulating these days and have access to BASIC XL/XE (well, and so do a fair number of hardware users too I suppose). Quote Link to comment Share on other sites More sharing options...
mono Posted November 7, 2015 Share Posted November 7, 2015 (edited) If you have both sets sorted ascending there is no need to use nesting loops. There is enough to take separate iterators (AI, BI) for both sets and test if items pointed by iterators (A,B) are lesser, greater or equal. Following BASIC code does all. ;init input sets 10 DIM A$(128),B$(128) 20 A$="ABEGHLOPRTVWXZ" 30 B$="BCDFHJKLMNPQSUWXY" ;init flag map 40 DIM F$(128) 50 FOR I=1 TO 128:F$(I,I)="-":NEXT I ;and set iterators 60 AI=1:BI=1 ;calculate item index in flag map 70 A=255:B=255 80 IF AI<=LEN(A$) THEN A=1+ASC(A$(AI,AI)) 90 IF BI<=LEN(B$) THEN B=1+ASC(B$(BI,BI)) ;check set(s) membership 100 IF A<B THEN F$(A,A)="A":AI=AI+1:GOTO 70 110 IF B<A THEN F$(B,B)="B":BI=BI+1:GOTO 70 120 IF A<255 THEN F$(A,A)="*":AI=AI+1:BI=BI+1:GOTO 70 ;print input sets and flag map result 130 ? A$ 140 ? B$ 150 ? F$ I'm using text arrays (A$,B$) as input sets and F$ for a flag map, so array indexes are increased by 1 (for technical purposes). "A" in flag map marks element belongs exclusivelly to set A, "B" - to set B, "*" - to both of sets and "-" marks elements not occured in both sets. Edit: A=255 or B=255 marks end of input set. SETS.LST Edited November 7, 2015 by mono 1 Quote Link to comment Share on other sites More sharing options...
+Larry Posted November 7, 2015 Author Share Posted November 7, 2015 Thanks very much, Mono! I'll take a look at this immediately. -Larry Quote Link to comment Share on other sites More sharing options...
+Larry Posted November 11, 2015 Author Share Posted November 11, 2015 This turned out to be a lot easier than I was originally trying to make it. My goal was a utility to compare two ATR file directories to find duplicate or missing files. Basically, I made a string "map" of each disk, and marked each file as unique, with a max of 64 files for each MyDos image. Then I put the file directory entries in two BXL/BXE string arrays and used a loop to find any titles that matched. If they matched, then I changed the maps to show that they were duplicates. I used "1", "2", and "3" for the two map entries, then after the comparisons I printed the directory contents of the two ATR's and showed a (DUP.) next to each file found on both images. -Larry Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.