TCS -TR-A-06-17

TCS Technical Report

Generating Frequent Closed Item Sets Based on
Zero-suppressed BDDs
by

Shin-ichi Minato

Division of Computer Science
Report Series A
July 3, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Generating Frequent Closed Item Sets Based on Zero-suppressed BDDs
Shin-ichi Minato
Division of Computer Science, Hokkaido University
North 14, West 9, Sapporo, 060-0814 Japan

July 3, 2006

ever, most of such item set mining algorithms focused on just enumerating or listing the item set
patterns which satisfy the given conditions and it
was a diﬀerent matter how to store and index theresult of patterns for eﬃcient data analysis.

(Abstract) Frequent item set mining is one of
the fundamental techniques for knowledge discovery and data mining. In the last decade, a number
of eﬃcient algorithms for frequent item set mining have been presented, but most of them focusedon just enumerating the item set patterns which
satisfy the given conditions, and it was a diﬀerent
matter how to store and index the result of patterns
for eﬃcient data analysis. Recently, we proposeda fast algorithm of extracting all frequent item set
patterns from transaction databases and simultaneously indexing the result of huge patterns using
Zero-suppressed BDDs (ZBDDs). That method,ZBDD-growth, is not only enumerating/listing thepatterns eﬃciently, but also indexing the output
data compactly on the memory to be analyzed withvarious algebraic operations. In this paper, we
present a variation of ZBDD-growth algorithm togenerate frequent closed item sets. This is a quite
simple modiﬁcation of ZBDD-growth, and additional computation cost is relatively small compared with the original algorithm for generating
all patterns. Our method can conveniently be utilized in the environment of ZBDD-based patternindexing.

1

Recently, we proposed a fast algorithm[8] of extracting all frequent item set patterns from transaction databases, and simultaneously indexing theresult of huge patterns on the computer memory
using Zero-suppressed BDDs. That method, called
ZBDD-growth, does not only enumerate/list thepatterns eﬃciently, but also indexes the output
data compactly on the memory. After mining, theresult of patterns can eﬃciently be analyzed by using algebraic operations.
The key of the method is to use BDD-based
data structure for representing sets of patterns.
BDDs[2] are graph-based representation of Booleanfunctions, now widely used in VLSI logic designand veriﬁcation area. For the data mining applications, it is important to use Zero-suppressed BDDs(ZBDDs)[7], a special type of BDDs, which aresuitable for handling large-scale sets of combinations. Using ZBDDs, we can implicitly enumeratecombinatorial item set data and eﬃciently computeset operations over the ZBDDs.

Introduction

In this paper, we present an interesting variationof ZBDD-growth algorithm to generate frequent
closed item sets. Closed item sets are the subset ofitem set patterns each of which is the unique representative for a group of sub-patterns relevant tothe same set of transaction records. Our method isa quite simple modiﬁcation of ZBDD-growth. We
inserted several operations in the recursive procedure of ZBDD-growth, to ﬁlter the closed patterns
from all frequent patterns. The experimental re-

Frequent item set mining is one of the fundamental
techniques for knowledge discovery and data mining. Since the introduction by Agrawal et al.[1], thefrequent item set mining and association rule analysis have been received much attentions from many
researchers, and a number of papers have been published about the new algorithms or improvements
for solving such mining problems[4, 6, 11]. How1

2

Shin-ichi Minato

Figure 1: A Boolean function and a combinatorial
item set.

Figure 2: An example of ZBDD.

sult shows that the additional computation costis relatively small compared with the original algorithm for generating all patterns. Our method
can conveniently be utilized in the environment of
ZBDD-based data mining and knowledge indexing.

2

ZBDD-based item set representation
Figure 3: Example of tuple-histogram.

As the preliminary section, we describe the methods for eﬃciently indexing item set data based on
Zero-suppressed BDDs.

2.1

Combinatorial item set and ZBDDs

A combinatorial item set consists of the elements
each of which is a combination of a number of
items. There are 2n combinations chosen from nnitems, so we have 22 variations of combinatorial
item sets. For example, for a domain of ﬁve items
a, b, c, d, and e, we can show examples of combinatorial item sets as:{ab, e}, {abc, cde, bd, acde, e}, {1, cd}, 0. Here “1”denotes a combination of null items, and 0 means
an empty set. Combinatorial item sets are one of
the basic data structure for various problems incomputer science, including data mining.
A combinatorial item set can be mapped into
Boolean space of n input variables. For example, Fig. 1 shows a truth table of Boolean function: F = (a b c) ∨ (b c), but also represents
a combinatorial item set S = {ab, ac, c}. Using
BDDs for the corresponding Boolean functions, we

can implicitly represent and manipulate combinatorial item set. In addition, we can enjoy more eﬃcient manipulation using “Zero-suppressed BDDs”(ZBDD)[7], which are special type of BDDs optimized for handling combinatorial item sets. An
example of ZBDD is shown in Fig. 2.
The detailed techniques of ZBDD manipulation
are described in the articles[7]. A typical ZBDD
package supports cofactoring operations to traverse
0-edge or 1-edge, and binary operations between
two combinatorial item sets, such as union, intersection, and diﬀerence. The computation time foreach operation is almost linear to the number of
ZBDD nodes related to the operation.

2.2

Tuple-Histograms and ZBDD vectors

A Tuple-histogram is the table for counting thenumber of appearance of each tuple in the given
database. An example of tuple-histogram is shownin Fig. 3. This is just a compressed table of theGenerating Frequent Closed Item Sets Based on Zero-suppressed BDDs

3

carry up T to F1 . This ripple carry procedure continues until T and Fk have no common part. After ﬁnishing accumulations for all data records, thetuple-histogram is completed.
Using the notation F .add(T ) for addition of atuple T to the ZBDD vector F , we describe the procedure of generating tuple-histogram H for given
database D.
Figure 4: ZBDD vector for tuple-histogram.

database to combine the same tuples appearing
more than once into one line with the frequency.
Our item set mining algorithm manipulates
ZBDD-based tuple-histogram representation as theinternal data structure. Here we describe how torepresent tuple-histograms using ZBDDs. Since
ZBDDs are representation of sets of combinations,a simple ZBDD distinguishes only existence ofeach tuple in the database. In order to represent the numbers of tuple’s appearances, we decompose the number into m-digits of ZBDD vector {F0 , F1 , . . . , Fm−1 } to represent integers up to(2m −1), as shown in Fig. 4. Namely, we encode theappearance numbers into binary digital code, as F0
represents a set of tuples appearing odd times (LSB
= 1), F1 represents a set of tuples whose appearance number’s second lowest bit is 1, and similar
way we deﬁne the set of each digit up to Fm−1 .
In the example of Fig. 4, The tuple frequencies are decomposed as: F0 = {abc, ab, c}, F1 ={ab, bc}, F2 = {abc}, and then each digit can be
represented by a simple ZBDD. The three ZBDDs
are shared their sub-graphs each other.
Now we explain the procedure for constructing a ZBDD-based tuple-histogram from original
database. We read a tuple data one by one fromthe database, and accumulate the single tuple data
to the histogram. More concretely, we generate a
ZBDD of T for a single tuple picked up from thedatabase, and accumulate it to the ZBDD vector.
The ZBDD of T can be obtained by starting from“1” (a null-combination), and applying “Change”
operations several times to join the items in thetuple. Next, we compare T and F0 , and if they
have no common parts, we just add T to F0 . If
F0 already contains T , we eliminate T from F0 and

H=0forall T ∈ D do
H = H.add(T )return H
When we construct a ZBDD vector of tuplehistogram, the number of ZBDD nodes in each
digit is bounded by total appearance of items in
all tuples. If there are many partially similar tuples in the database, the sub-graphs of ZBDDs areshared very well, and compact representation is obtained. The bit-width of ZBDD vector is boundedby log Smax , where Smax is the appearance of mostfrequent items.
Once we have generated a ZBDD vector forthe tuple-histogram, various operations can be executed eﬃciently. Here are the instances of operations used in our pattern mining algorithm.
• H.factor0(v): Extracts sub-histogram of tuples without item v.
• H.factor1(v): Extracts sub-histogram of tuples including item v and then delete v fromthe tuple combinations. (also considered as
the quotient of H/v)
• v · H: Attaches an item v on each tuple combinations in the histogram F .
• H1 + H2 : Generates a new tuple-histogramwith sum of the frequencies of corresponding
tuples.
• H.tuplecount: The number of tuples appearing at least once.
These operations can be composed as a sequenceof ZBDD operations. The result is also compactly
represented by a ZBDD vector. The computation
time is bounded by roughly linear to total ZBDD
sizes.

4Shin-ichi Minato

ZBDDgrowth(H, α){if(H has only one item v)
if(v appears more than α )return v ;else return “0” ;F ← Cache(H) ;if(F exists) return F ;v ← H.top ; /* Top item in H */H1 ← H.factor1(v) ;H0 ← H.factor0(v) ;F1 ←ZBDDgrowth(H1 , α) ;F0 ←ZBDDgrowth(H0 + H1 , α) ;F ← (v · F1 ) ∪ F0 ;Cache(H) ← F ;return F ;}Figure 5: ZBDD-growth algorithm.

3

the pointer to the ZBDD vector for a given tuplehistogram, and F is the pointer to the result of
ZBDD. On each recursive call, we check the cache
to see whether the same histogram H has alreadyappeared, and if so, we can avoid duplicate processing and return the pointer to F directly. By using
this technique, the computation time becomes almost linear to the total ZBDD sizes.
In our implementation, we use some simple techniques to prune the search space. For example, if
H1 and H0 are equivalent, we may skip to compute F0 . For another case, we can stop the recursive calls if total frequencies in H is no more thanα. There are some other elaborate pruning techniques, but they needs additional computation costfor checking the conditions, so sometimes eﬀective
but not always.

ZBDD-growth Algorithm
4

Recently,
wedevelopeda
ZBDD-basedalgorithm[8], ZBDD-growth, to generate “all”
frequent item set patterns. Here we describe thisalgorithm as the basis of our method for “closed”
item set mining.
ZBDD-growth is based on a recursive depth-ﬁrst
search over the ZBDD-based tuple-histogram representation. The basic algorithm is shown in Fig. 5.
In this algorithm, we choose an item v used in
the tuple-histogram H, and compute the two subhistograms H1 and H0 . (Namely, H = (v · H1 ) ∪H0 .) As v is the top item in the ZBDD vector,
H1 and H0 can be obtained just by referring the1-edge and 0-edge of the highest ZBDD-node, so
the computation time is constant for each digit of
ZBDD.
The algorithm consists of the two recursive calls,
one of which computes the subset of patterns including v, and the other computes the patterns
excluding v. The two subsets of patterns can beobtained as a pair of pointers to ZBDDs, and thenthe ﬁnal result of ZBDD is computed. This procedure may require an exponential number of recursive calls, however, we prepare a hash-based cacheto store the result of each recursive call. Each entry
in the cache is formed as pair (H, F ), where H is

Frequent closed item set mining

In frequent item set mining, we sometimes facedwith the problem that a huge number of frequent
patterns are extracted and hard to ﬁnd useful information. Closed item set mining is one of thetechniques to ﬁlter important subset of patterns.
In this section, we present a variation of ZBDDgrowth algorithm to generate frequent closed item
sets.

4.1

Closed item sets

Closed item sets are the subset of item set patterns each of which is the unique representative fora group of sub-patterns relevant to the same setof tuples. For more clear deﬁnition, we ﬁrst deﬁne the common item set Com(ST ) for the given
set of tuples ST , such that Com(ST ) is the set ofitems commonly included in every tuple T ∈ ST .
Next, we deﬁne occurence Occ(D, X) for the given
database D and item set X, such that Occ(D, X)
is the subset of tuples in D, each of which includes
X. Using these notations, if an item set X satisﬁes
Com(Occ(D, X)) = X, we call X is a closed item
set in D.

Generating Frequent Closed Item Sets Based on Zero-suppressed BDDs

For example, let us consider the database D
as shown in Fig. 3. Here, all item set patterns
with threshold α = 1 is: {abc, ab, ac, a, bc, b, c}, butclosed item sets are: {abc, ab, bc, b, c}. In this example, “ac” is eliminated from a closed pattern because Occ(D,“ac”) = Occ(D,“abc”).
In recent years, many researchers discuss the efﬁcient algorithms for closed item set mining. Oneof the remarkable result is LCM algorithm[10] presented by Uno et. al. LCM is a depth-ﬁrst searchalgorithm to extract closed item sets. It featuresthat the computation time is bounded by linear tothe output data length. Our ZBDD-based algorithm is also based on a depth-ﬁrst search manner,so, it has similar properties as LCM. The majordiﬀerence is in the data structure of output data.
Our method generates ZBDDs for the set of closed
patterns, ready to go for more ﬂexible analysis using ZBDD operations.

4.2

Eliminating non-closed patterns

Our method is a quite simple modiﬁcation of
ZBDD-growth shown in Fig. 5. We inserted several
operations in the recursive procedure of ZBDDgrowth, to ﬁlter the closed patterns from all frequent patterns. The ZBDD-growth algorithm isstaring from the given tuple-histogram H, andcompute the two sub-histograms H1 and H0 , suchthat H = (v · H1 ) ∪ H0 . Then ZBDD-growth(H1 )and ZBDD-growth(H1 + H0 ) is recursively executed.
Here, we consider the way to eliminate nonclosed patterns in this algorithm. We call the
new algorithm ZBDD-growthC(H). It is obviousthat (v· ZBDD-growthC(H1 ) ) generates (a partof) closed patterns for H each of which includes v,
because the occurrence of any closed pattern withv is limited in (v · H1 ), thus we may search onlyfor H1 . Next, we consider the second recursive call
ZBDD-growthC(H1 + H0 ) to generate the closed
patterns without v. Important point is that someof patterns generated by ZBDD-growthC(H1 + H0 )may have the same occurrence as one of the pattern with v already found in H1 . The conditionof such duplicate pattern is that it appears only in

5

P .permit(Q){
if(P =“0” or Q =“0”) return “0” ;if(P = Q) return F ;if(P =“1”) return “1” ;if(Q =“1”)if(P include “1” ) return “1” ;else return “0” ;R ← Cache(P, Q) ;if(R exists) return R ;v ←TopItem(P, Q) ; /* Top item in P, Q */(P0 , P1 ) ←factors of P by v ;(Q0 , Q1 ) ←factors of Q by v ;R ← (v · P1 .permit(Q1 ))∪ (P0 .permit(Q0 ∪ Q1 )) ;Cache(P, Q) ← R ;return R ;}Figure 6: Permit operation.

H1 but irrelevant to H0 . In other words, we eliminate the patterns from ZBDD-growthC(H1 + H0 )such that the patterns are already found in ZBDDgrowthC(H1 ) but not included in any tuples in H0 .
For checking the condition for closed patterns,
we can use a ZBDD-based operation, called permit operation by Okuno et al.[9].1 P .permit(Q)returns a set of combinations in P each of which isa subset of some combinations in Q. For example,
when P = {ab, abc, bcd} and Q = {abc, bc}, thenP .permit(Q) returns {ab, abc}. The permit operation is eﬃciently implemented as a recursive procedure of ZBDD manipulation, as shown in Fig. 6.
The computation time of permit operation is almost linear to the ZBDD size.
Finally, we describe the ZBDD-growthC algorithm using the permit operation, as shown in
Fig. 7. The diﬀerence from the original algorithm
is only one line, written in the frame box.

5

Experimental Results

Here we show the experimental results to evaluate our new method. We used a Pentium-4 PC,
1

Permit operation is basically same as SubSet operation
by Coudert et al.[3], defined for ordinary BDDs.

6

Shin-ichi Minato

Table 1: Generation of tuple-histograms[8].

Data name#T
total|T |T10I4D100K
100,000 1,010,228
T40I10D100K 100,000 3,960,507
chess
3,196
118,252
connect
67,557 2,904,951
mushroom
8,124
186,852
pumsb
49,046 3,629,404
pumsb star
49,046 2,475,947
BMS-POS
515,597 3,367,020
BMS-WebView-1 59,602
149,639
BMS-WebView-2 77,512
358,278
accidents
340,183 11,500,870|ZBDD Vector| Time(s)552,42943.2
3,396,395
150.2
40,0281.4
309,075
58.1
8,006
1.2
1,750,883
188.5
1,324,502
123.6
1,350,970
895.0
46,14818.3
198,471138.0
3,877,333
107.0

Table 2: Result of the original ZBDD-growth[8].
Data name:#Frequent (output) Time(sec)Min. freq. αpatterns |ZBDD|
mushroom: 5,000
41
11
1.2
1,000
123,277
1,417
3.7
200
18,094,821
12,3409.7
50
198,169,865
36,65210.2
16
1,176,182,553
53,8047.7
43,786,792,695
59,9704.3
15,574,930,437
40,557
1.8
T10I4D100K: 5,000
10
10
81.3
1,000
385
382
135.5
200
13,255
4,288
279.4
50
53,38520,364408.7
16
175,915
89,423543.3
43,159,067 1,108,723
646.0
BMS-WebView1: 1,000
31
31
27.8
200
372
309
31.3
50
8,191
3,753
49.0
40
48,543
12,17646.6
36461,52134,790102.4
351,177,607
47,457111.4
344,849,465
64,601120.8
3369,417,073
80,604130.0
321,531,980,297
97,692133.7
31 8,796,564,756,112 117,101
138.1
30 35,349,566,550,691 152,431
143.9

800MHz, 1.5GB of main memory, with SuSE Linux9. We can deal with up to 40,000,000 nodes of ZBDDs in this machine.
Table 1 shows the time and space for generating ZBDD vectors of tuple-histograms for the
FIMI2003 benchmark databases[5]. This tableshows the computation time and space for providing input data for ZBDD-growth algorithm. In thistable, #T shows the number of tuples, total|T |is the total of tuple sizes (total appearances of
items), and |ZBDD| is the number of ZBDD nodes
for the tuple-histograms. We can see that tuplehistograms can be constructed for all instances ina feasible time and space. The ZBDD sizes arealmost same or less than total|T |.
After generating ZBDD vectors for the tuple-

histograms, we applied ZBDD-growth algorithm
to generate frequent patterns. Table 2 show theresults of the original ZBDD-growth algorithm[8]for the selected benchmark examples, “mushroom,”“T10I4D100K,” and “BMS-WebView-1.” The execution time includes the time for generating theinitial ZBDD vectors for tuple-histograms.
The results shows that the ZBDD size is exponentially smaller than the number of patterns
for “mushroom.” This is a signiﬁcant eﬀect of using the ZBDD data structure. On the other hand,no remarkable reduction is seen in ”T10I4D100K.””T10I4D100K” is known as an artiﬁcial database,consists of randomly generated combinations, so
there are almost no relationship between the tuples.
In such cases, ZBDD nodes cannot be shared well,Generating Frequent Closed Item Sets Based on Zero-suppressed BDDsZBDDgrowthC(H, α){if(H has only one item v)
if(v appears more than α )return v ;else return “0” ;F ← Cache(H) ;if(F exists) return F ;v ← H.top ; /* Top item in H */H1 ← H.factor1(v) ;H0 ← H.factor0(v) ;F1 ←ZBDDgrowthC(H1 , α) ;F0 ←ZBDDgrowthC(H0 + H1 , α) ;F ← (v · F1 ) ∪(F0 − (F1 − F1 .permit(H0 ))) ;Cache(H) ← F ;return F ;}Figure 7: ZBDD-growthC algorithm.

6

7Conclusion

In this paper, we presented an interesting variation of ZBDD-growth algorithm to generate frequent closed item sets. Our method is a quite
simple modiﬁcation of ZBDD-growth. We inserted
several operations in the recursive procedure of
ZBDD-growth, to ﬁlter the closed patterns from all
frequent patterns. The experimental result showsthat the additional computation cost is relatively
small compared with the original algorithm for generating all patterns.
A ZBDD can be regarded as a compressed trie
for representing a set of patterns. ZBDD-based
method will be useful as a fundamental techniquefor database analysis and knowledge indexing, andwill be utilized for various data mining applications.

References
and only the overhead factor is revealed. For thethird example, “BMS-WebView-1,” the ZBDD sizeis almost linear to the number of patterns when the
output size is small, however, an exponential factorof reduction is observed for the cases of generating
huge patterns.

Next, we show the experimental results of frequent closed pattern mining using ZBDD-growthC
algorithm. In Table 3, we show the results forthe same examples as used in the experimentof the original ZBDD-growth. The last column
T ime(closed) /T ime(all) shows the ratio of computation time between the ZBDD-growthC and theoriginal ZBDD-growth algorithm. We can observethat the computation time is almost the sameorder as the original algorithms for “mushroom”
and “BMS-WebView-1,” but some additional factor is observed for “T10I4D100K.” Anyway, ﬁltering closed item sets has been regarded as not aeasy task. We can say that the ZBDD-growthC
algorithm can generate closed item sets with arelatively small additional cost from the original
ZBDD-growth.

[1] R. Agrawal, T. Imielinski, and A. N. Swami,
Mining Association rules between sets of items
in large databases, In P. Buneman and S. Jajodia, edtors, Proc. of the 1993 ACM SIGMODInternational Conference on Management of
Data, Vol. 22(2) of SIGMOD Record, pp. 207–
216, ACM Press, 1993.
[2] Bryant, R. E., Graph-based algorithms for
Boolean function manipulation, IEEE Trans.
Comput., C-35, 8 (1986), 677–691.
[3] O. Coudert, J. C. Madre, H. Fraisse, A new
viewpoint on two-level logic minimization, in
Proc. of 30th ACM/IEEE Design Automation
Conference, pp. 625-630, 1993.
[4] B.
Goethals,“SurveyonFrequent
Pattern
Mining”,
Manuscript,
2003.
http://www.cs.helsinki.fi/
u/goethals/publications/survey.ps[5] B. Goethals, M. Javeed Zaki (Eds.), Frequent
Itemset Mining Dataset Repository, Frequent
Itemset Mining Implementations (FIMI’03),
2003.
http://fimi.cs.helsinki.fi/data/

8Shin-ichi Minato

Table 3: Results of ZBDD-based closed pattern mining.
Data name:Min. freq. α#Freq. (output) ZBDD- T ime(closed)
closed |ZBDD| growthC /T ime(all)patterns
Time(s)mushroom:
5,000
16
1,000
3,427
200
26,96850
68,46816 124,411
4 203,882
1 238,709
T10I4D100K:
5,000
10
1,000
385
200
13,10850
46,99316 142,520
4 1,023,614
BMS-WebView-1:
1,000
31
200
372
50
7,811
40
29,48936
64,762
35
76,26034
87,982
33
99,69632 110,800
31 120,190
30 127,131

16
1,660
9,826
19,054
24,841
26,325
20,392

1.2
3.8
9.9
13.0
13.3
13.2
12.9

1.00
1.02
1.02
1.27
1.73
3.06
7.19

10
382
4,312
20,581
89,185691,154

104.8
208.1
2713.64600.15798.518573.0

1.29
1.54
9.71
11.25
10.67
28.75

31
309
3,796
11,74825,11730,01135,39240,91546,42451,36955,407

30.1
36.8
71.9
111.4
153.7
169.2
186.5
207.7
221.7
247.7
271.5

1.08
1.18
1.47
2.39
1.50
1.52
1.54
1.60
1.66
1.79
1.89

[6] J. Han, J. Pei, Y. Yin, R. Mao, Mining
Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,
Data Mining and Knowledge Discovery, 8(1),53–87, 2004.

ing Frequent Closed Item Sets,” Proc. Workshop on Frequent Itemset Mining Implementations (FIMI’03), Mohammed J. Zaki and Bart
Goethals (eds.), 2003.
http://fimi.cs.helsinki.fi/fimi03/[7] S. Minato: Zero-suppressed BDDs for set manipulation in combinatorial problems, In Proc.
30th ACM/IEEE Design Automation Conf.
(DAC-93), (1993), 272–277.

[11] M. J. Zaki, Scalable Algorithms for Association Mining, IEEE Trans. Knowl. Data Eng.
12(2), 372–390, 2000.

[8] S. Minato, H. Arimura:
ZBDD-growth:
An Eﬃcient Method for Frequent Pattern
Mining and Knowledge Indexing, Hokkaido
University, Division of Computer Science,
TCS Technical Reports, TCS-TR-A-06-12,
Apr. 2006.
http://www-alg.ist.hokudai.ac.jp/
tra.html[9] H. Okuno, S. Minato, and H. Isozaki: On
the Properties of Combination Set Operations,
Information Procssing Letters, Elsevier, 66(1998), pp. 195-199, 1998.
[10] T. Uno, Y. Uchida, T. Asai, and H. Arimura:“LCM: An Eﬃcient Algorithm for Enumerat-