Sets: Collections of Unique Items

Sometimes, you need a collection that simply tracks a group of items where each item is unique and the order doesn't matter. While data structures such as arrays manage ordered sequences and dictionaries handle key-value mappings, they do not provide this specific functionality. This is where sets come into play. A set in Julia, much like its mathematical counterpart, is an unordered collection of distinct elements.

Sets are particularly useful when you need to:

• Quickly determine if an item is part of a collection.
• Ensure that a collection only contains unique items (e.g., removing duplicates from a list).
• Perform standard set operations like unions, intersections, and differences between collections.

Creating Sets

You can create a set in Julia using the Set constructor. If you want to create an empty set, you typically specify the type of elements it will hold. If you create a set with initial elements, Julia can often infer the type.

To create an empty set that will hold integers:

julia> empty_int_set = Set{Int}()
Set{Int64}()

julia> typeof(empty_int_set)
Set{Int64}

Here, Set{Int}() creates an empty set specifically designed to store integers (Int64 is the default integer type on most systems).

To create a set with some initial elements, you can pass an iterable collection (like an array) to the Set constructor:

julia> fruit_set = Set(["apple", "banana", "orange"])
Set{String} with 3 elements:
  "orange"
  "banana"
  "apple"

julia> number_set = Set([1, 2, 2, 3, 1, 4])
Set{Int64} with 4 elements:
  4
  2
  3
  1

Notice two important things in the number_set example:

1. Uniqueness: Even though the input array [1, 2, 2, 3, 1, 4] had duplicate values (1 and 2 appeared twice), the resulting set Set{Int64}{4, 2, 3, 1} only contains each distinct element once.
2. Unordered: The elements in the printed representation of the set (4, 2, 3, 1) are not necessarily in the same order as they were provided or in numerical order. Sets do not guarantee any specific ordering of their elements.

Basic Set Operations

Once you have a set, you can perform several fundamental operations.

Adding Elements

To add an element to a set, use the push! function. If the element is already in the set, the set remains unchanged because elements must be unique.

julia> colors = Set(["red", "green"])
Set{String} with 2 elements:
  "green"
  "red"

julia> push!(colors, "blue")
Set{String} with 3 elements:
  "green"
  "blue"
  "red"

julia> push!(colors, "red") # Adding "red" again
Set{String} with 3 elements:
  "green"
  "blue"
  "red"
# The set still has 3 elements, "red" was not added again.

Checking for Membership

A frequent use of sets is to check if an element is present. This is done using the in keyword or its function form in(element, set). Membership testing is generally very efficient for sets.

julia> names = Set(["Alice", "Bob", "Charlie"])
Set{String} with 3 elements:
  "Alice"
  "Charlie"
  "Bob"

julia> "Bob" in names
true

julia> in("David", names)
false

Removing Elements

To remove an element from a set, you can use pop! or delete!. pop!(set, element) removes the specified element and returns it. If the element is not found, it raises an error. delete!(set, element) removes the element and returns the modified set; it does not error if the element isn't found.

julia> items = Set([10, 20, 30, 40])
Set{Int64} with 4 elements:
  40
  20
  30
  10

julia> pop!(items, 30) # Removes 30
30

julia> items
Set{Int64} with 3 elements:
  40
  20
  10

julia> delete!(items, 20) # Removes 20
Set{Int64} with 2 elements:
  40
  10

julia> pop!(items, 50) # Element 50 is not in the set
ERROR: KeyError: key 50 not found
Stacktrace:
 [1] pop!(s::Set{Int64}, key::Int64)
   @ Base ./set.jl:106
 [2] top-level scope
   @ REPL[8]:1

julia> delete!(items, 50) # Element 50 is not in the set, no error
Set{Int64} with 2 elements:
  40
  10

You can also use pop!(set) without specifying an element to remove and return an arbitrary element from the set. This is useful when you want to process elements one by one without regard to which one you get.

Getting the Size

To find out how many elements are in a set, use the length function:

julia> simple_set = Set(['a', 'b', 'c'])
Set{Char} with 3 elements:
  'c'
  'a'
  'b'

julia> length(simple_set)
3

Set-Theoretic Operations

Julia's sets support standard mathematical set operations, which are powerful for comparing and combining collections.

Union

The union of two sets, denoted $A \cup B$, creates a new set containing all elements that are in set A, in set B, or in both. Julia provides the union function or the ∪ operator (you can type \cup then TAB in the Julia REPL or many editors).

julia> set1 = Set([1, 2, 3])
Set{Int64} with 3 elements:
  2
  3
  1

julia> set2 = Set([3, 4, 5])
Set{Int64} with 3 elements:
  4
  3
  5

julia> union(set1, set2)
Set{Int64} with 5 elements:
  4
  2
  3
  5
  1

julia> set1 ∪ set2 # Using the ∪ operator
Set{Int64} with 5 elements:
  4
  2
  3
  5
  1

Intersection

The intersection of two sets, $A \cap B$, creates a new set containing only the elements that are common to both set A and set B. Use the intersect function or the ∩ operator (typed as \cap then TAB).

julia> set1 = Set([1, 2, 3, 4])
Set{Int64} with 4 elements:
  4
  2
  3
  1

julia> set2 = Set([3, 4, 5, 6])
Set{Int64} with 4 elements:
  4
  3
  5
  6

julia> intersect(set1, set2)
Set{Int64} with 2 elements:
  4
  3

julia> set1 ∩ set2 # Using the ∩ operator
Set{Int64} with 2 elements:
  4
  3

Difference

The difference between two sets, $A \setminus B$ (or $A - B$), creates a new set containing elements that are in set A but not in set B. Julia uses the setdiff function.

julia> set_a = Set(["apple", "banana", "cherry"])
Set{String} with 3 elements:
  "cherry"
  "banana"
  "apple"

julia> set_b = Set(["banana", "date"])
Set{String} with 2 elements:
  "date"
  "banana"

julia> setdiff(set_a, set_b) # Elements in set_a but not in set_b
Set{String} with 2 elements:
  "cherry"
  "apple"

julia> setdiff(set_b, set_a) # Elements in set_b but not in set_a
Set{String} with 1 element:
  "date"

Symmetric Difference

The symmetric difference between two sets, $A \Delta B$, creates a new set containing elements that are in either set A or set B, but not in both. Julia uses the symdiff function.

julia> set_x = Set([10, 20, 30])
Set{Int64} with 3 elements:
  20
  30
  10

julia> set_y = Set([20, 40, 50])
Set{Int64} with 3 elements:
  40
  20
  50

julia> symdiff(set_x, set_y) # Elements in one or the other, but not both
Set{Int64} with 4 elements:
  40
  10
  30
  50
# Result is {10, 30, 40, 50} because 20 is in both.

Iterating Over Sets

You can iterate over the elements of a set using a for loop, just like with arrays. However, remember that sets are unordered, so the elements will be processed in an arbitrary sequence, not necessarily the order they were inserted or any sorted order.

julia> my_set = Set(["cat", "dog", "bird"])
Set{String} with 3 elements:
  "cat"
  "bird"
  "dog"

julia> for animal in my_set
           println("Found a ", animal)
       end
Found a cat
Found a bird
Found a dog
# The order of output might vary.

When to Use Sets

Sets are a valuable tool in your Julia programming toolkit. Consider using a set when:

• You need to store a collection of items where duplicates are not allowed. For example, tracking unique visitors to a website.
• You need to perform very fast checks for the existence of an item in a collection (membership testing). This is often faster than searching through an array, especially for large collections.
• You need to perform logical operations like finding common items between two lists (intersection) or combining two lists while keeping only unique items (union). For example, finding common friends between two users.
• You want to easily remove duplicates from an existing array: unique_items = Set(my_array).

Understanding sets, along with arrays, tuples, and dictionaries, gives you a flexible range of options for structuring and managing data in your Julia programs. Each collection type has its strengths, and choosing the right one can make your code cleaner, more efficient, and easier to understand.