Unable to remove the smallest element from a Set

General Usage
1

I have a set of Characters A to Z which are represented by int64 1,2,3…,26 in a set. I want to remove the smallest character A from the set but my code does not work and I could not figure out why

"""
  Create a set of 26 alphabets
"""

AlphabetSet = Set{Int64}(1:26)

@inline function elementsofset(S::Set)
    return [ element for element in S ]
end

function elementsofsetsorted(S::Set,args...)
    return sort(elementsofset(S,args...))
end

arrayofelements = elementsofset(AlphabetSet)
sortedarrayofelements = elementsofsetsorted(AlphabetSet)

function pop_smallest!(S::Set)
    temparr = elementsofsetsorted(S)
    element = popfirst!(temparr)
    S = Set(temparr)
    return element
end

z = pop_smallest!(AlphabetSet)
println(length(AlphabetSet))
println(AlphabetSet)

The output is

julia> 
26
Set([5, 16, 20, 12, 24, 8, 17, 1, 19, 22, 23, 6, 11, 9, 14, 3, 7, 25, 4, 13, 15, 2, 10, 18, 21, 26])

I except the AlphabetSet to have a length of 25 with the integer value 1 removed but instead it still have 26 elements.

2

The function, as is, is not very efficient. Getting the smallest element, does not require sorting all the elements. The other big problem is that S = Set(temparr) does not mutate S as intended, it just binds the S name to a different set, leaving the set variable in the calling scope bound to the original set, and thus unchanged.

A working way of implementing this could be:

function pop_smallest!(S::Set)
    e = minimum(S)
    delete!(S, e)
    return e
end

See this section of the manual: Variables · The Julia Language

3

Yes, I found that delete! works. And I should write my own code to find the smallest element. Thank you.

function pop_smallest!(S::Set)
    if length(S) == 0
        return nothing
    end
    local smallest = minimum(elementsofset(S))
    delete!(S,smallest)
    return smallest
end
4

minimum(elementsofset(S)) can be minimum(S) as minimum is defined on sets too. The elementsofset call creates a new vector of set elements which allocates and is wasteful.

If the set is very dynamic, i.e. elements are added and the minimum element removed many times, then you might want to consider a specialized data structure from DataStructures.jl package.

2 Likes