Set
You are encouraged to solve this task according to the task description, using any language you may know.
Data Structure
This illustrates a data structure, a means of storing data within a program.
A set is a collection of elements, without duplicates and without order.
Show each of these set operations:
- Set creation
- Test m ∈ S -- "m is an element in set S"
- A ∪ B -- union; a set of all elements either in set A or in set B.
- A ∩ B -- intersection; a set of all elements in both set A and set B.
- A ∖ B -- difference; a set of all elements in set A, except those in set B.
- A ⊆ B -- subset; true if every element in set A is also in set B.
- A = B -- equality; true if every element of set A is in set B and vice-versa.
As an option, show some other set operations. (If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.) As another option, show how to modify a mutable set.
One might implement a set using an associative array (with set elements as array keys and some dummy value as the values). One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bitwise binary operators). The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.
- See also
- Array
- Associative array: Creation, Iteration
- Collections
- Compound data type
- Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
- Linked list
- Queue: Definition, Usage
- Set
- Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
- Stack
Ada
This solution uses the generic Ordered_Sets package from the Ada.Containers standard library, which internally is based on red-black trees. An alternative hash-based solution could use the Hashed_Maps package from Ada.Containers.
<lang Ada>with Ada.Text_IO, Ada.Containers.Ordered_Sets;
procedure Set_Demo is
package CS is new Ada.Containers.Ordered_Sets(Character); use CS; package IO renames Ada.Text_IO;
-- helper functions for string to something conversion, and vice versa function To_Set(S: String) return Set is Result: Set; begin for I in S'Range loop begin Result.Insert(S(I)); -- raises Constraint_Error if S(I) is already in Result exception when Constraint_Error => null; end; end loop; return Result; end To_Set;
function Image(S: Set) return String is C: Character; T: Set := S; begin if T.Is_Empty then return ""; else C:= T.First_Element; T.Delete_First; return C & Image(T); end if; end Image;
function Image(C: Ada.Containers.Count_Type) return String renames Ada.Containers.Count_Type'Image;
S1, S2: Set;
begin -- main program
loop S1 := To_Set(Ada.Text_IO.Get_Line); exit when S1 = To_Set("quit!"); S2 := To_Set(Ada.Text_IO.Get_Line); IO.Put_Line("Sets [" & Image(S1) & "], [" & Image(S2) & "] of size" & Image(S1.Length) & " and" & Image(S2.Length) & "."); IO.Put_Line("Intersection: [" & Image(Intersection(S1, S2)) & "],"); IO.Put_Line("Union: [" & Image(Union(S1, S2)) & "],"); IO.Put_Line("Difference: [" & Image(Difference(S1, S2)) & "],"); IO.Put_Line("Symmetric Diff: [" & Image(S1 xor S2) & "],"); IO.Put_Line("Subset: " & Boolean'Image(S1.Is_Subset(S2)) & ", Equal: " & Boolean'Image(S1 = S2) & "."); end loop;
end Set_Demo; </lang>
- Output:
set demo Sets [est], [demo] of size 3 and 4. Intersection: [e], Union: [demost], Difference: [st], Symmetric Diff: [dmost], Subset: FALSE, Equal: FALSE. quit!
AutoHotkey
<lang AutoHotkey>test(Set,element){ for i, val in Set if (val=element) return true return false }
Union(SetA,SetB){ SetC:=[], Temp:=[] for i, val in SetA SetC.Insert(val), Temp[val] := true for i, val in SetB if !Temp[val] SetC.Insert(val) return SetC }
intersection(SetA,SetB){ SetC:=[], Temp:=[] for i, val in SetA Temp[val] := true for i, val in SetB if Temp[val] SetC.Insert(val) return SetC }
difference(SetA,SetB){ SetC:=[], Temp:=[] for i, val in SetB Temp[val] := true for i, val in SetA if !Temp[val] SetC.Insert(val) return SetC }
subset(SetA,SetB){ Temp:=[], A:=B:=0 for i, val in SetA Temp[val] := true , A++ for i, val in SetB if Temp[val]{ B++ IfEqual, A, %B%, return 1 } return 0 }
equal(SetA,SetB){ return (SetA.MaxIndex() = SetB.MaxIndex() && subset(SetA,SetB)) ? 1: 0 }</lang> Examples:<lang AutoHotkey>A:= ["apple", "cherry", "elderberry", "grape"] B:= ["banana", "cherry", "date", "elderberry", "fig"] C:= ["apple", "cherry", "elderberry", "grape", "orange"] D:= ["apple", "cherry", "elderberry", "grape"] E:= ["apple", "cherry", "elderberry"] M:= "banana"
Res = ( A:= ["apple", "cherry", "elderberry", "grape"] B:= ["banana", "cherry", "date", "elderberry", "fig"] C:= ["apple", "cherry", "elderberry", "grape", "orange"] D:= ["apple", "cherry", "elderberry", "grape"] E:= ["apple", "cherry", "elderberry"] M:= "banana"
)
Res .= "`nM is " (test(A,M)?"":"not ") "an element of Set A" Res .= "`nM is " (test(B,M)?"":"not ") "an element of Set B"
Res .= "`nUnion(A,B) = " for i, val in Union(A,B) Res.= (A_Index=1?"`t":", ") val
Res .= "`nintersection(A,B) = " for i, val in intersection(A,B) Res.= (A_Index=1?"`t":", ") val
Res .= "`ndifference(A,B) = " for i, val in difference(A,B) Res.= (A_Index=1?"`t":", ") val
Res .= "`n`nA is " (subset(A,C)?"":"not ") "a subset of Set C" Res .= "`nA is " (subset(A,D)?"":"not ") "a subset of Set D" Res .= "`nA is " (subset(A,E)?"":"not ") "a subset of Set E"
Res .= "`n`nA is " (equal(A,C)?"":"not ") "a equal to Set C" Res .= "`nA is " (equal(A,D)?"":"not ") "a equal to Set D" Res .= "`nA is " (equal(A,E)?"":"not ") "a equal to Set E"
MsgBox % Res</lang>
- Output:
A:= ["apple", "cherry", "elderberry", "grape"] B:= ["banana", "cherry", "date", "elderberry", "fig"] C:= ["apple", "cherry", "elderberry", "grape", "orange"] D:= ["apple", "cherry", "elderberry", "grape"] E:= ["apple", "cherry", "elderberry"] M:= "banana" M is not an element of Set A M is an element of Set B Union(A,B) = apple, cherry, elderberry, grape, banana, date, fig intersection(A,B) = cherry, elderberry difference(A,B) = apple, grape A is a subset of Set C A is a subset of Set D A is not a subset of Set E A is not a equal to Set C A is a equal to Set D A is not a equal to Set E
BBC BASIC
The sets are represented as 32-bit integers, which means that the maximum number of elements is 32. <lang bbcbasic> DIM list$(6)
list$() = "apple", "banana", "cherry", "date", "elderberry", "fig", "grape" setA% = %1010101 PRINT "Set A: " FNlistset(list$(), setA%) setB% = %0111110 PRINT "Set B: " FNlistset(list$(), setB%) elementM% = %0000010 PRINT "Element M: " FNlistset(list$(), elementM%) ' IF elementM% AND setA% THEN PRINT "M is an element of set A" ELSE PRINT "M is not an element of set A" ENDIF IF elementM% AND setB% THEN PRINT "M is an element of set B" ELSE PRINT "M is not an element of set B" ENDIF PRINT '"The union of A and B is " FNlistset(list$(), setA% OR setB%) PRINT "The intersection of A and B is " FNlistset(list$(), setA% AND setB%) PRINT "The difference of A and B is " FNlistset(list$(), setA% AND NOT setB%) IF (setA% AND setB%) = setA% THEN PRINT '"Set A is a subset of set B" ELSE PRINT '"Set A is not a subset of set B" ENDIF IF setA% = setB% THEN PRINT "Set A is equal to set B" ELSE PRINT "Set A is not equal to set B" ENDIF END DEF FNlistset(list$(), set%) LOCAL i%, o$ FOR i% = 0 TO 31 IF set% AND 1 << i% o$ += list$(i%) + ", " NEXT = LEFT$(LEFT$(o$))</lang>
- Output:
Set A: apple, cherry, elderberry, grape Set B: banana, cherry, date, elderberry, fig Element M: banana M is not an element of set A M is an element of set B The union of A and B is apple, banana, cherry, date, elderberry, fig, grape The intersection of A and B is cherry, elderberry The difference of A and B is apple, grape Set A is not a subset of set B Set A is not equal to set B
C
Building a set highly depends on the datatype and use case. For example, a set of string could be implemented by hash table, sort tree or trie, but if all sets are known to have very few number of elements, it might be best to use just flat arrays. There isn't, and shouldn't be, an all-purpose set type for C.
A frequent use of set is that of small, non-negative integers, implemented as a bit field as shown below. <lang c>#include <stdio.h>
typedef unsigned int set_t; /* probably 32 bits; change according to need */
void show_set(set_t x, const char *name) { int i; printf("%s is:", name); for (i = 0; (1U << i) <= x; i++) if (x & (1U << i)) printf(" %d", i); putchar('\n'); }
int main(void) { int i; set_t a, b, c;
a = 0; /* empty set */ for (i = 0; i < 10; i += 3) /* add 0 3 6 9 to set a */ a |= (1U << i); show_set(a, "a");
for (i = 0; i < 5; i++) printf("\t%d%s in set a\n", i, (a & (1U << i)) ? "":" not");
b = a; b |= (1U << 5); b |= (1U << 10); /* b is a plus 5, 10 */ b &= ~(1U << 0); /* sans 0 */ show_set(b, "b");
show_set(a | b, "union(a, b)"); show_set(c = a & b, "c = common(a, b)"); show_set(a & ~b, "a - b"); /* diff, not arithmetic minus */ show_set(b & ~a, "b - a"); printf("b is%s a subset of a\n", !(b & ~a) ? "" : " not"); printf("c is%s a subset of a\n", !(c & ~a) ? "" : " not");
printf("union(a, b) - common(a, b) %s union(a - b, b - a)\n", ((a | b) & ~(a & b)) == ((a & ~b) | (b & ~a)) ? "equals" : "does not equal");
return 0; }</lang>
C++
C++ standard library contains a set class, which is a sorted container without duplicates and implemented as a binary tree. Additional set functionality can be implemented in terms of standard library algorithms.
C++11 standard library also contains unordered_set based on a hash table. However, algorithms like std::set_intersection etc take sorted ranges, so set-specific functions should be hand-rolled.
<lang cpp>
- include <set>
- include <iostream>
- include <iterator>
- include <algorithm>
namespace set_display { template <class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& set) {
os << '['; if (!set.empty()) { std::copy(set.begin(), --set.end(), std::ostream_iterator<T>(os, ", ")); os << *--set.end(); } return os << ']';
} }
template <class T> bool contains(const std::set<T>& set, const T& key) {
return set.count(key) != 0;
}
template <class T> std::set<T> set_union(const std::set<T>& a, const std::set<T>& b) {
std::set<T> result; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(result, result.end())); return result;
}
template <class T> std::set<T> set_intersection(const std::set<T>& a, const std::set<T>& b) {
std::set<T> result; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(result, result.end())); return result;
}
template <class T> std::set<T> set_difference(const std::set<T>& a, const std::set<T>& b) {
std::set<T> result; std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::inserter(result, result.end())); return result;
}
template <class T> bool is_subset(const std::set<T>& set, const std::set<T>& subset) {
return std::includes(set.begin(), set.end(), subset.begin(), subset.end());
}
int main() {
using namespace set_display; std::set<int> a{2, 5, 7, 5, 9, 2}; //C++11 initialization syntax std::set<int> b{1, 5, 9, 7, 4 }; std::cout << "a = " << a << '\n'; std::cout << "b = " << b << '\n';
int value1 = 8, value2 = 5; std::cout << "Set a " << (contains(a, value1) ? "contains " : "does not contain ") << value1 << '\n'; std::cout << "Set a " << (contains(a, value2) ? "contains " : "does not contain ") << value2 << '\n';
std::cout << "Union of a and b: " << set_union(a, b) << '\n'; std::cout << "Intersection of a and b: " << set_intersection(a, b) << '\n'; std::cout << "Difference of a and b: " << set_difference(a, b) << '\n';
std::set<int> sub{5, 9}; std::cout << "Set b " << (is_subset(a, b) ? "is" : "is not") << " a subset of a\n"; std::cout << "Set " << sub << ' ' << (is_subset(a, sub) ? "is" : "is not") << " a subset of a\n";
std::set<int> copy = a; std::cout << "a " << (a == copy ? "equals " : "does not equal ") << copy << '\n';
return 0;
} </lang>
Clojure
<lang clojure>(require 'clojure.set)
- sets can be created using the set method or set literal syntax
(def a (set [1 2 3 4])) (def b #{4 5 6 7})
(a 10) ; returns the element if it's contained in the set, otherwise nil
(clojure.set/union a b)
(clojure.set/intersection a b)
(clojure.set/difference a b)
(clojure.set/subset? a b)</lang>
CoffeeScript
This implements functions from the task, along with an iteration helper called "each". <lang coffeescript>
- For ad-hoc set features, it sometimes makes sense to use hashes directly,
- rather than abstract to this level, but I'm showing a somewhat heavy
- solution to show off CoffeeScript class syntax.
class Set
constructor: (elems...) -> @hash = {} for elem in elems @hash[elem] = true
add: (elem) -> @hash[elem] = true remove: (elem) -> delete @hash[elem] has: (elem) -> @hash[elem]? union: (set2) -> set = new Set() for elem of @hash set.add elem for elem in set2.to_array() set.add elem set intersection: (set2) -> set = new Set() for elem of @hash set.add elem if set2.has elem set minus: (set2) -> set = new Set() for elem of @hash set.add elem if !set2.has elem set is_subset_of: (set2) -> for elem of @hash return false if !set2.has elem true equals: (set2) -> this.is_subset_of(set2) and set2.is_subset_of this to_array: -> (elem for elem of @hash) each: (f) -> for elem of @hash f(elem) to_string: -> @to_array()
run_tests = ->
set1 = new Set("apple", "banana") # creation console.log set1.has "apple" # true (membership) console.log set1.has "worms" # false (membership)
set2 = new Set("banana", "carrots") console.log set1.union(set2).to_string() # [ 'apple', 'banana', 'carrots' ] (union) console.log set1.intersection(set2).to_string() # [ 'banana' ] (intersection) console.log set1.minus(set2).to_string() # [ 'apple' ] (difference)
set3 = new Set("apple") console.log set3.is_subset_of set1 # true console.log set3.is_subset_of set2 # false
set4 = new Set("apple", "banana") console.log set4.equals set1 # true console.log set4.equals set2 # false
set5 = new Set("foo") set5.add "bar" # add console.log set5.to_string() # [ 'foo', 'bar' ] set5.remove "bar" # remove console.log set5.to_string() # [ 'foo' ]
# iteration, prints apple then banana (order not guaranteed) set1.each (elem) -> console.log elem
run_tests() </lang>
Common Lisp
Common Lisp provides some set operations on lists. <lang lisp>(setf a '(1 2 3 4)) (setf b '(2 3 4 5))
(format t "sets: ~a ~a~%" a b)
- element
(loop for x from 1 to 6 do (format t (if (member x a) "~d ∈ A~%" "~d ∉ A~%") x))
(format t "A ∪ B: ~a~%" (union a b)) (format t "A ∩ B: ~a~%" (intersection a b)) (format t "A \\ B: ~a~%" (set-difference a b)) (format t (if (subsetp a b) "~a ⊆ ~a~%" "~a ⊈ ~a~%") a b)
(format t (if (and (subsetp a b) (subsetp b a)) "~a = ~a~%" "~a ≠ ~a~%") a b)</lang>
D
<lang d>void main() {
import std.stdio, std.algorithm, std.range;
// Not true sets, items can be repeated, but must be sorted. auto s1 = [1, 2, 3, 4, 5, 6].assumeSorted; auto s2 = [2, 5, 6, 3, 4, 8].sort(); // [2,3,4,5,6,8]. auto s3 = [1, 2, 5].assumeSorted;
assert(s1.canFind(4)); // Linear search. assert(s1.contains(4)); // Binary search. assert(s1.setUnion(s2).equal([1,2,2,3,3,4,4,5,5,6,6,8])); assert(s1.setIntersection(s2).equal([2, 3, 4, 5, 6])); assert(s1.setDifference(s2).equal([1])); assert(s1.setSymmetricDifference(s2).equal([1, 8])); assert(s3.setDifference(s1).empty); // It's a subset. assert(!s1.equal(s2));
auto s4 = [[1, 4, 7, 8], [1, 7], [1, 7, 8], [4], [7]]; const s5 = [1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8]; assert(s4.nWayUnion.equal(s5));
}</lang>
Dart
<lang d>void main(){
//Set Creation Set A = new Set.from([1,2,3]); Set B = new Set.from([1,2,3,4,5]); Set C = new Set.from([1,2,4,5]);
print('Set A = $A'); print('Set B = $B'); print('Set C = $C'); print(); //Test if element is in set int m = 3; print('m = 5'); print('m in A = ${A.contains(m)}'); print('m in B = ${B.contains(m)}'); print('m in C = ${C.contains(m)}'); print(); //Union of two sets Set AC = A.union(C); print('Set AC = Union of A and C = $AC'); print(); //Intersection of two sets Set A_C = A.intersection(C); print('Set A_C = Intersection of A and C = $A_C'); print(); //Difference of two sets Set A_diff_C = A.difference(C); print('Set A_diff_C = Difference between A and C = $A_diff_C'); print(); //Test if set is subset of another set print('A is a subset of B = ${B.containsAll(A)}'); print('C is a subset of B = ${B.containsAll(C)}'); print('A is a subset of C = ${C.containsAll(A)}'); print(); //Test if two sets are equal print('A is equal to B = ${B.containsAll(A) && A.containsAll(B)}'); print('B is equal to AC = ${B.containsAll(AC) && AC.containsAll(B)}');
}</lang>
- Output:
Set A = {1, 2, 3} Set B = {1, 2, 3, 4, 5} Set C = {1, 2, 4, 5} m = 5 m in A = true m in B = true m in C = false Set AC = Union of A and C = {1, 2, 3, 4, 5} Set A_C = Intersection of A and C = {1, 2} Set A_diff_C = Difference between A and C = {3} A is a subset of B = true C is a subset of B = true A is a subset of C = false A is equal to B = false B is equal to AC = true
EchoLisp
EchoLisp sets are lists, i.e the set of all sets is a proper subset of the set of all lists. Sets elements may be any object, including sets.
The set operations are: ∩ ∪ ⊆ / ∈ = ∆ × <lang lisp>
- use { } to read a set
(define A { 1 2 3 4 3 5 5}) → { 1 2 3 4 5 } ; duplicates are removed from a set
- or use make-set to make a set from a list
(define B (make-set ' ( 3 4 5 6 7 8 8))) → { 3 4 5 6 7 8 } (set-intersect A B) → { 3 4 5 } (set-intersect? A B) → #t ; predicate (set-union A B) → { 1 2 3 4 5 6 7 8 } (set-substract A B) → { 1 2 } (set-sym-diff A B) → { 1 2 6 7 8 } ; ∆ symmetric difference (set-equal? A B) → #f (set-equal? { a b c} { c b a}) → #t ; order is unimportant (set-subset? A B) → #f ; B in A or B = A (set-subset? A { 3 4 }) → #t (member 4 A) → (4 5) ; same as #t : true (member 9 A) → #f
- check basic equalities
(set-equal? A (set-union (set-intersect A B) (set-substract A B))) → #t (set-equal? (set-union A B) (set-union (set-sym-diff A B) (set-intersect A B))) → #t
- ×
- cartesian product of two sets : all pairs (a . b) , a in A, b in B
- returns a list (not a set)
(define A { albert simon}) (define B { antoinette ornella marylin})
(set-product A B) → ((albert . antoinette) (albert . marylin) (albert . ornella) (simon . antoinette) (simon . marylin) (simon . ornella))
- sets elements may be sets
{ { a b c} {c b a } { a b d}} → { { a b c } { a b d } } ; duplicate removed
- A few functions return sets
(primes 10) → { 2 3 5 7 11 13 17 19 23 29 } </lang>
Elixir
HashSet
is the implementing module of the Set
module.
<lang elixir>iex(101)> s = HashSet.new
- HashSet<[]>
iex(102)> sa = Set.put(s, :a)
- HashSet<[:a]>
iex(103)> sab = Set.put(sa, :b)
- HashSet<[:b, :a]>
iex(104)> sbc = Enum.into([:b,:c], HashSet.new)
- HashSet<[:c, :b]>
iex(105)> Set.member?(sa, :a) true iex(106)> Set.member?(sa, :b) false iex(107)> Set.union(sab, sbc)
- HashSet<[:c, :b, :a]>
iex(108)> Set.intersection(sab, sbc)
- HashSet<[:b]>
iex(109)> Set.difference(sab, sbc)
- HashSet<[:a]>
iex(110)> Set.disjoint?(sab, sbc) false iex(111)> Set.subset?(sa, sab) true iex(112)> Set.subset?(sab, sa) false iex(113)> sa == sab false</lang>
Erlang
Built in.
2> S = sets:new(). 3> Sa = sets:add_element(a, S). 4> Sab = sets:from_list([a, b]). 5> sets:is_element(a, Sa). true 6> Union = sets:union(Sa, Sab). 7> sets:to_list(Union). [a,b] 8> Intersection = sets:intersection(Sa, Sab). 9> sets:to_list(Intersection). [a] 10> Subtract = sets:subtract(Sab, Sa). 11> sets:to_list(Subtract). [b] 12> sets:is_subset(Sa, Sab). true 13> Sa =:= Sab. false
F#
The Collections.Set<'T> class implements "Immutable sets based on binary trees, where comparison is the F# structural comparison function, potentially using implementations of the IComparable interface on key values." (http://msdn.microsoft.com/en-us/library/ee353619.aspx) <lang fsharp>[<EntryPoint>] let main args =
// Create some sets (of int): let s1 = Set.ofList [1;2;3;4;3] let s2 = Set.ofArray [|3;4;5;6|]
printfn "Some sets (of int):" printfn "s1 = %A" s1 printfn "s2 = %A" s2 printfn "Set operations:" printfn "2 ∈ s1? %A" (s1.Contains 2) printfn "10 ∈ s1? %A" (s1.Contains 10) printfn "s1 ∪ s2 = %A" (Set.union s1 s2) printfn "s1 ∩ s2 = %A" (Set.intersect s1 s2) printfn "s1 ∖ s2 = %A" (Set.difference s1 s2) printfn "s1 ⊆ s2? %A" (Set.isSubset s1 s1) printfn "{3, 1} ⊆ s1? %A" (Set.isSubset (Set.ofList [3;1]) s1) printfn "{3, 2, 4, 1} = s1? %A" ((Set.ofList [3;2;4;1]) = s1) printfn "s1 = s2? %A" (s1 = s2) printfn "More set operations:" printfn "#s1 = %A" s1.Count printfn "s1 ∪ {99} = %A" (s1.Add 99) printfn "s1 ∖ {3} = %A" (s1.Remove 3) printfn "s1 ⊂ s1? %A" (Set.isProperSubset s1 s1) printfn "s1 ⊂ s2? %A" (Set.isProperSubset s1 s2) 0</lang>
- Output:
Some sets (of int): s1 = set [1; 2; 3; 4] s2 = set [3; 4; 5; 6] Set operations: 2 ∈ s1? true 10 ∈ s1? false s1 ∪ s2 = set [1; 2; 3; 4; 5; 6] s1 ∩ s2 = set [3; 4] s1 ∖ s2 = set [1; 2] s1 ⊆ s2? true {3, 1} ⊆ s1? true {3, 2, 4, 1} = s1? true s1 = s2? false More set operations: #s1 = 4 s1 ∪ {99} = set [1; 2; 3; 4; 99] s1 ∖ {3} = set [1; 2; 4] s1 ⊂ s1? false s1 ⊂ s2? false
Factor
We will use Factor's hash-sets for this task. A hash-set is created with HS{ ... }
.
<lang factor>( scratchpad ) USE: sets
( scratchpad ) HS{ 2 5 4 3 } HS{ 5 6 7 } union .
HS{ 2 3 4 5 6 7 }
( scratchpad ) HS{ 2 5 4 3 } HS{ 5 6 7 } intersect .
HS{ 5 }
( scratchpad ) HS{ 2 5 4 3 } HS{ 5 6 7 } diff .
HS{ 2 3 4 }
( scratchpad ) HS{ 2 5 4 3 } HS{ 5 6 7 } subset? .
f
( scratchpad ) HS{ 5 6 } HS{ 5 6 7 } subset? .
t
( scratchpad ) HS{ 5 6 } HS{ 5 6 7 } set= .
f
( scratchpad ) HS{ 6 5 7 } HS{ 5 6 7 } set= .
t</lang>
FunL
<lang funl>A = {1, 2, 3} B = {3, 4, 5} C = {1, 2, 3, 4, 5} D = {2, 1, 3}
println( '2 is in A: ' + (2 in A) ) println( '4 is in A: ' + (4 in A) ) println( 'A union B: ' + A.union(B) ) println( 'A intersect B: ' + A.intersect(B) ) println( 'A difference B: ' + A.diff(B) ) println( 'A subset of B: ' + A.subsetOf(B) ) println( 'A subset of B: ' + A.subsetOf(C) ) println( 'A equal B: ' + (A == B) ) println( 'A equal D: ' + (A == D) )
S = set( A )
println( 'S (mutable version of A): ' + S ) S.add( 4 ) println( 'S with 4 added: ' + S ) println( 'S subset of C: ' + S.subsetOf(C) ) S.remove( 1 ) println( 'S after 1 removed: ' + S )</lang>
- Output:
2 is in A: true 4 is in A: false A union B: {4, 5, 1, 2, 3} A intersect B: {3} A difference B: {1, 2} A subset of B: false A subset of B: true A equal B: false A equal D: true S (mutable version of A): {1, 2, 3} S with 4 added: {1, 2, 3, 4} S subset of C: true S after 1 removed: {2, 3, 4}
Go
Go maps make pretty good sets, especially if you use bool for the value type and follow the convention of always storing true. <lang go>package main
import "fmt"
type set map[int]bool
func main() {
// task: set creation s0 := make(set) // create empty set s1 := set{3: true} // create set with one element s2 := set{3: true, 1: true} // create set with two elements
// option: another way to create a set s3 := newSet([]int{3, 1, 4, 1, 5, 9})
// option: output! fmt.Println("s0:", s0) fmt.Println("s1:", s1) fmt.Println("s2:", s2) fmt.Println("s3:", s3)
// task: element predicate fmt.Printf("%v ∈ s0: %t\n", 3, s0.hasElement(3)) fmt.Printf("%v ∈ s3: %t\n", 3, s3.hasElement(3)) fmt.Printf("%v ∈ s3: %t\n", 2, s3.hasElement(2))
// task: union b := set{4: true, 2: true} fmt.Printf("s3 ∪ %v: %v\n", b, union(s3, b))
// task: intersection fmt.Printf("s3 ∩ %v: %v\n", b, intersection(s3, b))
// task: difference fmt.Printf("s3 \\ %v: %v\n", b, difference(s3, b))
// task: subset predicate fmt.Printf("%v ⊆ s3: %t\n", b, subset(b, s3)) fmt.Printf("%v ⊆ s3: %t\n", s2, subset(s2, s3)) fmt.Printf("%v ⊆ s3: %t\n", s0, subset(s0, s3))
// task: equality s2Same := set{1: true, 3: true} fmt.Printf("%v = s2: %t\n", s2Same, equal(s2Same, s2))
// option: proper subset fmt.Printf("%v ⊂ s2: %t\n", s2Same, properSubset(s2Same, s2)) fmt.Printf("%v ⊂ s3: %t\n", s2Same, properSubset(s2Same, s3))
// option: delete. it's built in. delete(s3, 3) fmt.Println("s3, 3 deleted:", s3)
}
func newSet(ms []int) set {
s := make(set) for _, m := range ms { s[m] = true } return s
}
func (s set) String() string {
if len(s) == 0 { return "∅" } r := "{" for e := range s { r = fmt.Sprintf("%s%v, ", r, e) } return r[:len(r)-2] + "}"
}
func (s set) hasElement(m int) bool {
return s[m]
}
func union(a, b set) set {
s := make(set) for e := range a { s[e] = true } for e := range b { s[e] = true } return s
}
func intersection(a, b set) set {
s := make(set) for e := range a { if b[e] { s[e] = true } } return s
}
func difference(a, b set) set {
s := make(set) for e := range a { if !b[e] { s[e] = true } } return s
}
func subset(a, b set) bool {
for e := range a { if !b[e] { return false } } return true
}
func equal(a, b set) bool {
return len(a) == len(b) && subset(a, b)
}
func properSubset(a, b set) bool {
return len(a) < len(b) && subset(a, b)
}</lang>
s0: ∅ s1: {3} s2: {3, 1} s3: {3, 4, 1, 5, 9} 3 ∈ s0: false 3 ∈ s3: true 2 ∈ s3: false s3 ∪ {4, 2}: {2, 3, 4, 1, 5, 9} s3 ∩ {2, 4}: {4} s3 \ {4, 2}: {3, 1, 5, 9} {4, 2} ⊆ s3: false {3, 1} ⊆ s3: true ∅ ⊆ s3: true {3, 1} = s2: true {1, 3} ⊂ s2: false {1, 3} ⊂ s3: true s3, 3 deleted: {4, 1, 5, 9}
Groovy
<lang groovy>def s1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as Set def m1 = 6 def m2 = 7 def s2 = [0, 2, 4, 6, 8] as Set assert m1 in s1 : 'member' assert ! (m2 in s2) : 'not a member' def su = s1 + s2 assert su == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as Set : 'union' def si = s1.intersect(s2) assert si == [8, 6, 4, 2] as Set : 'intersection' def sd = s1 - s2 assert sd == [1, 3, 5, 7, 9, 10] as Set : 'difference' assert s1.containsAll(si) : 'subset' assert ! s1.containsAll(s2) : 'not a subset' assert (si + sd) == s1 : 'equality' assert (s2 + sd) != s1 : 'inequality' assert s1 != su && su.containsAll(s1) : 'proper subset' s1 << 0 assert s1 == su : 'added element 0 to s1'</lang>
Haskell
GHC offers a functional, persistent set data structure in its Data.Set
module. It is implemented using a binary search tree. Elements must be of an orderable type (instance of Ord
).
<lang haskell>Prelude> import Data.Set
Prelude Data.Set> empty :: Set Integer -- Empty set
fromList []
Prelude Data.Set> let s1 = fromList [1,2,3,4,3] -- Convert list into set
Prelude Data.Set> s1
fromList [1,2,3,4]
Prelude Data.Set> let s2 = fromList [3,4,5,6]
Prelude Data.Set> union s1 s2 -- Union
fromList [1,2,3,4,5,6]
Prelude Data.Set> intersection s1 s2 -- Intersection
fromList [3,4]
Prelude Data.Set> s1 \\ s2 -- Difference
fromList [1,2]
Prelude Data.Set> s1 `isSubsetOf` s1 -- Subset
True
Prelude Data.Set> fromList [3,1] `isSubsetOf` s1
True
Prelude Data.Set> s1 `isProperSubsetOf` s1 -- Proper subset
False
Prelude Data.Set> fromList [3,1] `isProperSubsetOf` s1
True
Prelude Data.Set> fromList [3,2,4,1] == s1 -- Equality
True
Prelude Data.Set> s1 == s2
False
Prelude Data.Set> 2 `member` s1 -- Membership
True
Prelude Data.Set> 10 `notMember` s1
True
Prelude Data.Set> size s1 -- Cardinality
4
Prelude Data.Set> insert 99 s1 -- Create a new set by inserting
fromList [1,2,3,4,99]
Prelude Data.Set> delete 3 s1 -- Create a new set by deleting
fromList [1,2,4]</lang>
Regular lists can also be used as sets. Haskell has some functions to help with using lists as sets. No requirement is made of element type. However, these are not very efficient because they require linear time to find an element. <lang haskell>Prelude> import Data.List Prelude Data.List> let s3 = nub [1,2,3,4,3] -- Remove duplicates from list Prelude Data.List> s3 [1,2,3,4] Prelude Data.List> let s4 = [3,4,5,6] Prelude Data.List> union s3 s4 -- Union [1,2,3,4,5,6] Prelude Data.List> intersect s3 s4 -- Intersection [3,4] Prelude Data.List> s3 \\ s4 -- Difference [1,2] Prelude Data.List> 42 : s3 -- Return new list with element inserted at the beginning [42,1,2,3,4] Prelude Data.List> delete 3 s3 -- Return new list with first occurrence of element removed [1,2,4]</lang>
Icon and Unicon
The set is a basic datatype (structure) in Icon and Unicon, which supports 'member', 'union', 'intersection' and 'difference' operations. Subset and equality must be implemented separately, or use the routines in the 'sets' library.
Implemented directly:
<lang unicon> procedure display_set (s)
writes ("[") every writes (!s || " ") write ("]")
end
- fail unless s1 and s2 contain the same elements
procedure set_equals (s1, s2)
return subset(s1, s2) & subset(s2, s1)
end
- fail if every element in s2 is not contained in s1
procedure subset (s1, s2)
every (a := !s2) do { if not(member(s1,a)) then fail } return s2
end
procedure main ()
a := set(1, 1, 2, 3, 4) b := set(2, 3, 5) writes ("a: ") display_set (a) writes ("b: ") display_set (b) # basic set operations writes ("Intersection: ") display_set (a ** b) writes ("Union: ") display_set (a ++ b) writes ("Difference: ") display_set (a -- b) # membership if member(a, 2) then write ("2 is a member of a") else write ("2 is not a member of a") if member(a, 5) then write ("5 is a member of a") else write ("5 is not a member of a") # equality if set_equals(a, set(1,2,3,4,4)) then write ("a equals set(1,2,3,4,4)") else write ("a does not equal set(1,2,3,4,4)") if set_equals(a, b) then write ("a equals b") else write ("a does not equal b") # subset if subset(a, set(1,2)) then write ("(1,2) is included in a") else write ("(1,2) is not included in a") if subset(a, set(1,2,5)) then write ("(1,2,5) is included in a") else write ("(1,2,5) is not included in a")
end </lang>
- Output:
a: [2 4 1 3 ] b: [5 2 3 ] Intersection: [2 3 ] Union: [5 2 4 1 3 ] Difference: [4 1 ] 2 is a member of a 5 is not a member of a a equals set(1,2,3,4,4) a does not equal b (1,2) is included in a (1,2,5) is not included in a
Using library:
<lang unicon> link sets
procedure main ()
a := set(1, 1, 2, 3, 4) b := set(2, 3, 5) write ("a: ", simage(a)) write ("b: ", simage(b)) # basic set operations write ("Intersection: ", simage (a**b)) write ("Union: ", simage (a++b)) write ("Difference: ", simage (a--b)) # membership if member(a, 2) then write ("2 is a member of a") else write ("2 is not a member of a") if member(a, 5) then write ("5 is a member of a") else write ("5 is not a member of a") # equality if seteq(a, set(1,2,3,4,4)) then write ("a equals set(1,2,3,4,4)") else write ("a does not equal set(1,2,3,4,4)") if seteq(a, b) then write ("a equals b") else write ("a does not equal b") # check subset if setlt(set(1,2), a) then write ("(1,2) is included in a") else write ("(1,2) is not included in a") if setlt(a, set(1,2,5), a) then write ("(1,2,5) is included in a") else write ("(1,2,5) is not included in a")
end </lang>
- Output:
a: { 2, 4, 1, 3 } b: { 5, 2, 3 } Intersection: { 2, 3 } Union: { 5, 2, 4, 1, 3 } Difference: { 4, 1 } 2 is a member of a 5 is not a member of a a equals set(1,2,3,4,4) a does not equal b (1,2) is included in a (1,2,5) is not included in a
J
In J, we use a sequence to represent a set. This actually winds up being a family of set implementations. In this example, we chose to ignore order and specify that duplicate elements are not allowed.
Here are definitions for the required operations:
<lang j>union=: ~.@, intersection=: [ -. -. difference=: -. subset=: *./@e. equality=: -:&(/:~)</lang>
Examples:
<lang j> 2 4 6 8 ~.@, 2 3 5 7 2 4 6 8 3 5 7
2 4 6 8 ([ -. -.) 2 3 5 7
2
2 4 6 8 -. 2 3 5 7
4 6 8
2 4 6 8 *./@e. 2 3 5 7
0
*./@e. 2 3 5 7
1
2 4 6 8 3 5 7 -:&(/:~) 8 7 6 5 4 3 2
1</lang>
Examples again, using names rather than code:
<lang j> 2 4 6 8 union 2 3 5 7 2 4 6 8 3 5 7
2 4 6 8 intersection 2 3 5 7
2
2 4 6 8 difference 2 3 5 7
4 6 8
2 4 6 8 subset 2 3 5 7
0
subset 2 3 5 7
1
2 4 6 8 3 5 7 equality 8 7 6 5 4 3 2
1</lang>
Note that J uses 1 for true and 0 for false. Mathematical revisionists object to this, but this is consistent with the original (and revised) formulations of boolean algebra. (And there are deep ties to Bayes' rule.)
Note that these operations can be combined in sentences with other operations. For example we could define
<lang j>properSubset=: subset * 1 - equality</lang>
Java
To use this in Java 5 replace all "<>" with "<Integer>". <lang java5>import java.util.Arrays; import java.util.Collections; import java.util.Set; import java.util.TreeSet;
public class Sets {
public static void main(String[] args){ Set<Integer> a = new TreeSet<>(); //TreeSet sorts on natural ordering (or an optional comparator) //other options: HashSet (hashcode) // LinkedHashSet (insertion order) // EnumSet (optimized for enum values) //others at: http://download.oracle.com/javase/7/docs/api/java/util/Set.html Set<Integer> b = new TreeSet<>(); Set<Integer> c = new TreeSet<>(); Set<Integer> d = new TreeSet<>(); a.addAll(Arrays.asList(1, 2, 3, 4, 5)); b.addAll(Arrays.asList(2, 3, 4, 5, 6, 8)); c.addAll(Arrays.asList(2, 3, 4)); d.addAll(Arrays.asList(2, 3, 4)); System.out.println("a: " + a); System.out.println("b: " + b); System.out.println("c: " + c); System.out.println("d: " + d); System.out.println("2 in a: " + a.contains(2)); System.out.println("6 in a: " + a.contains(6)); Set<Integer> ab = new TreeSet<>(); ab.addAll(a); ab.addAll(b); System.out.println("a union b: " + ab); Set<Integer> a_b = new TreeSet<>(); a_b.addAll(a); a_b.removeAll(b); System.out.println("a - b: " + a_b); System.out.println("c subset of a: " + a.containsAll(c)); //use a.conatins() for single elements System.out.println("c = d: " + c.equals(d)); System.out.println("d = c: " + d.equals(c)); Set<Integer> aib = new TreeSet<>(); aib.addAll(a); aib.retainAll(b); System.out.println("a intersect b: " + aib); System.out.println("add 7 to a: " + a.add(7)); System.out.println("add 2 to a again: " + a.add(2)); //other noteworthy things related to sets: Set<Integer> empty = Collections.EMPTY_SET; //immutable empty set //empty.add(2); would fail empty.isEmpty(); //test if a set is empty empty.size(); Collections.disjoint(a, b); //returns true if the sets have no common elems (based on their .equals() methods) Collections.unmodifiableSet(a); //returns an immutable copy of a }
}</lang>
- Output:
a: [1, 2, 3, 4, 5] b: [2, 3, 4, 5, 6, 8] c: [2, 3, 4] d: [2, 3, 4] 2 in a: true 6 in a: false a union b: [1, 2, 3, 4, 5, 6, 8] a - b: [1] c subset of a: true c = d: true d = c: true a intersect b: [2, 3, 4, 5] add 7 to a: true add 2 to a again: false
JavaScript
JavaScript does not support native sets before ECMAScript 6.
<lang javascript> var set = new Set();
set.add(0); set.add(1); set.add('two'); set.add('three');
set.has(0); //=> true set.has(3); //=> false set.has('two'); // true set.has(Math.sqrt(4)); //=> true set.has('TWO'.toLowerCase()); //=> true
set.size; //=> 4
set.delete('two'); set.has('two'); //==> false set.size; //=> 3
//iterating set using ES6 for..of //Set order is preserved in order items are added. for (var item of set) {
console.log('item is ' + item);
}</lang>
jq
Neither JSON nor jq has a "set" type, but as explained below in the first part of this entry, finite sets of Unicode strings can be directly represented in JSON and thus jq.
The second part of this entry focuses on a jq library of set-theoretic functions that support finite sets of arbitrary JSON entities.
Finite Sets of Unicode Strings
There is an obvious 1-1 mapping between the collection of finite sets of Unicode strings and the collection of JSON objects with distinct keys the values of which all have the boolean value "true". For example, the set of strings {"a", "b"} corresponds to the JSON object {"a": true, "b": true }.
When restricted to such JSON objects, jq's equality operator ("==") yields set-theoretic semantics, and similarly, jq's + operator yields set-theoretic union.
For example: <lang jq>{"a":true, "b":true } == {"b":true, "a":true}. {"a":true} + {"b":true } == { "a":true, "b":true}</lang>
Thus, it can be seen that jq has built-in support for sets of finite-length Unicode strings.
For simplicity and to avoid confusion, we shall refer to JSON objects all of whose keys are distinct and all values of which have the boolean value "true" as "string sets".
String-set test
Here is a jq filter for determining whether a JSON object is a "string set": <lang jq>def is_stringset:
. as $in | type == "object" and reduce keys[] as $key (true; . and $in[$key] == true);</lang>
String-set membership:
The test for set membership, m ∈ S, where m is a string and S is a set of strings, corresponds exactly to the jq test: <lang jq>T | has(m)</lang> where T is the JSON object corresponding to S. This test is also efficient.
String-set intersection <lang jq># Set-intersection: A ∩ B def stringset_intersection(A;B):
reduce (A|keys)[] as $k ({}; if (B|has($k)) then . + {($k):true} else . end);</lang>
String-set difference <lang jq># stringset_difference: A \ B def stringset_difference(A;B):
reduce (A|keys)[] as $k ({}; if (B|has($k)) then . else . + {($k):true} end);</lang>
Subset <lang jq># A ⊆ B iff string_subset(A;B) def stringset_subset(A;B):
reduce (A|keys)[] as $k (true; . and (B|has($k)));</lang>
Finite Sets of JSON Entities
Finite sets of arbitrary JSON entities can be represented by sets of strings using an invertible serialization of JSON entities, but in the remainder of this entry, we provide a more straightforward and probably more efficient implementation of finite sets using JSON arrays.
Specifically, the empty set is represented by [] and a non-empty set of JSON entities with distinct members m1, m2, ... mN is represented by the JSON array [s1, s2, ... sN] where:
[s1, s2, ... sN] is the result of ([m1, m2, mN] | sort)
When confined to sorted arrays, jq's equality operator (==) yields set-theoretic semantics, and therefore, for the remainder of this entry, we shall refer to sorted arrays simply as sets.
To convert an arbitrary jq or JSON array to a set, we can simply use the built-in jq operator "unique". To test whether an arbitrary JSON entity is a set without sorting: <lang jq>def is_set:
. as $in | type == "array" and reduce range(0;length-1) as $i (true; if . then $in[$i] < $in[$i+1] else false end);</lang>
The following library of set-theoretic functions is intended for use with jq version 1.4 or later. However, as noted below, if used with a version of jq that does not have bsearch, then it is assumed that a definition of bsearch equivalent to that given in Binary search is available.
Set creation
- [] is the empty set;
- if m1 <= m2 <= ... mN then [m1, m2, ... mN] is the set containing the listed elements;
- The set of elements in an array, a, can be constructed by writing: a | unique
- The set of strings in the string-set SS is: SS|keys
m ∈ S
If m is a JSON entity and S a set, then the jq expression S[m] can be used to test whether m is an element of S, but for large sets, this is inefficient. A generally more efficient test membership of m in S would use bsearch as defined at Binary search or as provided in recent versions of jq: <lang jq>def is_member(m): bsearch(m) > -1;</lang>
Intersection <lang jq># If A and B are sets, then intersection(A;B) emits their intersection: def intersection(A;B):
(A|length) as $al | (B|length) as $bl | if $al == 0 or $bl == 0 then [] else reduce range(0; $al + $bl) as $k ( [0, 0, []]; .[0] as $i | .[1] as $j | if $i < $al and $j < $bl then if A[$i] == B[$j] then [ $i+1 , $j+1, .[2] + [A[$i]]] elif A[$i] < B[$j] then [ $i+1 , $j, .[2] ] else [ $i , $j+1, .[2] ] end else . end ) | .[2] end ;</lang>
Difference <lang jq># If A and B are sets, then A-B is emitted def difference(A;B):
(A|length) as $al | (B|length) as $bl | if $al == 0 then [] elif $bl == 0 then A else reduce range(0; $al + $bl) as $k ( [0, 0, []]; .[0] as $i | .[1] as $j | if $i < $al and $j < $bl then if A[$i] == B[$j] then [ $i+1, $j+1, .[2] ] elif A[$i] < B[$j] then [ $i+1, $j, .[2] + [A[$i]] ] else [ $i , $j+1, .[2] ] end elif $i < $al then [ $i+1, $j, .[2] + [A[$i]] ] else . end ) | .[2] end ;</lang>
Union
A simple but inefficient implementation would use: (A + B) | unique
To compute the union of two sets efficiently, it is helpful to define a function for merging sorted arrays. <lang jq># merge input array with array x by comparing the heads of the arrays in turn;
- if both arrays are sorted, the result will be sorted:
def merge(x):
length as $length | (x|length) as $xl | if $length == 0 then x elif $xl == 0 then . else . as $in | reduce range(0; $xl + $length) as $z # state [ix, xix, ans] ( [0, 0, []]; if .[0] < $length and ((.[1] < $xl and $in[.[0]] <= x[.[1]]) or .[1] == $xl) then [(.[0] + 1), .[1], (.[2] + [$in[.[0]]]) ] else [.[0], (.[1] + 1), (.[2] + [x[.[1]]]) ] end ) | .[2] end ;
def union(A;B):
A|merge(B) | reduce .[] as $m ([]; if length == 0 or .[length-1] != $m then . + [$m] else . end);</lang>
A ⊆ B <lang jq>def subset(A;B):
# TCO def _subset: if .[0]|length == 0 then true elif .[1]|length == 0 then false elif .[0][0] == .[1][0] then [.[0][1:], .[1][1:]] | _subset elif .[0][0] < .[1][0] then false else [ .[0], .[1][1:] ] | _subset end; [A,B] | _subset;</lang>
Julia
julia> S1 = Set(1:4) ; S2 = Set(3:6) ; println(S1,"\n",S2) Set{Int64}({4,2,3,1}) Set{Int64}({5,4,6,3}) julia> 5 in S1 , 5 in S2 (false,true) julia> intersect(S1,S2) Set{Int64}({4,3}) julia> union(S1,S2) Set{Int64}({5,4,6,2,3,1}) julia> setdiff(S1,S2) Set{Int64}({2,1}) julia> issubset(S1,S2) false julia> isequal(S1,S2) false julia> symdiff(S1,S2) Set{Int64}({5,6,2,1})
Lasso
<lang Lasso>// Extend set type define set->issubsetof(p::set) => .intersection(#p)->size == .size define set->oncompare(p::set) => .intersection(#p)->size - .size
// Set creation local(set1) = set('j','k','l','m','n') local(set2) = set('m','n','o','p','q')
//Test m ∈ S -- "m is an element in set S"
- set1 >> 'm'
// A ∪ B -- union; a set of all elements either in set A or in set B.
- set1->union(#set2)
//A ∩ B -- intersection; a set of all elements in both set A and set B.
- set1->intersection(#set2)
//A ∖ B -- difference; a set of all elements in set A, except those in set B.
- set1->difference(#set2)
//A ⊆ B -- subset; true if every element in set A is also in set B.
- set1->issubsetof(#set2)
//A = B -- equality; true if every element of set A is in set B and vice-versa.
- set1 == #set2</lang>
- Output:
true set(j, k, l, m, n, o, p, q) set(m, n) set(j, k, l) false false
LFE
<lang lisp> > (set set-1 (sets:new))
- (set 0 16 16 8 80 48 ...)
> (set set-2 (sets:add_element 'a set-1))
- (set 1 16 16 8 80 48 ...)
> (set set-3 (sets:from_list '(a b)))
- (set 2 16 16 8 80 48 ...)
> (sets:is_element 'a set-2) true > (set union (sets:union set-2 set-3))
- (set 2 16 16 8 80 48 ...)
> (sets:to_list union) (a b) > (set intersect (sets:intersection set-2 set-3))
- (set 1 16 16 8 80 48 ...)
> (sets:to_list intersect) (a) > (set subtr (sets:subtract set-3 set-2))
- (set 1 16 16 8 80 48 ...)
> (sets:to_list subtr) (b) > (sets:is_subset set-2 set-3) true > (=:= set-2 set-3) false > (set set-4 (sets:add_element 'b set-2))
- (set 2 16 16 8 80 48 ...)
> (=:= set-3 set-4) true </lang>
Liberty BASIC
Sets are not natively available- implemented here in string form so no need to dim/redim or pass number of elements. <lang lb> A$ ="red hot chili peppers rule OK" B$ ="lady in red"
print " New set, in space-separated form. Extra spaces and duplicates will be removed. " input newSet$
newSet$ =trim$( newSet$) newSet$ =stripBigSpaces$( newSet$) newSet$ =removeDupes$( newSet$)
print " Set stored as the string '"; newSet$; "'"
print print " 'red' is an element of '"; A$; "' is "; isAnElementOf$( "red", A$) print " 'blue' is an element of '"; A$; "' is "; isAnElementOf$( "blue", A$) print " 'red' is an element of '"; B$; "' is "; isAnElementOf$( "red", B$) print print " Union of '"; A$; "' & '"; B$; "' is '"; unionOf$( A$, B$); "'." print print " Intersection of '"; A$; "' & '"; B$; "' is '"; intersectionOf$( A$, B$); "'." print print " Difference of '"; A$; "' & '"; B$; "' is '"; differenceOf$( A$, B$); "'." print print " '"; A$; "' equals '"; A$; "' is "; equalSets$( A$, A$) print " '"; A$; "' equals '"; B$; "' is "; equalSets$( A$, B$) print print " '"; A$; "' is a subset of '"; B$; "' is "; isSubsetOf$( A$, B$) print " 'red peppers' is a subset of 'red hot chili peppers rule OK' is "; isSubsetOf$( "red peppers", "red hot chili peppers rule OK")
end
function removeDupes$( a$)
numElements =countElements( a$) redim elArray$( numElements) ' ie 4 elements are array entries 1 to 4 and 0 is spare ="" for m =0 to numElements el$ =word$( a$, m, " ") elArray$( m) =el$ next m sort elArray$(), 0, numElements b$ ="" penultimate$ ="999" for jk =0 to numElements ' do not use "" ( nuls) or elementsalready seen if elArray$( jk) ="" then [on] if elArray$( jk) <>penultimate$ then b$ =b$ +elArray$( jk) +" ": penultimate$ =elArray$( jk) [on] next jk b$ =trim$( b$) removeDupes$ =b$
end function
function stripBigSpaces$( a$) ' copy byte by byte, but id=f a space had a preceding space, ignore it.
lenA =len( a$) penul$ ="" for i =1 to len( a$) c$ =mid$( a$, i, 1) if c$ <>" " then if penul$ <>" " then b$ =b$ +c$ else b$ =b$ +" " +c$ end if end if penul$ =c$ next i stripBigSpaces$ =b$
end function
function countElements( a$) ' count elements repr'd by space-separated words in string rep'n.
if isNul$( a$) ="True" then countElements =0: exit function i =0 do el$ =word$( a$, i +1, " ") i =i +1 loop until el$ ="" countElements =i -1
end function
function isNul$( a$) ' a nul set implies its string rep'n is length zero.
if a$ ="" then isNul$ ="True" else isNul$ ="False"
end function
function isAnElementOf$( a$, b$) ' check element a$ exists in set b$.
isAnElementOf$ ="False" i =0 do el$ =word$( b$, i +1, " ") if a$ =el$ then isAnElementOf$ ="True" i =i +1 loop until el$ =""
end function
function unionOf$( a$, b$)
i =1 o$ =a$ do w$ =word$( b$, i, " ") if w$ ="" then exit do if isAnElementOf$( w$, a$) ="False" then o$ =o$ +" " +w$ i =i +1 loop until w$ ="" unionOf$ =o$
end function
function intersectionOf$( a$, b$)
i =1 o$ ="" do el$ =word$( a$, i, " ") if el$ ="" then exit do if ( isAnElementOf$( el$, b$) ="True") and ( o$ ="") then o$ =el$ if ( isAnElementOf$( el$, b$) ="True") and ( o$ <>el$) then o$ =o$ +" " +el$ i =i +1 loop until el$ ="" intersectionOf$ =o$
end function
function equalSets$( a$, b$)
if len( a$) <>len( b$) then equalSets$ ="False": exit function i =1 do el$ =word$( a$, i, " ") if isAnElementOf$( el$, b$) ="False" then equalSets$ ="False": exit function i =i +1 loop until w$ ="" equalSets$ ="True"
end function
function differenceOf$( a$, b$)
i =1 o$ ="" do el$ =word$( a$, i, " ") if el$ ="" then exit do if ( isAnElementOf$( el$, b$) ="False") and ( o$ ="") then o$ =el$ if ( isAnElementOf$( el$, b$) ="False") and ( o$ <>el$) then o$ =o$ +" " +el$ i =i +1 loop until el$ ="" differenceOf$ =o$
end function
function isSubsetOf$( a$, b$)
isSubsetOf$ ="True" i =1 do el$ =word$( a$, i, " ") if el$ ="" then exit do if ( isAnElementOf$( el$, b$) ="False") then isSubsetOf$ ="False": exit function i =i +1 loop until el$ =""
end function
</lang>
New set, in space-separated form. Extra spaces and duplicates will be removed. ? now is the the time for all good all men Set stored as the string 'all for good is men now the time' 'red' is an element of 'red hot chili peppers rule OK' is True 'blue' is an element of 'red hot chili peppers rule OK' is False 'red' is an element of 'lady in red' is True Union of 'red hot chili peppers rule OK' & 'lady in red' is 'red hot chili peppers rule OK lady in'. Intersection of 'red hot chili peppers rule OK' & 'lady in red' is 'red'. Difference of 'red hot chili peppers rule OK' & 'lady in red' is 'hot chili peppers rule OK'. 'red hot chili peppers rule OK' equals 'red hot chili peppers rule OK' is True 'red hot chili peppers rule OK' equals 'lady in red' is False 'red hot chili peppers rule OK' is a subset of 'lady in red' is False 'red peppers' is a subset of 'red hot chili peppers rule OK' is True
Maple
Sets in Maple are built-in, native data structures, and are immutable. Sets are formed by enclosing a sequence of objects between braces. You can get something essentially equivalent to set comprehensions by using {seq}, which applies the set constructor ("{}") to the sequencing operation "seq". <lang Maple> > S := { 2, 3, 5, 7, 11, Pi, "foo", { 2/3, 3/4, 4/5 } };
S := {2, 3, 5, 7, 11, "foo", Pi, {2/3, 3/4, 4/5}}
> type( S, set );
true
> Pi in S;
Pi in {2, 3, 5, 7, 11, "foo", Pi, {2/3, 3/4, 4/5}}
> if Pi in S then print( yes ) else print( no ) end:
yes
> member( Pi, S );
true
> if 4 in S then print( yes ) else print( no ) end:
no
> evalb( { 2/3, 3/4, 4/5 } in S );
true
> { a, b, c } union { 1, 2, 3 };
{1, 2, 3, a, b, c}
> { a, b, c } intersect { b, c, d };
{b, c}
> { a, b, c } minus { b, c, d };
{a}
> { a, b } subset { a, b, c };
true
> { a, d } subset { a, b, c };
false
> evalb( { 1, 2, 3 } = { 1, 2, 3 } );
true
> evalb( { 1, 2, 3 } = { 1, 2, 4 } );
false
</lang>
Mathematica
<lang Mathematica>set1 = {"a", "b", "c", "d", "e"}; set2 = {"a", "b", "c", "d", "e", "f", "g"}; MemberQ[set1, "a"] Union[set1 , set2] Intersection[set1 , set2] Complement[set2, set1](*Set Difference*) MemberQ[Subsets[set2], set1](*Subset*) set1 == set2(*Equality*) set1 == set1(*Equality*)</lang>
- Output:
True {"a", "b", "c", "d", "e", "f", "g"} {"a", "b", "c", "d", "e"} {"f", "g"} True False True
MATLAB / Octave
There are two types of sets supported, sets with numeric values are stored in a vector, sets with string elements are stored in a cell-array. <lang Matlab>
% Set creation
s = [1, 2, 4]; % numeric values t = {'a','bb','ccc'}; % cell array of strings
u = unique([1,2,3,3,2,3,2,4,1]); % set consists only of unique elements % Test m ∈ S -- "m is an element in set S" ismember(m, S) % A ∪ B -- union; a set of all elements either in set A or in set B.
union(A, B)
% A ∩ B -- intersection; a set of all elements in both set A and set B.
intersect(A, B)
% A ∖ B -- difference; a set of all elements in set A, except those in set B.
setdiff(A, B)
% A ⊆ B -- subset; true if every element in set A is also in set B. all(ismember(A, B)) % A = B -- equality; true if every element of set A is in set B and vice-versa. isempty(setxor(A, B))
</lang>
Maxima
<lang>/* illustrating some functions on sets; names are self-explanatory */
a: {1, 2, 3, 4}; {1, 2, 3, 4}
b: {2, 4, 6, 8}; {2, 4, 6, 8}
intersection(a, b); {2, 4}
union(a, b); {1, 2, 3, 4, 6, 8}
powerset(a); {{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 4}, {1, 3}, {1, 3, 4}, {1, 4}, {2}, {2, 3}, {2, 3, 4}, {2, 4}, {3}, {3, 4}, {4}}
set_partitions(a); {{{1}, {2}, {3}, {4}}, {{1}, {2}, {3, 4}}, {{1}, {2, 3}, {4}}, {{1}, {2, 3, 4}}, {{1}, {2, 4}, {3}}, {{1, 2}, {3}, {4}}, {{1, 2}, {3, 4}}, {{1, 2, 3}, {4}}, Template:1, 2, 3, 4, {{1, 2, 4}, {3}}, {{1, 3}, {2}, {4}}, {{1, 3}, {2, 4}}, {{1, 3, 4}, {2}}, {{1, 4}, {2}, {3}}, {{1, 4}, {2, 3}}}
setdifference(a, b); {1, 3}
emptyp(a); false
elementp(2, a); true
cardinality(a); 4
cartesian_product(a, b); {[1, 2], [1, 4], [1, 6], [1, 8], [2, 2], [2, 4], [2, 6], [2, 8], [3, 2], [3, 4], [3, 6], [3, 8], [4, 2], [4, 4], [4, 6], [4, 8]}
subsetp(a, b); false
symmdifference(a, b); {1, 3, 6, 8}
partition_set(union(a, b), evenp); [{1, 3}, {2, 4, 6, 8}]
c: setify(makelist(fib(n), n, 1, 20)); {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765}
equiv_classes(c, lambda([m, n], mod(m - n, 3) = 0)); {{1, 13, 34, 55, 610, 1597, 2584}, {2, 5, 8, 89, 233, 377, 4181}, {3, 21, 144, 987, 6765}}
disjointp(a, b); false
adjoin(7, a); {1, 2, 3, 4, 7}
a; {1, 2, 3, 4}
disjoin(1, a); {2, 3, 4}
a; {1, 2, 3, 4}
subset(c, primep); {2, 3, 5, 13, 89, 233, 1597}
permutations(a); {[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2],
[2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]}
setequalp(a, b); false</lang>
Nemerle
The Nemerle.Collections namespace provides an implementation of a Set. <lang Nemerle>using System.Console; using Nemerle.Collections;
module RCSet {
HasSubset[T](this super : Set[T], sub : Set[T]) : bool { super.ForAll(x => sub.Contains(x)) } Main() : void { def names1 = Set(["Bob", "Billy", "Tom", "Dick", "Harry"]); def names2 = Set(["Bob", "Mary", "Alice", "Louisa"]); //def names3 = Set(["Bob", "Bob"]); // unfortunately, duplicated elements are not well handled by the stock // implementation, this statement would throw an ArgumentException def elem = names1.Contains("Bob"); // element test def names1u2 = names1.Sum(names2); // union def names1d2 = names1.Subtract(names2); // difference def names1i2 = names1.Intersect(names2); // intersection def same = names1.Equals(names2); // equality def sub12 = names1.HasSubset(names2); // subset WriteLine($"$names1u2\n$names1d2\n$names1i2"); WriteLine($"$same\t$sub12"); }
}</lang>
Nim
<lang nim>var # creation
s = {0,3,5,10} t = {3..20, 50..55}
if 5 in s: echo "5 is in!" # element test
var
c = s + t # union d = s * t # intersection e = s - t # difference
if s <= t: echo "s ⊆ t" # subset
if s <= t: echo "s ⊂ t" # strong subset
if s == t: echo "s = s" # equality
s.incl(4) # add 4 to set s.excl(5) # remove 5 from set</lang>
Objective-C
<lang objc>#import <Foundation/Foundation.h>
int main (int argc, const char *argv[]) {
@autoreleasepool { NSSet *s1 = [NSSet setWithObjects:@"a", @"b", @"c", @"d", @"e", nil]; NSSet *s2 = [NSSet setWithObjects:@"b", @"c", @"d", @"e", @"f", @"h", nil]; NSSet *s3 = [NSSet setWithObjects:@"b", @"c", @"d", nil]; NSSet *s4 = [NSSet setWithObjects:@"b", @"c", @"d", nil]; NSLog(@"s1: %@", s1); NSLog(@"s2: %@", s2); NSLog(@"s3: %@", s3); NSLog(@"s4: %@", s4); // Membership NSLog(@"b in s1: %d", [s1 containsObject:@"b"]); NSLog(@"f in s1: %d", [s1 containsObject:@"f"]); // Union NSMutableSet *s12 = [NSMutableSet setWithSet:s1]; [s12 unionSet:s2]; NSLog(@"s1 union s2: %@", s12); // Intersection NSMutableSet *s1i2 = [NSMutableSet setWithSet:s1]; [s1i2 intersectSet:s2]; NSLog(@"s1 intersect s2: %@", s1i2); // Difference NSMutableSet *s1_2 = [NSMutableSet setWithSet:s1]; [s1_2 minusSet:s2]; NSLog(@"s1 - s2: %@", s1_2); // Subset of NSLog(@"s3 subset of s1: %d", [s3 isSubsetOfSet:s1]); // Equality NSLog(@"s3 = s4: %d", [s3 isEqualToSet:s4]); // Cardinality NSLog(@"size of s1: %lu", [s1 count]); // Has intersection (not disjoint) NSLog(@"does s1 intersect s2? %d", [s1 intersectsSet:s2]); // Adding and removing elements from a mutable set NSMutableSet *mut_s1 = [NSMutableSet setWithSet:s1]; [mut_s1 addObject:@"g"]; NSLog(@"mut_s1 after adding g: %@", mut_s1); [mut_s1 addObject:@"b"]; NSLog(@"mut_s1 after adding b again: %@", mut_s1); [mut_s1 removeObject:@"c"]; NSLog(@"mut_s1 after removing c: %@", mut_s1); } return 0;
}</lang>
- Output:
s1: {( d, b, e, c, a )} s2: {( d, b, e, c, h, f )} s3: {( b, c, d )} s4: {( b, c, d )} b in s1: 1 f in s1: 0 s1 union s2: {( c, h, d, e, a, f, b )} s1 intersect s2: {( d, b, e, c )} s1 - s2: {( a )} s3 subset of s1: 1 s3 = s4: 1 size of s1: 5 does s1 intersect s2? 1 mut_s1 after adding g: {( d, b, g, e, c, a )} mut_s1 after adding b again: {( d, b, g, e, c, a )} mut_s1 after removing c: {( d, b, g, e, a )}
OCaml
OCaml offers a functional, persistent set data structure in its Set
module. It is implemented using a binary search tree. Set
works in the functor model, which means you need to first use the Set.Make
functor to create a module for your kind of set that you can use. You must give the functor an argument that is a module containing the type and ordering function.
In the interactive toplevel:
<lang ocaml># module IntSet = Set.Make(struct type t = int let compare = compare end);; (* Create a module for our type of set *) module IntSet :
sig type elt = int type t val empty : t val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> bool val subset : t -> t -> bool val iter : (elt -> unit) -> t -> unit val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a val for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int val elements : t -> elt list val min_elt : t -> elt val max_elt : t -> elt val choose : t -> elt val split : elt -> t -> t * bool * t val find : elt -> t -> elt val of_list : elt list -> t end
- IntSet.empty;; (* Empty set. A set is an abstract type that will not display in the interpreter *)
- : IntSet.t = <abstr>
- IntSet.elements (IntSet.empty);; (* Get the previous set into a list *)
- : IntSet.elt list = []
- let s1 = IntSet.of_list [1;2;3;4;3];;
val s1 : IntSet.t = <abstr>
- IntSet.elements s1;;
- : IntSet.elt list = [1; 2; 3; 4]
- let s2 = IntSet.of_list [3;4;5;6];;
val s2 : IntSet.t = <abstr>
- IntSet.elements s2;;
- : IntSet.elt list = [3; 4; 5; 6]
- IntSet.elements (IntSet.union s1 s2);; (* Union *)
- : IntSet.elt list = [1; 2; 3; 4; 5; 6]
- IntSet.elements (IntSet.inter s1 s2);; (* Intersection *)
- : IntSet.elt list = [3; 4]
- IntSet.elements (IntSet.diff s1 s2);; (* Difference *)
- : IntSet.elt list = [1; 2]
- IntSet.subset s1 s1;; (* Subset *)
- : bool = true
- IntSet.subset (IntSet.of_list [3;1]) s1;;
- : bool = true
- IntSet.equal (IntSet.of_list [3;2;4;1]) s1;; (* Equality *)
- : bool = true
- IntSet.equal s1 s2;;
- : bool = false
- IntSet.mem 2 s1;; (* Membership *)
- : bool = true
- IntSet.mem 10 s1;;
- : bool = false
- IntSet.cardinal s1;; (* Cardinality *)
- : int = 4
- IntSet.elements (IntSet.add 99 s1);; (* Create a new set by inserting *)
- : IntSet.elt list = [1; 2; 3; 4; 99]
- IntSet.elements (IntSet.remove 3 s1);; (* Create a new set by deleting *)
- : IntSet.elt list = [1; 2; 4]</lang>
(Note: of_list
is only available in OCaml 4.02+. In earlier versions, you can implement one yourself like
let of_list lst = List.fold_right IntSet.add lst IntSet.empty;;
)
Regular lists can also be used as sets.
In addition, you can use imperative hash tables from the Hashtbl
module as a hash table-based set, using the unit type as the "value" for each key.
ooRexx
<lang ooRexx>-- Set creation -- Using the OF method s1 = .set~of(1, 2, 3, 4, 5, 6) -- Explicit addition of individual items s2 = .set~new s2~put(2) s2~put(4) s2~put(6) -- group addition s3 = .set~new s3~putall(.array~of(1, 3, 5)) -- Test m ? S -- "m is an element in set S" say s1~hasindex(1) s3~hasindex(2) -- "1 0", which is "true" and "false" -- A ? B -- union; a set of all elements either in set A or in set B. s4 = s2~union(s3) -- {1, 2, 3, 4, 5, 6} Call show 's4',s4 -- A ? B -- intersection; a set of all elements in both set A and set B. s5 = s1~intersection(s2) -- {2, 4, 6} Call show 's5',s5 -- A ? B -- difference; a set of all elements in set A, except those in set B. s6 = s1~difference(s2) -- {1, 3, 5} Call show 's6',s6 -- A ? B -- subset; true if every element in set A is also in set B. say s1~subset(s2) s2~subset(s1) -- "0 1" -- A = B -- equality; true if every element of set A is in set B and vice-versa. -- No direct equivalence method, but the XOR method can be used to determine this say s1~xor(s4)~isempty -- true Exit show: Procedure
Use Arg set_name,set Say set_name':' set~makearray~makestring((LINE),',') return</lang>
The set operators don't come out too well :-(
- Output:
1 0 s4: 1,2,3,4,5,6 s5: 2,4,6 s6: 1,3,5 0 1 1
PARI/GP
Aside from ⊆, all operations are already a part of GP. <lang parigp>setsubset(s,t)={
for(i=1,#s, if(!setsearch(t,s[i]), return(0)) ); 1
}; s=Set([1,2,2]) t=Set([4,2,4]) setsearch(s,1) setunion(s,t) setintersect(s,t) setminus(s,t) setsubset(s,t) s==t</lang>
- Output:
%1 = [1, 2] %2 = [2, 4] %3 = 1 %4 = [1, 2, 4] %5 = [2] %6 = [1] %7 = 0 %8 = 0
Pascal
Freepascal/object pascal handles sets very well. --Guionardo 22:03, 7 January 2012 (UTC)
<lang pascal>program Rosetta_Set;
{$mode objfpc}{$H+}
uses {$IFDEF UNIX} {$IFDEF UseCThreads}
cthreads, {$ENDIF} {$ENDIF} Classes;
{$R *.res} type
CharSet = set of char;
var
A, B, C, S: CharSet; M: char;
function SetToString(const ASet: CharSet): string; var J: char; begin Result := ; // Test all chars for J in char do // If the char is in set, add to result if J in ASet then Result := Result + J + ', '; // Clear the result if Result > then Delete(Result, Length(Result) - 1, 2); end;
procedure PrintSet(const ASet: CharSet; const ASetName: string; const ATitle: string = ); begin if ATitle > then WriteLn(ATitle); WriteLn(ASetName, ' = [', SetToString(ASet), ']', #10); end;
procedure ShowEqual(const ASetA, ASetB: CharSet; const ASetNameA, ASetNameB: string); begin WriteLn(ASetNameA, ' = [', SetToString(ASetA), ']'); WriteLn(ASetNameB, ' = [', SetToString(ASetB), ']'); if ASetA = ASetB then WriteLn(ASetNameA, ' = ', ASetNameB) else WriteLn(ASetNameA, ' <> ', ASetNameB); end;
begin
// Set Creation A := ['A', 'B', 'C', 'D', 'E', 'F']; B := ['E', 'F', 'G', 'H', 'I', 'J']; PrintSet(A, 'A', 'Set Creation'); PrintSet(B, 'B');
// Test m ∈ S -- "m is an element in set S" M := 'A'; if M in A then WriteLn('"A" is in set A');
// A ∪ B -- union; a set of all elements either in set A or in set B. S := A + B; PrintSet(S, 'S', 'S = A U B -- union; a set of all elements either in set A or in set B.');
// A ∩ B -- intersection; a set of all elements in both set A and set B. S := A * B; PrintSet(S, 'S', 'S = A ∩ B -- intersection; a set of all elements in both set A and set B.');
// A \ B -- difference; a set of all elements in set A, except those in set B. S := A - B; PrintSet(S, 'S', 'S = A \ B -- difference; a set of all elements in set A, except those in set B.');
// A ⊆ B -- subset; true if every element in set A is also in set B. Writeln('A ⊆ B -- subset; true if every element in set A is also in set B.'); if A <= B then WriteLn('A in B') else Writeln('A is not in B'); Writeln; //A = B -- equality; true if every element of set A is in set B and vice-versa. Writeln('A = B -- equality; true if every element of set A is in set B and vice-versa.');
ShowEqual(A, B, 'A', 'B'); S := A * B; C := ['E', 'F']; ShowEqual(S, C, 'S', 'C');
readln;
end.</lang>
Perl
For real code, try Set::Object from CPAN. Here we provide a primitive implementation using hashes. <lang perl>use strict;
package Set; # likely will conflict with stuff on CPAN use overload '""' => \&str, 'bool' => \&count, '+=' => \&add, '-=' => \&del, '-' => \&diff, '==' => \&eq, '&' => \&intersection, '|' => \&union, '^' => \&xdiff;
sub str { my $set = shift; # This has drawbacks: stringification is used as set key # if the set is added to another set as an element, which # may cause inconsistencies if the element set is modified # later. In general, a hash key loses its object identity # anyway, so it's not unique to us. "Set{ ". join(", " => sort map("$_", values %$set)) . " }" }
sub new { my $pkg = shift; my $h = bless {}; $h->add($_) for @_; $h }
sub add { my ($set, $elem) = @_; $set->{$elem} = $elem; $set }
sub del { my ($set, $elem) = @_; delete $set->{$elem}; $set }
sub has { # set has element my ($set, $elem) = @_; exists $set->{$elem} }
sub union { my ($this, $that) = @_; bless { %$this, %$that } }
sub intersection { my ($this, $that) = @_; my $s = new Set; for (keys %$this) { $s->{$_} = $this->{$_} if exists $that->{$_} } $s }
sub diff { my ($this, $that) = @_; my $s = Set->new; for (keys %$this) { $s += $this->{$_} unless exists $that->{$_} } $s }
sub xdiff { # xor, symmetric diff my ($this, $that) = @_; my $s = new Set; bless { %{ ($this - $that) | ($that - $this) } } }
sub count { scalar(keys %{+shift}) }
sub eq { my ($this, $that) = @_; !($this - $that) && !($that - $this); }
sub contains { # this is a superset of that my ($this, $that) = @_; for (keys %$that) { return 0 unless $this->has($_) } return 1 }
package main; my ($x, $y, $z, $w);
$x = Set->new(1, 2, 3); $x += $_ for (5 .. 7); $y = Set->new(1, 2, 4, $x); # not the brightest idea
print "set x is: $x\nset y is: $y\n"; for (1 .. 4, $x) { print "$_ is", $y->has($_) ? "" : " not", " in y\n"; }
print "union: ", $x | $y, "\n"; print "intersect: ", $x & $y, "\n"; print "z = x - y = ", $z = $x - $y, "\n"; print "y is ", $x->contains($y) ? "" : "not ", "a subset of x\n"; print "z is ", $x->contains($z) ? "" : "not ", "a subset of x\n"; print "z = (x | y) - (x & y) = ", $z = ($x | $y) - ($x & $y), "\n"; print "w = x ^ y = ", $w = ($x ^ $y), "\n"; print "w is ", ($w == $z) ? "" : "not ", "equal to z\n"; print "w is ", ($w == $x) ? "" : "not ", "equal to x\n";</lang>
Perl 6
<lang perl6>use Test;
my $a = set <a b c>; my $b = set ; my $c = set <a b c d e>;
ok 'c' ∈ $a, "c is an element in set A"; nok 'd' ∈ $a, "d is not an element in set A";
is $a ∪ $b, set(<a b c d>), "union; a set of all elements either in set A or in set B"; is $a ∩ $b, set(), "intersection; a set of all elements in both set A and set B"; is $a (-) $b, set(<a>), "difference; a set of all elements in set A, except those in set B";
ok $a ⊆ $c, "subset; true if every element in set A is also in set B"; nok $c ⊆ $a, "subset; false if every element in set A is not also in set B"; ok $a ⊂ $c, "strict subset; true if every element in set A is also in set B"; nok $a ⊂ $a, "strict subset; false for equal sets"; ok $a === set(<a b c>), "equality; true if every element of set A is in set B and vice-versa"; nok $a === $b, "equality; false for differing sets";</lang>
- Output:
ok 1 - c is an element in set A ok 2 - d is not an element in set A ok 3 - union; a set of all elements either in set A or in set B ok 4 - intersection; a set of all elements in both set A and set B ok 5 - difference; a set of all elements in set A, except those in set B ok 6 - subset; true if every element in set A is also in set B ok 7 - subset; false if every element in set A is not also in set B ok 8 - strict subset; true if every element in set A is also in set B ok 9 - strict subset; false for equal sets ok 10 - equality; true if every element of set A is in set B and vice-versa ok 11 - equality; false for differing sets
PicoLisp
We may use plain lists, or 'idx' structures for sets. A set may contain any type of data.
Using lists
<lang PicoLisp>(setq
Set1 (1 2 3 7 abc "def" (u v w)) Set2 (2 3 5 hello (x y z)) Set3 (3 hello (x y z)) )
- Element tests (any non-NIL value means "yes")
- (member "def" Set1)
-> ("def" (u v w))
- (member "def" Set2)
-> NIL
- (member '(x y z) Set2)
-> ((x y z))
- Union
- (uniq (append Set1 Set2))
-> (1 2 3 7 abc "def" (u v w) 5 hello (x y z))
- Intersection
- (sect Set1 Set2)
-> (2 3)
- Difference
- (diff Set1 Set2)
-> (1 7 abc "def" (u v w))
- Test for subset
- (not (diff Set1 Set2))
-> NIL # Set1 is not a subset of Set2
- (not (diff Set3 Set2))
-> T # Set3 is a subset of Set2
- Test for equality
- (= (sort (copy Set1)) (sort (copy Set2)))
-> NIL
- (= (sort (copy Set2)) (sort (copy Set2)))
-> T</lang>
Using 'idx' structures
<lang PicoLisp># Create three test-sets (balance 'Set1 (1 2 3 7 abc "def" (u v w))) (balance 'Set2 (2 3 5 hello (x y z))) (balance 'Set3 (3 hello (x y z)))
- Get contents
- (idx 'Set1)
-> (1 2 3 7 abc "def" (u v w))
- (idx 'Set2)
-> (2 3 5 hello (x y z))
- Element tests (any non-NIL value means "yes")
- (idx 'Set1 "def")
-> ("def" (abc) (u v w))
- (idx 'Set2 "def")
-> NIL
- (idx 'Set2 '(x y z))
-> ((x y z))
- Union
- (use S
(balance 'S (idx 'Set1)) (balance 'S (idx 'Set2) T) (idx 'S) )
-> (1 2 3 5 7 abc "def" hello (u v w) (x y z))
- Intersection
- (sect (idx 'Set1) (idx 'Set2))
-> (2 3)
- Difference
- (diff (idx 'Set1) (idx 'Set2))
-> (1 7 abc "def" (u v w))
- Test for subset
- (not (diff (idx 'Set1) (idx 'Set2)))
-> NIL # Set1 is not a subset of Set2
- (not (diff (idx 'Set3) (idx 'Set2)))
-> T # Set3 is a subset of Set2
- Test for equality
- (= (idx 'Set1) (idx 'Set2))
-> NIL
- (= (idx 'Set2) (idx 'Set2))
-> T</lang>
Prolog
Works with SWI-Prolog, library(lists). <lang Prolog>:- use_module(library(lists)).
set :- A = [2, 4, 1, 3], B = [5, 2, 3, 2], ( is_set(A) -> format('~w is a set~n', [A]) ; format('~w is not a set~n', [A])), ( is_set(B) -> format('~w is a set~n', [B]) ; format('~w is not a set~n', [B])),
% create a set from a list
list_to_set(B, BS), ( is_set(BS) -> format('~nCreate a set from a list~n~w is a set~n', [BS]) ; format('~w is not a set~n', [BS])),
intersection(A, BS, I), format('~n~w intersection ~w => ~w~n', [A, BS, I]), union(A, BS, U), format('~w union ~w => ~w~n', [A, BS, U]), difference(A, BS, D), format('~w difference ~w => ~w~n', [A, BS, D]),
X = [1,2], ( subset(X, A) -> format('~n~w is a subset of ~w~n', [X, A]) ; format('~w is not a subset of ~w~n', [X, A])), Y = [1,5], ( subset(Y, A) -> format('~w is a subset of ~w~n', [Y, A]) ; format('~w is not a subset of ~w~n', [Y, A])), Z = [1, 2, 3, 4], ( equal(Z, A) -> format('~n~w is equal to ~w~n', [Z, A]) ; format('~w is not equal to ~w~n', [Z, A])), T = [1, 2, 3], ( equal(T, A) -> format('~w is equal to ~w~n', [T, A]) ; format('~w is not equal to ~w~n', [T, A])).
% compute difference of sets difference(A, B, D) :- exclude(member_(B), A, D).
member_(L, X) :- member(X, L).
equal([], []). equal([H1 | T1], B) :- select(H1, B, B1), equal(T1, B1). </lang>
- Output:
?- set. [2,4,1,3] is a set [5,2,3,2] is not a set Create a set from a list [5,2,3] is a set [2,4,1,3] intersection [5,2,3] => [2,3] [2,4,1,3] union [5,2,3] => [4,1,5,2,3] [2,4,1,3] difference [5,2,3] => [4,1] [1,2] is a subset of [2,4,1,3] [1,5] is not a subset of [2,4,1,3] [1,2,3,4] is equal to [2,4,1,3] [1,2,3] is not equal to [2,4,1,3] true.
SWI-Prolog provides a standard library(ordsets). It is loaded by default. I demonstrate almost all of these predicates in the interactive top-level (`?-` is the prompt). Variables prefixed with `$` refer back to the value of the last instantiation. It treats sets as ordered lists of unique elements:
<lang prolog> %% Set creation
?- list_to_ord_set([1,2,3,4], A), list_to_ord_set([2,4,6,8], B). A = [1, 2, 3, 4], B = [2, 4, 6, 8].
%% Test m ∈ S -- "m is an element in set S"
?- ord_memberchk(2, $A). true.
%% A ∪ B -- union; a set of all elements either in set A or in set B.
?- ord_union($A, $B, Union). Union = [1, 2, 3, 4, 6, 8].
%% A ∩ B -- intersection; a set of all elements in both set A and set B.
?- ord_intersection($A, $B, Intersection). Intersection = [2, 4].
%% A ∖ B -- difference; a set of all elements in set A, except those in set B.
?- ord_subtract($A, $B, Diff). Diff = [1, 3].
%% A ⊆ B -- subset; true if every element in set A is also in set B.
?- ord_subset($A, $B). false.
?- ord_subset([2,4], $B). true.
%% A = B -- equality; true if every element of set A is in set B and vice-versa.
?- $A == $B. false.
?- $A == [1,2,3,4]. true.
%% Definition of a proper subset:
ord_propsubset(A, B) :-
ord_subset(A, B), \+(A == B).
%% add/remove elements
?- ord_add_element($A, 19, NewA). NewA = [1, 2, 3, 4, 19].
?- ord_del_element($NewA, 3, NewerA). NewerA = [1, 2, 4, 19]. </lang>
PureBasic
This solution uses PureBasic's maps (hash tables). <lang purebasic>Procedure.s booleanText(b) ;returns 'True' or 'False' for a boolean input
If b: ProcedureReturn "True": EndIf ProcedureReturn "False"
EndProcedure
Procedure.s listSetElements(Map a(), delimeter.s = " ") ;format elements for display
Protected output$ ForEach a() output$ + MapKey(a()) + delimeter Next ProcedureReturn "(" + RTrim(output$, delimeter) + ")"
EndProcedure
Procedure.s listSortedSetElements(Map a(), delimeter.s = " ") ;format elements for display as sorted for easy comparison
Protected output$ NewList b.s() ForEach a() AddElement(b()): b() = MapKey(a()) Next SortList(b(), #PB_Sort_Ascending | #PB_Sort_NoCase) ForEach b() output$ + b() + delimeter Next ProcedureReturn "(" + RTrim(output$, delimeter) + ")"
EndProcedure
Procedure cardinalityOf(Map a())
ProcedureReturn MapSize(a())
EndProcedure
Procedure createSet(elements.s, Map o(), delimeter.s = " ", clearSet = 1)
Protected i, elementCount If clearSet: ClearMap(o()): EndIf elementCount = CountString(elements, delimeter) + 1 ;add one for the last element which won't have a delimeter For i = 1 To elementCount AddMapElement(o(), StringField(elements, i, delimeter)) Next ProcedureReturn MapSize(o())
EndProcedure
Procedure adjoinTo(elements.s, Map o(), delimeter.s = " ")
ProcedureReturn createSet(elements, o(), delimeter, 0)
EndProcedure
Procedure disjoinFrom(elements.s, Map o(), delimeter.s = " ")
Protected i, elementCount elementCount = CountString(elements, delimeter) + 1 ;add one for the last element which won't have a delimeter For i = 1 To elementCount DeleteMapElement(o(), StringField(elements, i, delimeter)) Next ProcedureReturn MapSize(o())
EndProcedure
Procedure isElementOf(element.s, Map a())
ProcedureReturn FindMapElement(a(), element)
EndProcedure
Procedure unionOf(Map a(), Map b(), Map o())
CopyMap(a(), o()) ForEach b() AddMapElement(o(), MapKey(b())) Next ProcedureReturn MapSize(o())
EndProcedure
Procedure intersectionOf(Map a(), Map b(), Map o())
ClearMap(o()) ForEach a() If FindMapElement(b(), MapKey(a())) AddMapElement(o(), MapKey(a())) EndIf Next ProcedureReturn MapSize(o())
EndProcedure
Procedure differenceOf(Map a(), Map b(), Map o())
CopyMap(a(), o()) ForEach b() If FindMapElement(o(), MapKey(b())) DeleteMapElement(o()) Else AddMapElement(o(), MapKey(b())) EndIf Next ProcedureReturn MapSize(o())
EndProcedure
Procedure isSubsetOf(Map a(), Map b()) ;boolean
ForEach a() If Not FindMapElement(b(), MapKey(a())) ProcedureReturn 0 EndIf Next ProcedureReturn 1
EndProcedure
Procedure isProperSubsetOf(Map a(), Map b()) ;boolean
If MapSize(a()) = MapSize(b()) ProcedureReturn 0 EndIf ProcedureReturn isSubsetOf(a(), b())
EndProcedure
Procedure isEqualTo(Map a(), Map b())
If MapSize(a()) = MapSize(b()) ProcedureReturn isSubsetOf(a(), b()) EndIf ProcedureReturn 0
EndProcedure
Procedure isEmpty(Map a()) ;boolean
If MapSize(a()) ProcedureReturn 0 EndIf ProcedureReturn 1
EndProcedure
If OpenConsole()
NewMap a() NewMap b() NewMap o() ;for output sets NewMap c() createSet("red blue green orange yellow", a()) PrintN("Set A = " + listSortedSetElements(a()) + " of cardinality " + Str(cardinalityOf(a())) + ".") createSet("lady green red", b()) PrintN("Set B = " + listSortedSetElements(b()) + " of cardinality " + Str(cardinalityOf(b())) + ".") PrintN("'red' is an element of A is " + booleanText(isElementOf("red", a())) + ".") PrintN("'red' is an element of B is " + booleanText(isElementOf("red", b())) + ".") PrintN("'blue' is an element of B is " + booleanText(isElementOf("blue", b())) + ".") unionOf(a(), b(), o()) PrintN(#crlf$ + "Union of A & B is " + listSortedSetElements(o()) + ".") intersectionOf(a(), b(), o()) PrintN("Intersection of A & B is " + listSortedSetElements(o()) + ".") differenceOf(a(), b(), o()) PrintN("Difference of A & B is " + listSortedSetElements(o()) + ".") PrintN(listSortedSetElements(a()) + " equals " + listSortedSetElements(a()) + " is " + booleanText(isEqualTo(a(), a())) + ".") PrintN(listSortedSetElements(a()) + " equals " + listSortedSetElements(b()) + " is " + booleanText(isEqualTo(a(), b())) + ".") createSet("red green", c()) PrintN(#crlf$ + listSortedSetElements(c()) + " is a subset of " + listSortedSetElements(a()) + " is "+ booleanText(isSubsetOf(c(), a())) + ".") PrintN(listSortedSetElements(c()) + " is a proper subset of " + listSortedSetElements(b()) + " is "+ booleanText(isProperSubsetOf(c(), b())) + ".") PrintN(listSortedSetElements(c()) + " is a proper subset of " + listSortedSetElements(a()) + " is "+ booleanText(isProperSubsetOf(c(), a())) + ".") PrintN(listSortedSetElements(b()) + " is a proper subset of " + listSortedSetElements(b()) + " is "+ booleanText(isProperSubsetOf(b(), b())) + ".") PrintN(#crlf$ + "Set C = " + listSortedSetElements(c()) + " of cardinality " + Str(cardinalityOf(c())) + ".") adjoinTo("dog cat mouse", c()) PrintN("Add 'dog cat mouse' to C to get " + listSortedSetElements(c()) + " of cardinality " + Str(cardinalityOf(c())) + ".") disjoinFrom("red green dog", c()) PrintN("Take away 'red green dog' from C to get " + listSortedSetElements(c()) + " of cardinality " + Str(cardinalityOf(c())) + ".") Print(#crlf$ + #crlf$ + "Press ENTER to exit"): Input() CloseConsole()
EndIf</lang>
- Output:
Set A = (blue green orange red yellow) of cardinality 5. Set B = (green lady red) of cardinality 3. 'red' is an element of A is True. 'red' is an element of B is True. 'blue' is an element of B is False. Union of A & B is (blue green lady orange red yellow). Intersection of A & B is (green red). Difference of A & B is (blue lady orange yellow). (blue green orange red yellow) equals (blue green orange red yellow) is True. (blue green orange red yellow) equals (green lady red) is False. (green red) is a subset of (blue green orange red yellow) is True. (green red) is a proper subset of (green lady red) is True. (green red) is a proper subset of (blue green orange red yellow) is True. (green lady red) is a proper subset of (green lady red) is False. Set C = (green red) of cardinality 2. Add 'dog cat mouse' to C to get (cat dog green mouse red) of cardinality 5. Take away 'red green dog' from C to get (cat mouse) of cardinality 2.
Python
In Python, set
is a standard type since Python 2.4.
There is also frozenset
which is an immutable version of set
. (In Python 2.3, they were provided as Set
and ImmutableSet
types in the module sets
.)
Language syntax for set literals is supported starting in Python 3.0 and 2.7.
(For versions prior to 2.7, use set([1, 2, 3, 4])
instead of {1, 2, 3, 4}
. Even in Python 2.7+ and 3.0+, it is necessary to write set()
to express the empty set.)
<lang python>>>> s1, s2 = {1, 2, 3, 4}, {3, 4, 5, 6} >>> s1 | s2 # Union {1, 2, 3, 4, 5, 6} >>> s1 & s2 # Intersection {3, 4} >>> s1 - s2 # Difference {1, 2} >>> s1 < s1 # True subset False >>> {3, 1} < s1 # True subset True >>> s1 <= s1 # Subset True >>> {3, 1} <= s1 # Subset True >>> {3, 2, 4, 1} == s1 # Equality True >>> s1 == s2 # Equality False >>> 2 in s1 # Membership True >>> 10 not in s1 # Non-membership True >>> {1, 2, 3, 4, 5} > s1 # True superset True >>> {1, 2, 3, 4} > s1 # True superset False >>> {1, 2, 3, 4} >= s1 # Superset True >>> s1 ^ s2 # Symmetric difference {1, 2, 5, 6} >>> len(s1) # Cardinality 4 >>> s1.add(99) # Mutability >>> s1 {99, 1, 2, 3, 4} >>> s1.discard(99) # Mutability >>> s1 {1, 2, 3, 4} >>> s1 |= s2 # Mutability >>> s1 {1, 2, 3, 4, 5, 6} >>> s1 -= s2 # Mutability >>> s1 {1, 2} >>> s1 ^= s2 # Mutability >>> s1 {1, 2, 3, 4, 5, 6} >>> </lang>
Racket
<lang racket>
- lang racket
(define A (set 1 2 3 4)) (define B (set 3 4 5 6)) (define C (set 4 5))
(set-union A B) ; gives (set 1 2 3 4 5 6) (set-intersect A B) ; gives (set 3 4) (set-subtract A B) ; gives (set 1 2) (set=? A B) ; gives #f (subset? C A) ; gives #f (subset? C B) ; gives #t </lang>
REXX
REXX doesn't have native set support, but can be easily coded to handle lists as sets. <lang rexx>/*REXX program demonstrates some common SET functions. */ truth.0='false'; truth.1='true' /*common names for truth table. */ set.= /*order of sets isn't important. */
call setAdd 'prime',2 3 2 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 call setSay 'prime' /*a small set of primes (numbers).*/
call setAdd 'emirp',97 97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 call setSay 'emirp' /*a small set of baclward primes. */
call setAdd 'happy',1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 100 94 97 97 97 97 97 call setSay 'happy' /*a small set of happy numbers. */
do j=11 to 100 by 10 /*see if PRIME contains some nums*/ call setHas 'prime',j say ' prime contains' j":" truth.result end /*j*/
call setUnion 'prime','happy','eweion'; call setSay 'eweion' call setCommon 'prime','happy','common'; call setSay 'common' call setDiff 'prime','happy','diff' ; call setSay 'diff' call setSubset 'prime','happy' ; say ' prime is a subset of happy:' truth.result call setEqual 'prime','emirp' ; say ' prime is equal to emirp:' truth.result exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────subroutines─────────────────────────*/ setHas: procedure expose set.; arg _ .,! .;return wordpos(!,set._)\==0 setAdd: return set$('add' ,arg(1),arg(2)) setDiff: return set$('diff' ,arg(1),arg(2),arg(3)) setSay: return set$('say' ,arg(1),arg(2)) setUnion: return set$('union' ,arg(1),arg(2),arg(3)) setCommon: return set$('common',arg(1),arg(2),arg(3)) setEqual: return set$('equal' ,arg(1),arg(2)) setSubset: return set$('subSet',arg(1),arg(2)) /*──────────────────────────────────set$ subroutine─────────────────────*/ set$: procedure expose set.; arg $,_1,_2,_3; set_=set._1; t=_3; s=t; !=1 if $=='SAY' then do; say '[set.'_1"]="set._1; return set._1; end if $=='UNION' then do
call set$ 'add',_3,set._1 call set$ 'add',_3,set._2 return set._3 end
add=$=='ADD';common=$=='COMMON';diff=$=='DIFF';eq=$=='EQUAL';subset=$=='SUBSET' if common | diff | eq | subset then s=_2 if add then do; set_=_2; t=_1; s=_1; end
do j=1 for words(set_); _=word(set_,j); has=wordpos(_,set.s)\==0 if (add & \has) |, (common & has) |, (diff & \has) then set.t=space(set.t _) if (eq | subset) & \has then return 0 end /*j*/
if subset then return 1 if eq then if arg()>3 then return 1
else return set$('equal',_2,_1,1)
return set.t</lang>
- Output:
[set.PRIME]=2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 [set.EMIRP]=97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 [set.HAPPY]=1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 100 94 97 prime contains 11: true prime contains 21: false prime contains 31: true prime contains 41: true prime contains 51: false prime contains 61: true prime contains 71: true prime contains 81: false prime contains 91: false [set.EWEION]=2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 1 10 28 32 44 49 68 70 82 86 91 100 94 [set.COMMON]=7 13 19 23 31 79 97 [set.DIFF]=2 3 5 11 17 29 37 41 43 47 53 59 61 67 71 73 83 89 prime is a subset of happy: false prime is equal to emirp: true
Ruby
Ruby's standard library contains a "set" package, which provides Set
and SortedSet
classes.
<lang ruby>>> require 'set'
=> true
>> s1, s2 = Set[1, 2, 3, 4], [3, 4, 5, 6].to_set # different ways of creating a set
=> [#<Set: {1, 2, 3, 4}>, #<Set: {5, 6, 3, 4}>]
>> s1 | s2 # Union
=> #<Set: {5, 6, 1, 2, 3, 4}>
>> s1 & s2 # Intersection
=> #<Set: {3, 4}>
>> s1 - s2 # Difference
=> #<Set: {1, 2}>
>> s1.proper_subset?(s1) # Proper subset
=> false
>> Set[3, 1].proper_subset?(s1) # Proper subset
=> true
>> s1.subset?(s1) # Subset
=> true
>> Set[3, 1].subset?(s1) # Subset
=> true
>> Set[3, 2, 4, 1] == s1 # Equality
=> true
>> s1 == s2 # Equality
=> false
>> s1.include?(2) # Membership
=> true
>> Set[1, 2, 3, 4, 5].proper_superset?(s1) # Proper superset
=> true
>> Set[1, 2, 3, 4].proper_superset?(s1) # Proper superset
=> false
>> Set[1, 2, 3, 4].superset?(s1) # Superset
=> true
>> s1 ^ s2 # Symmetric difference
=> #<Set: {5, 6, 1, 2}>
>> s1.size # Cardinality
=> 4
>> s1 << 99 # Mutability (or s1.add(99) )
=> #<Set: {99, 1, 2, 3, 4}>
>> s1.delete(99) # Mutability
=> #<Set: {1, 2, 3, 4}>
>> s1.merge(s2) # Mutability
=> #<Set: {5, 6, 1, 2, 3, 4}>
>> s1.subtract(s2) # Mutability
=> #<Set: {1, 2}>
>> </lang>
Scala
<lang scala> object sets {
val set1 = Set(1,2,3,4,5) val set2 = Set(3,5,7,9) println(set1 contains 3) println(set1 | set2) println(set1 & set2) println(set1 diff set2) println(set1 subsetOf set2) println(set1 == set2)
} </lang>
Scheme
Implemented based on lists. Not efficient on large sets. <lang lisp>(define (element? a lst)
(and (not (null? lst)) (or (eq? a (car lst))
(element? a (cdr lst)))))
- util, not strictly needed
(define (uniq lst)
(if (null? lst) lst (let ((a (car lst)) (b (cdr lst))) (if (element? a b)
(uniq b) (cons a (uniq b))))))
(define (intersection a b)
(cond ((null? a) '())
((null? b) '()) (else (append (intersection (cdr a) b) (if (element? (car a) b) (list (car a)) '())))))
(define (union a b)
(if (null? a) b (union (cdr a)
(if (element? (car a) b) b (cons (car a) b)))))
(define (diff a b) ; a - b
(if (null? a) '() (if (element? (car a) b) (diff (cdr a) b) (cons (car a) (diff (cdr a) b)))))
(define (subset? a b) ; A ⊆ B
(if (null? a) #t (and (element? (car a) b)
(subset? (cdr a) b))))
(define (set-eq? a b)
(and (subset? a b) (subset? b a)))</lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const type: charSet is set of char; enable_output(charSet);
const proc: main is func
local const charSet: A is {'A', 'B', 'C', 'D', 'E', 'F'}; var charSet: B is charSet.value; var char: m is 'A'; begin B := {'E', 'F', 'G', 'H', 'I', 'K'}; incl(B, 'J'); # Add 'J' to set B excl(B, 'K'); # Remove 'K' from set B writeln("A: " <& A); writeln("B: " <& B); writeln("m: " <& m); writeln("m in A -- m is an element in A: " <& m in A); writeln("A | B -- union: " <& A | B); writeln("A & B -- intersection: " <& A & B); writeln("A - B -- difference: " <& A - B); writeln("A >< B -- symmetric difference: " <& A >< B); writeln("A <= A -- subset: " <& A <= A); writeln("A < A -- proper subset: " <& A < A); writeln("A = B -- equality: " <& A = B); end func;</lang>
- Output:
A: {A, B, C, D, E, F} B: {E, F, G, H, I, J} m: A m in A -- m is an element in A: TRUE A | B -- union: {A, B, C, D, E, F, G, H, I, J} A & B -- intersection: {E, F} A - B -- difference: {A, B, C, D} A >< B -- symmetric difference: {A, B, C, D, G, H, I, J} A <= A -- subset: TRUE A < A -- proper subset: FALSE A = B -- equality: FALSE
Smalltalk
<lang smalltalk>
- (1 2 3) asSet union: #(2 3 4) asSet.
"a Set(1 2 3 4)"
- (1 2 3) asSet intersection: #(2 3 4) asSet.
"a Set(2 3)"
- (1 2 3) asSet difference: #(2 3 4) asSet.
"a Set(1)"
- (1 2 3) asSet includesAllOf: #(1 3) asSet.
"true"
- (1 2 3) asSet includesAllOf: #(1 3 4) asSet.
"false"
- (1 2 3) asSet = #(2 1 3) asSet.
"true"
- (1 2 3) asSet = #(1 2 4) asSet.
"false" </lang>
Swift
<lang swift>var s1 : Set<Int> = [1, 2, 3, 4] let s2 : Set<Int> = [3, 4, 5, 6] println(s1.union(s2)) // union; prints "[5, 6, 2, 3, 1, 4]" println(s1.intersect(s2)) // intersection; prints "[3, 4]" println(s1.subtract(s2)) // difference; prints "[2, 1]" println(s1.isSubsetOf(s1)) // subset; prints "true" println(Set<Int>([3, 1]).isSubsetOf(s1)) // subset; prints "true" println(s1.isStrictSubsetOf(s1)) // proper subset; prints "false" println(Set<Int>([3, 1]).isStrictSubsetOf(s1)) // proper subset; prints "true" println(Set<Int>([3, 2, 4, 1]) == s1) // equality; prints "true" println(s1 == s2) // equality; prints "false" println(s1.contains(2)) // membership; prints "true" println(Set<Int>([1, 2, 3, 4]).isSupersetOf(s1)) // superset; prints "true" println(Set<Int>([1, 2, 3, 4]).isStrictSupersetOf(s1)) // proper superset; prints "false" println(Set<Int>([1, 2, 3, 4, 5]).isStrictSupersetOf(s1)) // proper superset; prints "true" println(s1.exclusiveOr(s2)) // symmetric difference; prints "[5, 6, 2, 1]" println(s1.count) // cardinality; prints "4" s1.insert(99) // mutability println(s1) // prints "[99, 2, 3, 1, 4]" s1.remove(99) // mutability println(s1) // prints "[2, 3, 1, 4]" s1.unionInPlace(s2) // mutability println(s1) // prints "[5, 6, 2, 3, 1, 4]" s1.subtractInPlace(s2) // mutability println(s1) // prints "[2, 1]" s1.exclusiveOrInPlace(s2) // mutability println(s1) // prints "[5, 6, 2, 3, 1, 4]"</lang>
Tcl
Sets in Tcl are modeled as lists of items, with operations that preserve uniqueness of membership.
<lang tcl>package require struct::set
- Many ways to build sets
set s1 [list 1 2 3 4] set s2 {3 4 5 6} struct::set add s3 {2 3 4 3 2}; # $s3 will be proper set... set item 5
puts "union: [struct::set union $s1 $s2]" puts "intersection: [struct::set intersect $s1 $s2]" puts "difference: [struct::set difference $s1 $s2]" puts "membership predicate: [struct::set contains $s1 $item]" puts "subset predicate: [struct::set subsetof $s1 $s2]"; # NB: not strict subset test! puts "equality predicate: [struct::set equal $s1 $s2]"
- Adding an element to a set (note that we pass in the name of the variable holding the set):
struct::set include s3 $item
- Removing an element from a set:
struct::set exclude s3 $item
- Getting the cardinality:
puts "cardinality: [struct::set size $s3]</lang>
zkl
A simplistic implementation that is fine for smallish sets <lang zkl>var [const] unique = Utils.Helpers.listUnique; class Set {
fcn init { var [const] set = (vm.arglist.copy() : unique(_)) } fcn holds(x) { set.holds(x) } fcn union(setB) { self(set.xplode(),setB.set.xplode()) } fcn intersection(setB){ sb:=setB.set; C:=self(); sc:=C.set; foreach x in (set){ if (sb.holds(x)) sc.append(x) } C } fcn diff(setB){ C:=self(); C.set.extend(set); setB.set.pump(Void,C.set.remove); C } fcn isSubset(setB){ sb:=setB.set; set.pump(Void,'wrap(x){ if (not sb.holds(x)) return(Void.Stop,False); True }) } fcn __opEQ(setB) { ((set.len() == setB.set.len()) and self.isSubset(setB)) }
}</lang>
A := Set(1,2,3,3,3,4); A.set.println(); //--> L(1,2,3,4) A.holds(3).println(); //--> True A.holds(9).println(); //--> False B:=Set("one",2,"three"); A.union(B).set.println(); // -->L(1,2,3,4,"one","three") B.union(A).set.println(); // -->L("one",2,"three",1,3,4) A.union(B).diff(B.union(A)).set.println(); // -->L() A.intersection(B).set.println(); //-->L(2) B.intersection(A).set.println(); //-->L(2) A.diff(B).set.println(); //-->L(1,3,4) B.diff(A).set.println(); //-->L("one","three") A.isSubset(B).println(); //-->False A.isSubset(A).println(); //-->True Set("three",2,2,2,2,2).isSubset(B).println(); //-->True (A==B).println(); //-->False (A==A).println(); //-->True (A==Set(2,3,1,4)).println(); //-->True
- Programming Tasks
- Discrete math
- Data Structures
- Ada
- AutoHotkey
- BBC BASIC
- C
- C++
- Clojure
- CoffeeScript
- Common Lisp
- D
- Dart
- EchoLisp
- Elixir
- Erlang
- F Sharp
- Factor
- FunL
- Go
- Groovy
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- Lasso
- LFE
- Liberty BASIC
- Maple
- Mathematica
- MATLAB
- Octave
- Maxima
- Nemerle
- Nim
- Objective-C
- OCaml
- OoRexx
- PARI/GP
- Pascal
- Perl
- Perl 6
- PicoLisp
- Prolog
- PureBasic
- Python
- Racket
- REXX
- Ruby
- Scala
- Scheme
- Seed7
- Smalltalk
- Swift
- Tcl
- Tcllib
- Zkl
- GUISS/Omit