
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.



Task

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


/* 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}}, {{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