Set

From Rosetta Code
Task
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.

You may see other such structures in the Data Structures category.

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>

  1. include <set>
  2. include <iostream>
  3. include <iterator>
  4. 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>

Haskell

Works with: GHC

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

  1. fail unless s1 and s2 contain the same elements

procedure set_equals (s1, s2) 

 return subset(s1, s2) & subset(s2, s1)

end

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

Works with: Java version 7+

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


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

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


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


  1. Union
(uniq (append Set1 Set2))

-> (1 2 3 7 abc "def" (u v w) 5 hello (x y z))


  1. Intersection
(sect Set1 Set2)

-> (2 3)


  1. Difference
(diff Set1 Set2)

-> (1 7 abc "def" (u v w))


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


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


  1. Get contents
(idx 'Set1)

-> (1 2 3 7 abc "def" (u v w))

(idx 'Set2)

-> (2 3 5 hello (x y z))


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


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


  1. Intersection
(sect (idx 'Set1) (idx 'Set2))

-> (2 3)


  1. Difference
(diff (idx 'Set1) (idx 'Set2))

-> (1 7 abc "def" (u v w))


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


  1. Test for equality
(= (idx 'Set1) (idx 'Set2))

-> NIL

(= (idx 'Set2) (idx 'Set2))

-> T</lang>

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

Works with: Python version 2.7+ and 3.0+

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

Tcl

Sets in Tcl are modeled as lists of items, with operations that preserve uniqueness of membership.

Library: Tcllib (Package: struct::set)

<lang tcl>package require struct::set

  1. 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]"

  1. Adding an element to a set (note that we pass in the name of the variable holding the set):

struct::set include s3 $item

  1. Removing an element from a set:

struct::set exclude s3 $item

  1. Getting the cardinality:

puts "cardinality: [struct::set size $s3]</lang>

Retrieved from "https://rosettacode.org/wiki/Set?oldid=200754"