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