演算子・メソッド一覧：ぱらぱらめくる『ZDD Ruby Package Documentation』

加算演算子 +
- これは集合で言えば、Union

irb(main):002:0> require 'zdd'
=> true
irb(main):003:0> univ = ZDD::itemset("a b c d e f g")
=> a b c d e f g
irb(main):004:0> a = ZDD::itemset("a")
=> a
irb(main):005:0> b = ZDD::itemset("b")
=> b
irb(main):006:0> c = ZDD::itemset("c")
=> c
irb(main):007:0> d = ZDD::itemset("d")
=> d
irb(main):008:0> e = ZDD::itemset("e")
=> e
irb(main):009:0> f = ZDD::itemset("f")
=> f
irb(main):010:0> g = ZDD::itemset("g")
=> g
irb(main):011:0> is1 = a*b*c + a*d + f
=> a b c + a d + f
irb(main):012:0> is2 = a*b*d + a*d + f*g
=> a b d + a d + f g
irb(main):013:0> is1 + is2
=> a b c + a b d + 2 a d + f g + f

減算演算子 -
- 加算の反対。その辻褄があうようにできている

irb(main):016:0> (is1 + is2) - is2
=> a b c + a d + f
irb(main):017:0> is1
=> a b c + a d + f

乗算演算子 *
- 多項式の積のようなもの。ただし単項の２乗は単項そのまま
- アイテムセットに０次の項が入っていないと、積によってどんどん次数が上がるが、単項の２乗はそのままなので、どんなに次数が高くなっても、すべてのシンボルの個数が最大次数
- これを利用すると、冪集合が次のように作れる

irb(main):018:0> beki = (a+1)*(b+1)*(c+1)
=> a b c + a b + a c + a + b c + b + c + 1

- 制御文を使うと次のようにできる

irb(main):030:0> t=ZDD::constant(1)
=> 1 
irb(main):031:0> univ.each_item{|weight,item|
irb(main):032:1* t*=(item+1)
irb(main):033:1> }
=> true
irb(main):034:0> t
=> a b c d e f g + a b c d e f + a b c d e g + a b c d e + a b c d f g + a b c d f + a b c d g + a b c d + a b c e f g + a b c e f + a b c e g + a b c e + a b c f g + a b c f + a b c g + a b c + a b d e f g + a b d e f + a b d e g + a b d e + a b d f g + a b d f + a b d g + a b d + a b e f g + a b e f + a b e g + a b e + a b f g + a b f + a b g + a b + a c d e f g + a c d e f + a c d e g + a c d e + a c d f g + a c d f + a c d g + a c d + a c e f g + a c e f + a c e g + a c e + a c f g + a c f + a c g + a c + a d e f g + a d e f + a d e g + a d e + a d f g + a d f + a d g + a d + a e f g + a e f + a e g + a e + a f g + a f + a g + a + b c d e f g + b c d e f + b c d e g + b c d e + b c d f g + b c d f + b c d g + b c d + b c e f g + b c e f + b c e g + b c e + b c f g + b c f + b c g + b c + b d e f g + b d e f + b d e g + b d e + b d f g + b d f + b d g + b d + b e f g + b e f + b e g + b e + b f g + b f + b g + b + c d e f g + c d e f + c d e g + c d e + c d f g + c d f + c d g + c d + c e f g + c e f + c e g + c e + c f g + c f + c g + c + d e f g + d e f + d e g + d e + d f g + d f + d g + d + e f g + e f + e g + e + f g + f + g + 1

- こうもできる

irb(main):036:0> ["a","b","c"].each{|item|
irb(main):037:1* t*=(item+1)
irb(main):038:1> }
=> ["a", "b", "c"]
irb(main):039:0> t
=> a b c + a b + a c + a + b c + b + c + 1

剰余演算子 %、除算演算子 /
- ZDDa/ZDDb = ZDDc * ZDDb + ZDDd という関係を満足している
- ZDDcの決め方は、ZDDaのすべての項についてZDDbのすべての項で除算をする。全除算に共通して存在しているZDDbの項について、最小係数をつけて足し合わせたものをZDDcとする
- ZDDaを集合の集まりの山脈として、その内部にあるZDDbがZDDc倍は存在する、というような解釈
- アイテムa,b,cがあって、それがA,B,C個ずつあるとき、多項式 $A a + B b + C c$ と表すが、それをZDD(これも多項式とみなす)で割ったときの商と余り
比較演算子
- 等価比較演算子、以上比較演算子、大なり比較演算子、以下比較演算子、小なり比較演算子、不等比較演算子
- ２つのアイテム集合を項ごとに比較して、その係数が「等価」「以上」「大なり」「以下」「小なり」「不等」であるか否かを判定し

irb(main):002:0> require 'zdd'
=> true
irb(main):003:0> a = ZDD::itemset("a")
=> a
irb(main):004:0> (a*(-2)).show
 - 2 a
=>  - 2 a
irb(main):005:0> b = ZDD::itemset("b")
=> b
irb(main):006:0> c = ZDD::itemset("c")
=> c
irb(main):007:0> d = ZDD::itemset("d")
=> d
irb(main):008:0> is1 = a*4 + b*3 + c*2 + d + ZDD::constant(1)
=> 4 a + 3 b + 2 c + d + 1 
irb(main):009:0> is2 = a + b*2 + c*3 + d*4 + ZDD::constant(1)*5
=> a + 2 b + 3 c + 4 d + 5 
irb(main):011:0> is1==is2
=> 
irb(main):012:0> is1>=is2
=> a + b
irb(main):013:0> is1>is2
=> a + b
irb(main):014:0> is1<=is2
=> c + d + 1 
irb(main):015:0> is1<is2
=> c + d + 1 
irb(main):016:0> is1.ne?(is2)
=> a + b + c + d + 1

constant
- 定数もZDDオブジェクトにしておき、ZDD演算に乗せる

ONE = ZDD.const(1)

cost
- 各シンボルは値を持つが(デフォルトは0.5)、多項式の値を返すのがcost演算子
- デフォルトが0.5なのは(おそらく)、シンボルがあるかないかの全通り $2^k$ のそれぞれの項の確率が二項分布になることを基準としたかったからだろう
count
- 項数を数える

$LOAD_PATH.push("/home/ryamada/.gem/ruby/2.2.0/gems/zdd-1.0.0-linux/lib/nysol/")
require "zdd"

univarray = ('a'..'z').to_a
ONE = ZDD::constant(1)
univ=ONE
univarray.each{|item|
 univ*=(ZDD::itemset(item)+1)
}

m1 = ONE
(univarray.sample(10)).each{|item|
 m1*=ZDD::itemset(item)
}

m2 = ONE
(univarray.sample(15)).each{|item|
 m2*=ZDD::itemset(item)
}

m3 = ONE
(univarray.sample(12)).each{|item|
 m3*=ZDD::itemset(item)
}

#M = m1 + m2 + m3
#M2 = M*M

def ZDDpow(z,k)
  ret = z
  for i in 2..k
    ret *= z
  end
  ret
end

k = 10

puts (ZDDpow(m1+m2+m3+ONE,k)).count

delta, meet
- 排他的論理和演算と論理和(共通集合)演算
- 要素ワイズに排他的論理和・論理和演算をしてその結果を返す
density
- 登録されている全アイテムから構成可能なアイテム集合の総数に対する$obj$に格納されたアイテム集合の数の割合
each,each_item
- ruby式の要素列挙
- eachはアイテム集合を列挙
- each_itemはアイテム集合の要素ごとにアイテムを取り出し、それを列挙。重み情報とかも出す

irb(main):265:0> M.each{|item|
irb(main):266:1* item.show
irb(main):267:1> }
 a d e
 b c d e
 b c d
=> true

irb(main):269:0> M.each_item{|weight,item,top,bottom|
irb(main):270:1*   puts weight
irb(main):271:1>   item.show
irb(main):272:1>   puts top
irb(main):273:1>   puts bottom
irb(main):274:1>   puts "----------"
irb(main):275:1> }
1
 a
true
false
----------
1
 d
false
false
----------
1
 e
false
true
----------
1
 b
true
false
----------
1
 c
false
false
----------
1
 d
false
false
----------
1
 e
false
true
----------
1
 b
true
false
----------
1
 c
false
false
----------
1
 d
false
true
----------
=> true

export,import
- exportはZDDの２種類のエッジの行き先ノードを指定した形式の出力
- importはファイルに書きだしたexportの出力形式を読み込む

irb(main):278:0> M.export
_i 26
_o 1
_n 6
248 22 F T
250 23 F 249
376 24 F 250
378 25 F 376
280 23 F 248
380 26 378 280
380
=> a d e + b c d e + b c d

iif
- 条件によってアイテムセットのアイテムを選び出す
items
- アイテム集合を「のべ」で考えて、アイテムの重み総和としてアイテムの１次線形和として返す
lcm
- トランザクションファイル(買い物ごとの購入物リストのファイル)を読み込んで、(高速な)LCM over ZDDアルゴリズムを使って頻出パターンを列挙する
maxcost, maxcover,mincost,mincover
- アイテム集合の中で最大・最小コストのアイテムを返す
maxweight,minweight,total
- アイテムの中で最大・最小のコスト、ZDD全体のコストの値を返す
permit, restrict
- アイテム集合のそれぞれが、引数アイテム集合のいずれかに含まれているかどうかを判定し、「含まれる側」を返すのがpermit、「含む側」を返すのがrestrict
permitsym
- アイテム集合のうち、指定数以下のアイテムの積となっているものを返す
same?
- ZDDの同一判定
size,totalsize
- 1つのZDDの節点数、扱っているすべてのZDDの節点数
tersmEQ,termsGE,termsGT,termsLE,termsLT,termsNE
- 係数が等しい、以上、より大きい、以下、より小さい、等しくない、を判定基準としてそれに合致する項を返す
to_a,to_i,to_s
- rubyのアレイ、整数、文字列への変換