I have reviewed codes zdd.pl on ZDD in Pack pac for easy
writing queries on ZDD. Although I could not add any new features, I hope ZDD library in pac could be usable for those who would play something around ZDD. Instead of giving tutorial
I chosen only a few of queries from many ones commented in the codes. They could be reproducible on latest pac 1.8.2 like this as usual, assuming it is installed.
Query Preparation
?- use_module(library(pac)).
true.
?- use_module(zdd(zdd)).
true.
?- module(zmod).
true.
zmod: ?- zdd X << pow([1,2,3]), C << card(X), psa(X).
zid = 4
[]
[3]
[2]
[2,3]
[1]
[1,3]
[1,2]
[1,2,3]
-------------------
X = 4,
C = 8.
I am far from zdd expert, and still all what I know about ZDD is
that it is a system handling families of sets (FOS) of given total ordered set of atoms. Basic set theoretical operations on them are well known and clear for all. Although the zdd library implemented here is currently a work by an amateur, FOS seems interesting data type also for Prolog, he would like to continue to work on little by little further.
BTW, I found that families of lists of given atoms without order
also interesting. Queries below include computing functions and permutationons using such lists.
Have a fun.
Sample queries on families of sets and lists
?- zdd X << pow([a,b]), Y << pow([c,d]), Z << X+Y, U << card(Z).
X = 3,
Y = 5,
Z = U, U = 7.
?- zdd X << pow([a,b]), Y << pow([c,d]), Z << :arith(X+Y).
X = 3,
Y = 5,
Z = 8.
?- zdd X << pow([a,b]), Y << pow([c,d]), { Z is X+Y }.
X = 3,
Y = 5,
Z = 8.
?- numlist(1, 16, L), (zdd X << pow(L), card(X, C)).
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
X = 17,
C = 65536.
?- N = 100, M = 100, numlist(1, N, Ns), numlist(1, M, Ms),
time(( zdd all_fun(Ns, Ms, F), card(F, C))).
% 33,627,275 inferences, 2.652 CPU in 2.874 seconds (92% CPU, 12678161 Lips)
N = M, M = 100,
Ns = Ms, Ms = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
F = 505101,
C = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 .
?- time(( zdd F << all_fun(:numlist(1, 100), :numlist(1, 100)), card(F, C))).
% 33,627,566 inferences, 3.144 CPU in 3.366 seconds (93% CPU, 10694590 Lips)
F = 505101,
C = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 .
?- zdd Is << all_mono([1,2],[a,b,c]), psa(Is).
zid = 15
[1-c,2-b]
[1-c,2-a]
[1-b,2-c]
[1-b,2-a]
[1-a,2-c]
[1-a,2-b]
-------------------
Is = 15.
?- zdd F << all_epi([a,b,c],[1,2]), psa(F).
zid = 16
[a-2,b-2,c-1]
[a-2,b-1,c-2]
[a-2,b-1,c-1]
[a-1,b-2,c-2]
[a-1,b-2,c-1]
[a-1,b-1,c-2]
-------------------
F = 16.
?- time((zdd Ps << all_perm(:numlist(1, 15)), C << card(Ps))).
% 84,009,018 inferences, 31.345 CPU in 31.648 seconds (99% CPU, 2680145 Lips)
Ps = 1105921,
C = 1307674368000.