Multiset

Multiset is a term that varies the amount of term from the set theory. The peculiarity of multi-sets over the ordinary concept of a set is that the elements of a multiset can occur more than once. Accordingly, the amount of operations used for multi-sets have a modified meaning.

In computer science, provide multi-sets ( there also Engl. Called Bag ) is a useful data structure dar. For example, the database language SQL tables treated by default as multisets.

• 6.1 Example

• 7.1 union, intersection and difference

Definition

A multiset over a set is a mapping from the set of natural numbers. The number indicates the number of occurrences of the element in the multiset. The set of all multisets over can be written as. In the other, but to save vertical space used.

Reduced basic quantity

The reduced base amount ( engl. "support" ) of a multiset over the set of relevant elements of, in formulas:

Part multiset

A multiset is called partial (multi) volume of a multi-set if every element of the reduced monthly amount of at least as frequently as in. Formal:

Two multi-sets and are equal if their reduced basic quantities are equal and the multiplicities coincide. You are then in both directions part multisets each other.

Remark

The above definition with the approval of the (actually irrelevant ) 0 value is a generalization of the indicator function in the usual quantities. It enables the provision of a " universe " as the basic amount to which each of the relevant multi quantities used, and simplifies handling in the sequence and comparison.

View

Clearly, a multiset is a set in which each element can occur any number of times. Quantities in this sense are a special case of multisets in which each value occurs only once.

Notation

One lists multisets then such amounts explicitly with braces and writes an element into it as many times as it occurs in the multiset. To distinguish multisets of normal amounts, in their enumeration ( bag for engl. ) Is sometimes also added as a small index. Some authors instead use modified brackets.

Semi - abstract example

It is the multiset over with, and. Then one writes so or or.

Illustrative examples

Take a dice and playing dice 20 times in a row. Then it may be that one

Has thrown. The basic amount is then; the multiplicity of Figure 4; therefore. The multi-set lists on any roll, the order will be left aside:

Another example is the prime factorization of 120:

It can be interpreted as a multiset.

Number of possible multi-sets

Given a set of items. The number of multi-sets over which contain elements, then ( analogous to the binomial coefficients ) as

Referred to. It can well express a binomial coefficient:

This indicates the number of possible outcomes when drawing distinguishable balls from an urn if the order is ignored and each drawn ball is put back in the urn after it has been drawn (see combination with repetition ).

Example

If from an urn with five balls in succession 10 is pulled, each drawn ball is put back in, so there is

Possible combinations when the order of the balls drawn is ignored.

Operations on multisets

A multiset over multisets over may be combined in accordance with the multiplicities. This is provided, with

A function can be extended to a function,

Along with having

We are dealing with a Monadenstruktur.

The functor and can be traced back to another useful operation. extended by a function to a function, namely

With the help of this operation and can be set.

Union, intersection and difference

The (large ) union of two multisets over the same ground set, either directly as

Or by means of

Be specified.

As a small union of two multisets is the smallest multiset

Comprising both considered.

The intersection of two multi-sets over the same ground set is application specific. There are

The second definition can be attributed to the above, if in addition a further operation is introduced. Be then defined by

The average in the second sense is then obtained as with

For the difference of two multisets over the same ground set, there are also at least two meaningful definitions.

For both and. What are the "right " depends on the particular application.

Comment: Be multisets over the primes. With and as ausmultiplizierten multi-sets we have:

• The large group corresponds to that product.
• The small union corresponds to the LCM, ie.
• The first version of the average corresponds to the gcd, ie.
• The first version corresponds to the difference.

Generalizations

If you keep the operations defined in the previous section in, obtained by varying the multiplicity amount related structures.

• Real multiplicities in the interval resulting probability distributions. The multiset basic quantity is the set of possible events. The operation expects functions to generate probability distributions of other sets of events on the basis of events that have occurred, in such order, that can deal with probability distributions as input.
• Allowed for the multiplicities of body elements and also defines a scale, be multisets over A to vectors of a vector space with a basis which is indexed by A. embodies the fact that it is sufficient for the definition of a linear mapping to determine the images of the basis vectors. Similarly, calculated on the basis functions to index pairs in bilinear mappings.