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) -> SubSetSizeItr{T}

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

source