e.g. S1 = {1,2,3}
This is identical to the set {3,1,1,2,3,2} because repeated elements don't count, and neither does the order in which they occur.
The first language I learned (back in the nineties) was Turbo Pascal, which had sets built in. Gambas doesn't have native support for them, so I wrote a few simple routines to handle the most commonly used set operations and relations.
There is more than one way of implementing the routines, but I've chosen the "bit vector" approach, which is quite efficient and easy to understand. The basic idea is to use an array of boolean the elements of which (true/false) indicate the presence or absence of an item in the set (Note : I have restricted set elements to integers in these routines).
For example, consider the set operation of Intersection, which takes sets S1, S2, and returns a third set the elements of which are common to both:
S1 = {1,2,3,4,5}
S2 = {4,5,6,7,8}
So S1 Intersection S2 = {4,5}
The simplest operation is adding an element to the set. To do this, declare an array of boolean large enough to hold the highest value in your set(s) + 1 (+ 1, because array indexing starts at zero). All elements in the arrays should initially be set to False, which signifies an empty set, and to add the elements of S1 above to this initially empty set use the following loop :
Code: Select all
Dim S1 As New Boolean[9]
Dim i As Integer
For i = 1 to 5
S1[i] = True
Next
Code: Select all
For i = 0 to 9
If s1[i] and s2[i] Then
result[i] = True
Endif
Next
Code: Select all
'Set Routines
'clear/initialise set
SUB set_clear(s AS boolean[])
s.Fill(FALSE)
END
'add element to a set
SUB set_incl(n AS integer, s AS boolean[])
s[n] = TRUE
END
'remove element from set
SUB set_excl(n AS integer, s AS boolean[])
s[n] = FALSE
END
'Is an element in the set?
FUNCTION set_in(n AS integer, s AS boolean[]) AS boolean
RETURN s[n]
END
'cardinality (return number of elements in set)
FUNCTION set_card(s AS boolean[]) AS integer
DIM n AS integer,i AS integer
n = 0
FOR i = 0 TO s.Max
IF s[i] = TRUE THEN
INC n
ENDIF
NEXT
RETURN n
END
'intersection
SUB set_inter(s1 AS boolean[],s2 AS boolean[],result AS boolean[])
DIM i AS integer
FOR i = 0 TO s1.Max
IF s1[i] and s2[i] THEN
result[i] = TRUE
ENDIF
NEXT
END
'union
SUB set_union(s1 AS boolean[],s2 AS boolean[],result AS boolean[])
DIM i AS integer
FOR i = 0 TO s1.Max
IF s1[i] or s2[i] THEN
result[i] = TRUE
ENDIF
NEXT
END
'difference (s1 - s2)
SUB set_diff(s1 AS boolean[],s2 AS boolean[],result AS boolean[])
DIM i AS integer
FOR i = 0 TO s1.Max
IF s1[i] and not s2[i] THEN
result[i] = TRUE
ENDIF
NEXT
END
'symmetric difference (result is union(s1,s2) - inter(s1,s2))
SUB set_symdiff(s1 AS boolean[],s2 AS boolean[],result AS boolean[])
DIM i AS integer
FOR i = 0 TO s1.Max
IF s1[i] xor s2[i] THEN
result[i] = TRUE
ENDIF
NEXT
END
' are the sets equal?
FUNCTION set_isequal(s1 AS boolean[],s2 AS boolean[]) AS boolean
DIM i AS integer
DIM equal AS boolean
equal = TRUE
FOR i = 0 TO s1.Max
IF s1[i] <> s2[i] THEN
equal = FALSE
BREAK
ENDIF
NEXT
RETURN equal
END
'Is set s1 a subset of set s2?
FUNCTION set_issubset(s1 AS boolean[],s2 AS boolean[]) AS boolean
DIM subset AS boolean
DIM i AS integer
subset = TRUE
FOR i = 0 TO s1.Max
IF NOT ((s1[i] AND s2[i]) = s1[i]) THEN
subset = FALSE
BREAK
ENDIF
NEXT
RETURN subset
END
'show a set
SUB set_show(s AS boolean[])
DIM i AS integer
FOR i = 0 TO s.Max
IF s[i] = TRUE THEN
PRINT i;;
ENDIF
NEXT
PRINT
END
Code: Select all
#!/usr/bin/env gbs3
INCLUDE "sets.gbs3"
CONST SIZE AS byte = 10
DIM A AS NEW boolean[SIZE]
DIM B AS NEW boolean[SIZE]
DIM C AS NEW boolean[SIZE]
DIM result AS NEW boolean[SIZE]
DIM i AS integer
'initialize
set_clear(A)
set_clear(B)
set_clear(C)
' A = {1,2,3,4,5,6,7}
' B = {4,5,6}
' C = {6,7,8,9}
' fill sets
FOR i = 1 TO 7
set_incl(i, A)
NEXT
FOR i = 4 TO 6
set_incl(i, B)
NEXT
FOR i = 6 TO 9
set_incl(i, C)
NEXT
'show sets
PRINT "A: ";
set_show(A)
PRINT "B: ";
set_show(B)
PRINT "C: ";
set_show(C)
'intersection
print "Intersection of A & B: ";
set_inter(A, B, result)
set_show(result)
'union
PRINT "Union of B & C: ";
set_union(B, C, result)
set_show(result)
'difference between B & C (B - C)
set_clear(result)
PRINT "Difference between C & A (C - A): ";
set_diff(C, A, result)
set_show(result)
'symmetric difference between A & C
set_clear(result)
PRINT "Symmetric difference of A & C: ";
set_symdiff(A, C, result)
set_show(result)
'subset; is C a subset of A?
PRINT "Is C a subset of A? ";
PRINT IF(set_issubset(C, A), "True", "False")
PRINT "Is B a subset of A? ";
PRINT IF(set_issubset(B, A), "True", "False")
' how many elements in A?
PRINT "Set A has ";
PRINT set_card(A);
PRINT " elements"
' remove elements 1..5 from A
FOR i = 1 TO 5
set_excl(i, A)
NEXT
PRINT "Removing elements 1..5 from A..."
PRINT "A: ";
set_show(A)
' add elements 8,9 to A
PRINT "Adding elements 8 & 9 to A..."
PRINT "A: ";
set_incl(8, A)
set_incl(9, A)
set_show(A)
'equal sets
PRINT "Does A = C?: ";
PRINT IF(set_isequal(A, C), "True", "False")
PRINT "Does A = B?: ";
PRINT IF(set_isequal(A, B), "True", "False")
Code: Select all
#!/usr/bin/env gbs3
include "sets.gbs3"
'Find the probability of seeing all 6 numbers in 6 rolls of a die.
RANDOMIZE
CONST TRIALS AS integer = 100000
DIM uniques AS NEW boolean[7]
DIM i,j,roll,n,success AS integer
success = 0
FOR j = 1 TO TRIALS
FOR i = 1 TO 6
roll = rand(1,6)
set_incl(roll, uniques)
NEXT
IF set_card(uniques) = 6 THEN
INC success
ENDIF
' reset for next trial
set_clear(uniques)
NEXT
PRINT "Probability = "; success/TRIALS
P.S. For more info on sets see here and here.