3.35 meet : Intersection operation

Format

$obj$.meet($zdd1$) $\rightarrow $ $zdd2$

Description

Find out the intersection $\alpha \cap \beta $ of itemsets between itemsets $\alpha $ in $obj$ and itemsets $\beta $ in $zdd1$, and return as ZDD object $zdd2$.

For example, the intersection of itemset abc and bcd are as follows.

  $\displaystyle  \textrm{abc.meet(bcd)} = \textrm{abc} \cap \textrm{bcd} = \textrm{bc}  $    

Find out the intersection of all combinations on multiple operations across itemsets.

  $\displaystyle  \textrm{(abc + a).meet(bcd + b)}  $ $\displaystyle = $ $\displaystyle  \textrm{abc} \cap \textrm{bcd} + \textrm{abc} \cap \textrm{b} + \textrm{a} \cap \textrm{bcd} + \textrm{a} \cap \textrm{b} $    
  $\displaystyle  $ $\displaystyle = $ $\displaystyle  \textrm{bc} + \textrm{b} + 1 + 1 $    
  $\displaystyle  $ $\displaystyle = $ $\displaystyle  \textrm{bc} + \textrm{b} + 2 $    

Weight is computed by expanding the same itemset to multiple instances.

In addition, when $\alpha \cap \beta $ is changed to $\alpha \oplus \beta $ (exclusive OR operation), it becomes delta function.

  $\displaystyle  \textrm{(2abc).meet(bcd)} = \textrm{(abc+abc).meet(bcd)} = \textrm{bc + bc = 2bc}  $    

Example

Example 1: Basic Example

> require 'zdd'
> a=ZDD::itemset("a")
> b=ZDD::itemset("b")
> c=ZDD::itemset("c")
> f=a+2*a*b+3*b

# Find out the intersection of itemset a with each term in the expression a + 2ab + 3b, 
# the result becomes a + 2a + 3 = 3 a + 3.
> f.meet(a).show
 3 a + 3

# The intersection with itemset b becomes 1 + 2b + 3b = 5b + 1.
> f.meet(b).show
 5 b + 1

# The intersection with itemset ab becomes a + 2ab + 3b.
> f.meet(a*b).show
 2 a b + a + 3 b

# Empty itemset is represented by constant number 1, thus the intersection with 1
# with all coefficients becomes 1 + 2 + 3 = 6.
> f.meet(1).show
 6

# Find out the interaction of each itemset in abc + 2ab + bc + 1 with each itemset 
# in the specified argument 2ab + a as follows (remove space between items) 
# abc ∩ 2ab = 2ab
# 2ab ∩ 2ab = 4ab
# bc  ∩ 2ab = 2b
# 1   ∩ 2ab = 2
# abc ∩ a   = a
# 2ab ∩ a   = 2a
# bc  ∩ a   = 1
# 1   ∩ a   = 1
# The result is summarized as 6ab + 3a + 2b + 4.
#
> f=((a*b*c)+2*(a*b)+(b*c)+1)
> g=2*a*b + a
> f.show
 a b c + 2 a b + b c + 1
> g.show
 2 a b + a
> f.meet(g).show
 6 a b + 3 a + 2 b + 4

Related

delta : Delta operation