Jump to content
IGNORED

List Compare Alogrithm?


Larry

Recommended Posts

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!

Link to comment
Share on other sites

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 0
This 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 a
d and b work the same way

This assumes there are no duplicates in a or b sets

In C you would use exit to break out of the inner loop



dim a[x], b[y] : REM sets
dim 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 here
for i=0 to x step 1 :REM counter for set a

c = 0 :REM clear flag indicating a match between sets for first array
for 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 by JamesD
Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 by Shawn Jefferson
Link to comment
Share on other sites

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).

Link to comment
Share on other sites

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 by mono
  • Like 1
Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...