    001    /* Copyright 2000, 2001, Compaq Computer Corporation */
    002
    003    package escjava.pa.generic;
    004
    005    import javafe.util.*;
    006
    007    /* Enumerates all clauses of size k, where there are n variables.
    008     */
    009
    010    class EnumKofN extends Disjunction {
    011
    012        int n,k;
    013
    014        public  EnumKofN(int k, int n) {
    015            super(-1L, 0);
    016            Assert.notFalse( k <= n );
    017            this.k = k;
    018            this.n = n;
    019        }
    020
    021        boolean getNext() {
    022
    023            if( stars == -1 ) {
    024                // intitialize
    025                stars = 0;
    026                for(int i=k; i<n; i++) {
    027                    stars |= 1<<i;
    028                }
    029                return true;
    030            }
    031
    032            // get next
    033
    034            int nb=0, ns=0, i=0;
    035
    036            for(i=0; i<n; i++) {
    037                Assert.notFalse( nb + ns == i );
    038
    039                long b = 1<<i;
    040                if( (stars & b) != 0 ) {
    041                    // was a star
    042                    ns++;
    043                    if (nb>0) {
    044                        // remove star
    045                        stars &= ~b;
    046                        // clear bit
    047                        bits &= ~b;
    048                        nb--;
    049                        break; // 0.enum(nb-1,s)
    050                    } else {
    051                        continue; // ret, done 0, nb=0
    052                    }
    053                } else {
    054                    // was a bit
    055                    if( (bits & b) == 0 ) {
    056                        // was a 0, set to 1
    057                        bits |= b;
    058                        break; // 1.enum(nb-1,s)
    059                    } else {
    060                        nb++;
    061                        // remove bit
    062                        bits &= ~b;
    063                        // put star in
    064                        stars |= b;
    065                        continue; // ret, done bits
    066                    }
    067                }
    068            }
    069            if( i==n ) return false;
    070
    071            // fill from i-1 to 0
    072            while( ns > 0 ) {
    073                ns --;
    074                i--;
    075                long b = 1<<i;
    076                Assert.notFalse( (stars & b) != 0 );
    077            }
    078            Assert.notFalse( i == nb );
    079
    080            while( i > 0 ) {
    081                i--;
    082                long b = 1<<i;
    083                stars &= ~b;
    084                Assert.notFalse( (stars & b) == 0 );
    085                Assert.notFalse( (bits & b) == 0 );
    086            }
    087
    088            return true;
    089        }
    090
    091        public static void main(String argv[]) {
    092
    093            EnumKofN e = new EnumKofN(2,3);
    094
    095            while( e.getNext() ) {
    096                System.out.println("Bits = "+Long.toString(e.bits,2)+
    097                                   " stars = "+Long.toString(e.stars,2));
    098            }
    099        }
    100
    101    }
    102
    103