L05: Multisets Flashcards
What is the occurrence model for the Golomb Ruler Problem?
- In our explicit model, we could create a set with 2^n - 1 elements
- Invoking our occurrence representation pattern, we begin with an array O indexed 0..2^n - 1
How can we express the distinct distances constraint for the occurrence model of the Golomb Ruler Problem?
- Bit shifting
- We can consider an array O1, which contains the same variables as O, shifted 1 position right
- That means that O[0] is O1[1]
- We can then assign the variables such that the scalar vector of the arrays is 1
- By shifting the array by 1, we can determine how many ticks have a distance of 1 (hence why we want the scalar product to only be one)
- We can then get the scalar product for a shift of 2, 3, 4, etc, until we have a scalar product of 1 for each
- This will give us unique ticks for each value, and the solution will be optimal (minimising the maximum length of the ruler for a given n)
- This does not introduce new variables, it just re-uses existing variables in new arrays
What is a multiset?
- A collection of distinct objects
- Repetition is allowed
- Elements are not arranges in any particular order
- E.g. {1, 2, 3, 1}
- E.g. {red, green, blue, green, red}
- Characterised by the number of times each object occurs in the multiset
What is the domain of a set?
- Sets have a finite size as all the elements can only appear once
What is the domain of a multiset?
- The domain is infinite (if the domain S is non-empty)
- If S = {1}, then the multiset of S = {{}, {1}, {1, 1}, {1 ,1, 1}, …}
How can we bound the number of elements in a multiset?
To ensure that the length of a multiset is finite, we do either of the following:
- Limit the total number of elements in the set (cardinality of the set)
- Bound the number of occurrences of each value
What is the explicit fixed-cardinality representation of a multiset?
- Explicit fixed-cardinality: find a multiset of n digits
- We can have an array indexed 1..n where the domain of each variable is 0..9 (for this example)
- We do not apply the AllDifferent constraint
How do we remove equivalence classes in a multiset?
We can order the set in an ascending order, but use the operator <= as we can have more than one of the same element
What is the occurrence representation of a multiset?
- We use the same representation for both fixed- and bounded-cardinality sets
- Find a multiset of n (or at most n) digits
- We have an array indexed by our domain (in this example 0..9), with the domain for each variable being 0..n (as each variable in the multiset can appear multiple times)
- Fixed-cardinality n: Sum is n
- Bounded-cardinality: Sum is at most n
What is the explicit bounded-cardinality representation of a multiset?
- Explicit bounded-cardinality: find a multiset of at most n digits
- We have an array indexed 1..n where the domain of each variable is 0..9 (for this example)
- We also have a switch array indexed 1..n where the domain of each variable is 0/1 (or we can use a marker variable)
- As this is a bounded-cardinality multiset, we need to know which values are unused
What is a relation?
- Assigns truth values to tuples of values
- In this sense, constraints are relations that are true
Examples
- Set P is {Bill, Bert, Tom}
- Binary relation ‘likes’ on PxP might assign:
- <Bill, Bert>, <Bert, Tom> true
- Bill likes Bert, Bert likes Tom
- All other combinations are false
What is the occurrence representation of a relation?
Find a relation R between the sets
- A = {1, 2, 3}
- B = {2, 3, 4}
such that each element of A is related to at least one element of B
We can draw a table with the heading as the values of A and B
The value in each cell of the table is 0/1, depending on whether the tuple is false/true
What is the projection of a relation?
- A common operation on relations
- We project a relation onto 1 or more of its arguments to result in a relation with a reduced arity
Example:
- Set P is {Bill, Bert, Tom}.
- Relation likes on P x P = {<Bill, Bert>, <Bert, Tom>, <Bert, Bill>}.
- Project likes onto Bert (first position): {Tom, Bill}
How can we find a relation R between sets
A = {1, 2, 3} and B = {2, 3, 4}
such that each element of A is related to at least one element of B
To fulfil this constraint, we can look at the table and do a summation of each row (where we see all the relations for each value of A) and if it is >= 1, then there is at least one relation for that element of A
The projection of R onto each element of A has a size of at least 1
How do we use a occurrence representation for k-ary relations?
We use a k-dimensional matrices
