GitHub

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.

MSet — Type
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.

multiset — Function
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:

multiplicities — Method
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
multiplicity — Method
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

subsets — Method
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

subsets — Method
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

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

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

source