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.
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, 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.find(key) != set.end();
}
template <class T> std::set<T> set_union(std::set<T> a, const std::set<T>& b) {
a.insert(b.begin(), b.end()); return a;
}
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';
} </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>
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}
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>
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
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
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
Objective-C
<lang objc>#import <Foundation/Foundation.h>
int main (int argc, const char *argv[]) {
NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; 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); [pool release]; 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.
<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 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 from_list lst = List.fold_right IntSet.add lst IntSet.empty;; (* Convenience function for constructing a set from a list *)
val from_list : IntSet.elt list -> IntSet.t = <fun>
- let s1 = from_list [1;2;3;4;3];;
val s1 : IntSet.t = <abstr>
- IntSet.elements s1;;
- : IntSet.elt list = [1; 2; 3; 4]
- let s2 = from_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 (from_list [3;1]) s1;;
- : bool = true
- IntSet.equal (from_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>
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.
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
Perl
Primitive set 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>
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.
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>
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>
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>
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>
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>