ILP Part 15 – Basic set operations

This is the fifteenth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to use comparisons to implement few basic set operations. Let’s go.

In set, Not in set

We start with In set operation. For set x = \{x_1, x_2, \ldots, x_n \} and value v we want to ask whether v is in set x. This is very easy because all we need to do is compare v with all values from set and calculate the sum:

    \begin{gather*} \displaystyle\mathop{\forall}_{i=1}^{n} b_i = x_i \stackrel{?}{=} v \\ b = \sum_{i=1}^{n} b_i \stackrel{?}{\ge} 1 \end{gather*}

For every value we calculate variable b_i which is true when x_i is equal to v. Next, we sum all values and check whether the sum is positive. If it is true then b is true which means that v is in set x.
For operation Not in set we do almost the same. The only difference is in comparing the sum with 0.

Different values count

Very similar operation is a Different values count. For multiset (e.g., set with repetitions) x = \{x_1, x_2, \ldots, x_n \} we want to ask how many different values does it contain. The formula is as follows:

    \begin{gather*} \displaystyle\mathop{\forall}_{i=1}^{n} d_i = \displaystyle\mathop{\wedge} _{j=i+1}^{n} x_i \stackrel{?}{\neq} x_j \\ d = \sum_{i=1}^{n} d_i \end{gather*}

For every variable x_i we check whether all variables with indexes greater than i are different than x_i. Basically, we traverse multiset x in some arbitrary order and for i-th value we check whether all remaining values are different.

All different

We can use previous formula to make sure that all values in mulitset are different (so the multiset is in fact set). To achieve that we need to calculate different values count d and add constraint d = n where n is a number of variables in a multiset.


Today we implemented useful set operations. Next time we are going to utilize all ILP knowledge to solve real problem — we will be solving a simple cube riddle.