1
2 // demo-is-self-contained
3
4 #include "fxttypes.h"
5 #include "fxtio.h"
6 #include "jjassert.h"
7 #include "nextarg.h"
8
9
10 //% Gray code for binary words with no substring 1x1, recursive CAT algorithm
11
12 //#define TIMING // define to disable printing
13
14
15 ulong n; // number of bits in words
16 ulong *rv; // bits of the word
17 ulong *rvo; // bits of previous word
18
19 ulong ct; // count objects
20
21 ulong xct; // count transitions
22
visit()23 void visit()
24 {
25 if ( ct>1 )
26 {
27 xct = 0;
28 for (ulong j=0; j<n; ++j) xct += (rvo[j] != rv[j]);
29 --xct;
30 }
31 for (ulong j=0; j<n; ++j) rvo[j] = rv[j];
32
33 #ifndef TIMING
34 cout << setw(4) << ct << ":";
35 cout << " ";
36 for (ulong j=0; j<n; ++j) cout << " " << (rv[j] ? '1' : '.');
37 // cout << setw(3) << xct;
38 cout << endl;
39 #endif
40
41 jjassert( 0==xct );
42 }
43 // -------------------------
44
45
46 void
no1x1_rec(ulong d,bool z)47 no1x1_rec(ulong d, bool z)
48 {
49 if ( d>=n )
50 {
51 if ( d<=n+2 )
52 {
53 ++ct; // count objects
54 visit();
55 }
56 }
57 else
58 {
59 if ( z )
60 {
61 rv[d]=1; rv[d+1]=0; rv[d+2]=0; no1x1_rec(d+3, z);
62 rv[d]=1; rv[d+1]=1; rv[d+2]=0; rv[d+3]=0; no1x1_rec(d+4, !z);
63 rv[d]=0; no1x1_rec(d+1, z);
64 }
65 else
66 {
67 rv[d]=0; no1x1_rec(d+1, z);
68 rv[d]=1; rv[d+1]=1; rv[d+2]=0; rv[d+3]=0; no1x1_rec(d+4, !z);
69 rv[d]=1; rv[d+1]=0; rv[d+2]=0; no1x1_rec(d+3, z);
70 }
71 }
72 }
73 // -------------------------
74
75
76 int
main(int argc,char ** argv)77 main(int argc, char **argv)
78 {
79 n = 7;
80 NXARG(n, "Length of words");
81 rv = new ulong[n+3];
82 rvo = new ulong[n+3];
83 bool rq = 0;
84 // NXARG(rq, "Whether to reverse order");
85
86
87 xct = 0;
88 ct = 0;
89 no1x1_rec(0, rq);
90
91 cout << "ct=" << ct << endl;
92
93 delete [] rv;
94 delete [] rvo;
95
96 return 0;
97 }
98 // -------------------------
99
100 /*
101 // 1 2 3 4 5 6 7 8 9 10
102 // 2 4 6 9 15 25 40 64 104 169 273 441 714 1156 1870 3025 4895
103 // OEIS sequence A006498 ,1,1,1,2,4,6,9,15,25,40,64,104,169,273,441
104 // A006498 a(n) = a(n-1)+a(n-3)+a(n-4).
105 // == A074677 a(n)=Sum((-1)^(i+Floor(n/2))F(2i+e),(i=0,..,Floor(n/2))), where F(n) = Fib(n)
106
107 no1x1 and no1xy1:
108 % echo $(for n in $(seq 0 17); do ./bin $n | grep -vE '1 .? .? 1' | grep ': ' | wc -l; done)
109 1 2 4 6 8 11 17 27 41 60 88 132 200 301 449 669 1001 1502
110 == A079972
111 */
112
113 /*
114 Timing:
115
116 */
117
118 /// Emacs:
119 /// Local Variables:
120 /// MyRelDir: "demo/comb"
121 /// makefile-dir: "../../"
122 /// make-target: "1demo DSRC=demo/comb/no1x1-gray-demo.cc"
123 /// make-target2: "1demo DSRC=demo/comb/no1x1-gray-demo.cc DEMOFLAGS=-DTIMING"
124 /// End:
125
126