## `Dom::Multiset` -- multisets

#### Introduction

`Dom::Multiset` is the domain of multisets, i.e., sets with possibly multiple identical elements.

#### Details

- A multiset is represented by a set of lists of the form [s, m], where s is an element of the multiset and m its multiplicity.
- Multisets can be returned by the system solver `solve`. For example, the input `solve(x^3 - 4*x^2 + 5*x - 2, x, Multiple)` gives all roots of the polynomial x^3 - 4*x^2 + 5*x - 2 in form of the multiset `{[1, 2], [2, 1]}`.
- The standard set operations such as union, intersection and subtraction of sets have been extended to deal with multisets.

  These operations can handle different types of sets, such as sets of type `DOM_SET` and multisets. One may, for example, compute the union of the multiset `{[a, 2], [b, 1]}` and the set `{c}`, which results in the multiset `{[a, 2], [b, 1], [c, 1]}`.

- The elements of the multiset are sorted at the time where the multiset is created. The system function `sort` is used in order to guarantee that exactly one representation exists for a multiset, independent of the sequence in which the arguments appear.

#### Creating Elements

`Dom::Multiset( <s1, s2...>)`

#### Parameters

`s1, s2...` | - | objects of any type

#### Categories

`Cat::Set`

#### Related Domains

`DOM_SET`, `Dom::ImageSet`

#### Details

- `Dom::Multiset``(s1, s2...)` creates the multiset consisting of the elements `s1, s2...`
- Multiple identical elements in `s1, s2`... are collected. For example, the call `Dom::Multiset``(a, b, a, c)` creates a multiset with the elements `a, b, c`. The element `a` has multiplicity two, the other two elements `b` and `c` both have multiplicity one.

#### Entries

isFinite

  is `TRUE` because `Dom::Multiset` represents finite sets.

inhomog_intersect

  a table of the form `T = Proc(multiset, setoftypeT)`. This entry is used internally by the implementation, and thus should not be touched.

inhomog_union

  a table of the form `T = Proc(multiset, setoftypeT)`. This entry is used internally by the implementation, and thus should not be touched.

#### Method normal: normalization of multisets

- `normal(dom set)`
- - This method normalizes every element of `set` using the system function `normal`.
  - This method overloads the function `normal` for multisets, i.e., one may use it in the form `normal(set)`.

#### Method powerset: the power set of a multiset

- `powerset(dom set)`
- - This method computes the power set of the multiset `set`, i.e., all sub-multisets of `set`.
  - The power set of `set` is returned as a set of multisets.

#### Method random: random multiset generation

- `random()`
- - This method returns a randomly generated multiset. It uses the function `random` to create the elements of the random multiset. Therefore, the elements of the returned multiset will be integers.
  - The number of elements created, including their multiplicities, is restricted to 20.

#### Method _index: multiset indexing

- `_index(dom set, index i)`
- - Returns the i-th element s of the multiset `set` and its multiplicity m in form of the list [s, m].

    Note that the elements of the multiset are sorted with the use of the system function `sort`, and thus the order of a multiset depends on the sorting criteria specified by this function.

  - See the method `"op"`.
  - This method overloads the function `_index` for multisets, i.e., one may use it in the form `set[i]`, or in functional notation: `_index(set, i)`.

#### Method contains: check on existence of set elements

- `contains(dom set, any s)`
- - This method returns `TRUE` if `set` does contain `s` (i.e., if `s` is an element of `set`), otherwise `FALSE` is returned. For the comparison of two elements, the system function `_equal` is used, which only tests for syntactical equivalence.
  - This method overloads the function `contains` for multisets, i.e., one may use it in the form `contains(set, s)`.

#### Method equal: test on equality of multisets

- `equal(dom set1, dom set2)`
- - This method tests if the two multisets `set1` and `set2` are equal and returns `TRUE`, `FALSE` or `UNKNOWN`, respectively.
  - The system function `_equal` is used for the test.

#### Method expand: expand a multiset to a sequence of its elements

- `expand(dom set)`
- - This method returns an expression sequence (i.e., an expression of type `"_exprseq"`) of all elements in `set`, appearing in correspondence to their multiplicity. For example, for the multiset {[1, 1], [2, 2], [3, 1]}. the expression sequence 3, 2, 2, 1 is returned.
  - This method overloads the function `expand` for multisets, i.e., one may use it in the form `expand(set)`.

#### Method getElement: extracts one element from a multiset

- `getElement(dom set)`
- - This method returns the first element of `set`.
  - Note that the elements of the multiset are sorted with the use of the system function `sort`, and thus the order of a multiset depends on the sorting criteria specified by this function.
  - This method overloads the function `solvelib::getElement`, i.e., one may use it in the form `solvelib::getElement(set)`.

#### Method has: check on existence of (sub-)expressions

- `has(dom set, any expr)`
- - This method returns `TRUE` if the multiset `set` has a subexpression equal to `expr`, and `FALSE` otherwise.
  - To check whether `expr` is contained as an element of `set` and not as a subexpression of the elements of `set`, the function `contains` must be used.
  - This method overloads the function `has` for multisets, i.e., one may use it in the form `has(set, expr)`.

#### Method map: apply a function to multiset elements

- `map(dom set, function func <, any expr...>)`
- - This method maps the function `func` onto the elements (not onto their multiplicities) of the multiset `set`, with the additional function parameters `expr...` passed to `func`, if given.

    See the system function `map` for details.

  - It overloads the function `map` for multisets, i.e., one may use it in the form `map(set, func...)`.

#### Method multiplicity: multiplicity of an element

- `multiplicity(dom set, any s)`
- - This method returns the multiplicity of the element `s` in the multiset `set`.
  - Elements which are not contained in `set` have multiplicity zero.

#### Method nops: number of different elements in a multiset

- `nops(dom set)`
- - This method returns the number of different elements in `set`.
  - This method overloads the function `nops` for multisets, i.e., one may use it in the form `nops(set)`.

#### Method op: elements of a multiset

- `op(dom set, positive integer i)`
- - Returns the i-th element s of the multiset `set` and its multiplicity m in form of the list [s,m].
  - See also the method `"_index"`.
  - Note that the elements of the multiset are sorted with the use of the system function `sort`, and thus the order of a multiset depends on the sorting criteria specified by this function.
  - This method overloads the function `op` for multisets, i.e., one may use it in the form `op(s, i)`.

#### Method select: selecting of multiset elements

- `select(dom set, function func <, any expr...>)`
- - This method maps the function `func` onto the elements (not onto their multiplicities) of the multiset `set`, with the additional function parameters `expr...` passed on to `func`, if given, and returns a multiset with those elements for which the function call returned `TRUE`.
  - This method overloads the function `select` for multisets, i.e., one may use it in the form `select(set, func...)`. See `select` for details.

#### Method split: splitting a multiset

- `split(dom set, function func <, any expr...>)`
- - This method maps the function `func` onto the elements (not onto their multiplicities) of the multiset `set`, with the additional function parameters, if given, `expr...` passed to `func` and returns a list of three multisets with those elements for which the function call returned `TRUE`, `FALSE`, and `UNKNOWN` respectively.
  - This method overloads the function `split` for multisets, i.e., one may use it in the form `split(set, func...)`. See `split` for details.

#### Method subs: substitution of elements in multisets

- `subs(dom set...)`
- - This method applies the function `subs` with additionally given parameters to the elements (not onto their multiplicities) of the multiset `set`.

    See the system function `subs` for details.

  - This method overloads the function `subs` for multisets, i.e., one may use it in the form `subs(set...)`.

#### Method convert: conversion into a multiset

- `convert(any x)`
- - This method tries to convert `x` into a multiset of domain type `Dom::Multiset`.
  - `FAIL` is returned if the conversion fails.
  - Currently only sets of type `DOM_SET` can be converted into multisets.

#### Method convert_to: multiset conversion

- `convert_to(dom set, any T)`
- - This method tries to convert the multiset `set` into an element of domain type `T`.
  - `FAIL` is returned if the conversion fails.
  - Currently `T` may either be `DOM_SET` to convert the multiset `set` into a set (loosing the multiplicities and the order of the elements of `set`), or `DOM_EXPR` or `"_exprseq"` to convert `set` into an expression sequence (see the method `"expand"` for details).
  - See also the method `"expr"`.

#### Method expr: multiset conversion into an object of a kernel domain

- `expr(dom set)`
- - This method converts `set` into a set of type `DOM_SET` consisting of lists of the form [s, m], where s is an element of `set` and m its multiplicity.

  - This method overloads the function `expr` for multisets, i.e., one may use it in the form `expr(set)`.

#### Method bin_intersect: intersection of two multisets

- `bin_intersect(dom set1, dom set2)`
- - Computes the intersection of `set1` and `set2`.
  - This method is called from routines defined in the category `Cat::Set`, which implements among others the overloading of the function `_intersect` for multisets. One may intersect two multisets directly by `set1 intersect set2`, or in functional notation by `_intersect(set1, set2)`.

#### Method bin_minus: subtraction of two multisets

- `bin_minus(dom set1, dom set2)`
- - Computes `set1` minus `set2`.
  - This method is called from routines defined in the category `Cat::Set`, which implements among others the overloading of the function `_minus` for multisets. One may subtract two multisets directly by `set1 minus set2`, or in functional notation by `_minus(set1, set2)`.

#### Method homog_union: union of multisets

- `homog_union(dom set...)`
- - Computes the union of the given multisets.
  - This method is called from routines defined in the category `Cat::Set`, which implements among others the overloading of the function `_union` for multisets. One may compute the union of two multisets directly by `set1 union set2`, or in functional notation by `_union(set1, set2)`.

#### Method nested_union: union of nested sets

- `nested_union(set setofsets)`
- - This method computes the union of the sets in `setofsets`. The contained sets may be multisets or sets of type `DOM_SET`.
  - This method is called from routines defined in the category `Cat::Set`, which implements among others the overloading of the function `_union` for multisets and sets. One may compute the union of multisets and sets directly by `set1 union set2`, or in functional notation by `_union(set1, set2)`.

#### Example 1

The multiset {a, a, b} consists of the two different elements a and b, where a has multiplicity two and b has multiplicity one:

    >> delete a, b, c:
       set1 := Dom::Multiset(a, a, b)

                                 {[a, 2], [b, 1]}

We create another multiset:

    >> set2 := Dom::Multiset(a, c, c)

                                 {[a, 1], [c, 2]}

Standard set operations such as union, intersection or subtraction are implemented for multisets and can be performed using the standard set operators of MuPAD:

    >> set1 union set2

                             {[b, 1], [a, 3], [c, 2]}

    >> set1 intersect set2

                                     {[a, 1]}

    >> contains(set1, a), contains(set1, d)

                                    TRUE, FALSE

#### Example 2

Some system functions were overloaded for multisets, such as `expand`, `normal` or `split`.

If we apply `expand` to a multiset, for example, we get an expression sequence of all elements of the multiset (appearing in correspondence to their multiplicity):

    >> delete a, b, c, d, e:
       set := Dom::Multiset(a, b, c, a, c, d, c, e, c)

                     {[a, 2], [b, 1], [d, 1], [e, 1], [c, 4]}

    >> expand(set)

                             e, d, c, c, c, c, b, a, a

If you want to convert a multiset into an ordinary set of the domain type `DOM_SET`, use `coerce`:

    >> coerce(set, DOM_SET)

                                  {a, b, c, d, e}

Note: The system function `coerce` uses the methods `"convert"` and `"convert_to"` of the domain `Dom::Multiset`.

Compare the last result with the return value of the function `expr`, when it is applied for multisets:

    >> expr(set)

                     {[a, 2], [b, 1], [d, 1], [e, 1], [c, 4]}

The result is a set of the domain type `DOM_SET`, consisting of lists of the domain type `DOM_LIST` with two entries, an element of the multiset and the corresponding multiplicity of that element.

#### Super-Domain

`Dom::BaseDomain`

#### Changes

- Method `contains` now returns either `TRUE` or `FALSE` instead of an integer.
- Method `convert` expects exactly one argument only and was extended to deal with sets of type `DOM_SET`.
- New entries and methods: `"isFinite"`, `"convert_to"`, `"equal"`, `"getElement"`, `"powerset"`, `"random"`.
- The methods `"_intersect"`, `"_subtract"` and `"_union"` were removed and replaced by the following new entries and methods: `"bin_intersect"`, `"bin_minus"`, `"inhomog_intersect"`, `"inhomog_union"`, `"homog_union"` and `"nested_union"`.
- The methods `"has"`, `"map"`, `"select"`, and `"subs"` now work on the elements only, but not on the multiplicities.
- `Dom::Multiset` is of the new category `Cat::Set`, and therefore offers the new features provided by this category.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000