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

Subset iterators for sets and multisets

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

Sub-sets of a given size

subsets — Method
subsets(s::Set, k::Int; inplace::Bool=false) -> SubSetSizeItr{T}

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

If inplace is true, the elements of the iterator may share their memory. This means that an element returned by the iterator may be overwritten 'in place' in the next iteration step. This may result in significantly fewer memory allocations. However, using the in-place version is only meaningful if just one element of the iterator is needed at any time. For example, calling collect on this iterator will not give useful results.

Examples

julia> for i in subsets(Set(["a","b","c"]), 1)
         println(i)
       end
Set(["a"])
Set(["b"])
Set(["c"])

julia> collect(subsets(Set([1:5;]), 2))
10-element Vector{Set{Int64}}:
 Set([3, 1])
 Set([2, 1])
 Set([4, 1])
 Set([5, 1])
 Set([2, 3])
 Set([4, 3])
 Set([5, 3])
 Set([4, 2])
 Set([5, 2])
 Set([5, 4])
source