Multi-sets and sub-set iterators

Multi-sets

Type and constructors

Objects of type MSet consists of a dictionary whose keys are the elements in the set, and the values are their respective multiplicity.

MSetType
MSet{T} <: AbstractSet{T}

Type for a multi-set, i.e. a set where elements are not unique, they (can) have a multiplicity. MSets can be created from any finite iterator.

Examples

julia> MSet([1,1,2,3,4,4,5])
MSet{Int64} with 7 elements:
5
4 : 2
2
3
1 : 2

4 : 2 means the element 4 has multiplicity 2, i.e. was included twice.

source

We can create multi-sets from any finite iterator, dictionary or pair of lists with the appropriate conditions.

multisetFunction
multiset(iter) -> MSet{eltype(iter)}
multiset(d::Dict{T, Int}) -> MSet{T}
multiset{l::Vector{T}, m::Vector{Int}} -> MSet{T}

Given either:

• a finite iterator iter;
• a dictionary d whose values are positive integers;
• a list l and a list of positive integers m of same length as l;

return the asscciated multi-set M.

Examples

julia> str = "A nice sentence"
"A nice sentence"

julia> multiset(str)
MSet{Char} with 15 elements:
'n' : 3
'A'
'c' : 2
'i'
'e' : 4
's'
't'
' ' : 2

julia> multiset(Int[x^3%8 for x = 1:50])
MSet{Int64} with 50 elements:
0 : 25
5 : 6
7 : 6
3 : 6
1 : 7

julia> d = Dict("a" => 4, "b" => 1, "c" =>9)
Dict{String, Int64} with 3 entries:
"c" => 9
"b" => 1
"a" => 4

julia> multiset(d)
MSet{String} with 14 elements:
"c" : 9
"b"
"a" : 4

julia> multiset(["a", "b", "c"], [4, 1, 9])
MSet{String} with 14 elements:
"c" : 9
"b"
"a" : 4
source
multiset(T::Type) -> MSet{T}

Create an empty multi-set M with elements of type T.

Examples

julia> multiset(QQFieldElem)
MSet{QQFieldElem}()

julia> multiset()
MSet{Any}()
source

Functions

One can iterate over an MSet as on a regular Set. Here is moreover a list of functions defined for collections of objects which are currently available for MSet:

• ==
• all
• any
• copy
• delete!
• eltype
• filter
• filter!
• in
• intersect
• intersect!
• isempty
• issubset
• length
• pop!
• push!
• setdiff
• setdiff!
• similar
• unique
• union
• union!
• ...

Note that pop! and delete! for MSet are available but have a different behaviour. For an element x in an multi-set M <: MSet, then pop!(M, x) will remove one instance of x in M - in particular multiplicity(M, x) will drop by $1$. Much stronger, delete!(M, x) will remove all instances of x in M and so multiplicity(M, x) will be $0$.

While unique will return the keys of the underlying dictionary, one can access the values (i.e. the multiplicities of the elements in the multi-set) via the following functions:

multiplicitiesMethod
multiplicities(s::MSet{T}) -> ValueIterator{Dict{T, Int}}

Return an iterator for the multiplicities of all the elements in s.

Examples

julia> m = multiset([1,1,2,3,4,4,5])
MSet{Int64} with 7 elements:
5
4 : 2
2
3
1 : 2

julia> mult_m = multiplicities(m)
ValueIterator for a Dict{Int64, Int64} with 5 entries. Values:
1
2
1
1
2

julia> collect(mult_m)
5-element Vector{Int64}:
1
2
1
1
2
source
multiplicityMethod
multiplicity(s::MSet{T}, x::T) -> Int

Return the multiplicity of the element x in the multi-set s. If x is not in s, return 0.

Examples

julia> m = multiset([1,1,2,3,4,4,5])
MSet{Int64} with 7 elements:
5
4 : 2
2
3
1 : 2

julia> multiplicity(m, 2)
1

julia> multiplicity(m, 6)
0
source

Finally, the sum and difference for MSet are also available. Difference is given by the complements of sets and the sum is given by disjoint union of sets.

+Method
(+)(s::MSet, itrs...) -> MSet

Return the multi-sets associated to the disjoint union of s and the collections of objects in itrs.

Examples

julia> m = multiset("A nice sentence")
MSet{Char} with 15 elements:
'n' : 3
'A'
'c' : 2
'i'
'e' : 4
's'
't'
' ' : 2

julia> n = multiset("A very nice sentence")
MSet{Char} with 20 elements:
'n' : 3
'e' : 5
'A'
'y'
'i'
'r'
's'
't'
' ' : 3
'c' : 2
'v'

julia> m + n
MSet{Char} with 35 elements:
'n' : 6
'e' : 9
'A' : 2
's' : 2
'i' : 2
't' : 2
'y'
'r'
' ' : 5
'c' : 4
'v'
source
-Method
(-)(s::MSet, itrs...) -> MSet

Return the multi-set associated to the complement in s of the collections in itrs.

Alias for setdiff(s, itrs...).

Examples

julia> m = multiset("A very nice sentence")
MSet{Char} with 20 elements:
'n' : 3
'e' : 5
'A'
'y'
'i'
'r'
's'
't'
' ' : 3
'c' : 2
'v'

julia> n = multiset("A nice sentence")
MSet{Char} with 15 elements:
'n' : 3
'A'
'c' : 2
'i'
'e' : 4
's'
't'
' ' : 2

julia> n-m
MSet{Char}()

julia> m-n
MSet{Char} with 5 elements:
'e'
'y'
'r'
' '
'v'
source

Sub-set iterators

Sub-multi-sets

subsetsMethod
subsets(s::MSet) -> MSubSetIt{T}

Return an iterator on all sub-multi-sets of s.

source
subsets(s::Set) -> SubSetItr{T}

Return an iterator for all sub-sets of s.

source
subsets(s::Set, k::Int) -> SubSetSizeItr{T}

Return an iterator on all sub-sets of size k of s.

source
subsets(v::Vector{T}, k::Int) where T

Return a vector of all ordered k-element sub-vectors of v.

source

Sub-sets

subsetsMethod
subsets(s::MSet) -> MSubSetIt{T}

Return an iterator on all sub-multi-sets of s.

source
subsets(s::Set) -> SubSetItr{T}

Return an iterator for all sub-sets of s.

source
subsets(s::Set, k::Int) -> SubSetSizeItr{T}

Return an iterator on all sub-sets of size k of s.

source
subsets(v::Vector{T}, k::Int) where T

Return a vector of all ordered k-element sub-vectors of v.

source

Sub-sets of a given size

subsetsMethod
subsets(s::Set, k::Int) -> SubSetSizeItr{T}

Return an iterator on all sub-sets of size k of s.

source