Set
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 how to create a set, and how to test m ∈ S, true if m is an element in set S. Also show each of these set operations:
- 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.
(If, in addition, A is not equal to B, then A is called a true or proper subset of B, written A ⊊ 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. 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), or using a list, a binary search tree or a hash table. The basic test, m ∈ S, is O(n) with a list, O(log n) with a balanced binary search tree, or near O(1) with a hash table.
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>
Python
In Python, the set is a standard type with support in the languages syntax. <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 >>> </lang>