1
2 #include "comb/tree-lev-seq.h"
3 #include "comb/tree-lev-seq-aux.h"
4
5 #include "fxtio.h"
6
7 #include "fxttypes.h"
8 #include "nextarg.h" // NXARG()
9 #include "jjassert.h"
10
11 //% Level sequences for unordered rooted trees.
12 //% Cf. OEIS sequence A000081.
13
14 // Cf. comb/id-tree-lev-seq-demo.cc for identity trees
15 // Cf. comb/ordered-tree-lev-seq-demo.cc for ordered trees
16 // Cf. comb/balanced-ordered-tree-lev-seq-demo.cc for blanced trees
17 // Cf. comb/ordered-tree-branching-seq-demo.cc branching sequences for ordered trees
18
19
20 //#define TIMING // uncomment to disable printing
21
22 int
main(int argc,char ** argv)23 main(int argc, char **argv)
24 {
25 ulong n = 6;
26 NXARG(n,"Number of non-root nodes");
27
28 bool aa = false;
29 NXARG(aa,"Whether to render trees as ASCII art");
30
31 tree_lev_seq T(n);
32 #ifdef TIMING
33 #endif
34
35 ulong ct = 0;
36 do
37 {
38 #if 0
39 { bool q = true; const ulong N = T.size();
40 #define NXT { q=false; break; } if ( ! q ) continue;
41
42 // series-reduced trees:
43 // for (ulong k=1; k+1 < N; ++k) if ( T.valency(k)==2 ) NXT; // A198518
44 // for (ulong k=0; k+1 < N; ++k) if ( T.valency(k)==2 ) NXT; // A001679
45
46 // for (ulong k=0; k+1 < N; ++k) // cf. A000598 (rooted ternary trees)
47 // {
48 // ulong v = T.valency(k);
49 // if ( k==0 && v!=1 ) NXT;
50 // if ( v==2 ) NXT;
51 // if ( v==3 ) NXT;
52 // if ( v>=5 ) NXT;
53 // } /**/ if ( ! q ) continue;
54
55 // for (ulong k=1; k+1 < N; ++k) if ( T.lev(k) == T.lev(k+1) ) NXT; // A002955
56 // cf. A255636
57
58 // for (ulong k=1; k+1 < N; ++k) if ( T.lev(k) == T.lev(k+1) + 1 ) NXT; // A000000
59
60 // no non-root branchings:
61 // for (ulong k=1; k < N; ++k) if ( T.branching_number(k) > 1 ) NXT; // A000041
62
63 // for (ulong k=1; k+1 < N; ++k) if ( T.branching_number(k)==1 ) NXT; // A198518
64
65 // for (ulong k=0; k+1 < N; ++k) if ( T.branching_number(k)==1 ) NXT; // A001678
66
67 // rooted forests without 1-trees:
68 // for (ulong k=0; k < N; ++k) if ( T.lev(k)==1 && T.lev(k+1)!=2 ) NXT; // A174145
69
70 // level sequence drops by at most 1:
71 // for (ulong k=0; k+1 < N; ++k) if ( T.lev(k) > T.lev(k+1)+1 ) NXT; // A000000
72
73 // no odd out-degrees:
74 // for (ulong k=1; k+1 < N; ++k) if ( (T.branching_number(k)&1)==1 ) NXT; // A195865
75 // for (ulong k=0; k+1 < N; ++k) if ( (T.branching_number(k)&1)==1 ) NXT; // A000000
76
77 // no even out-degrees for internal nodes:
78 // for (ulong k=1; k+1 < N; ++k)
79 // { ulong b = T.branching_number(k); if ( (b!=0) && (b&1)==0 ) NXT; } // A000000
80 // for (ulong k=0; k+1 < N; ++k)
81 // { ulong b = T.branching_number(k); if ( (b!=0) && (b&1)==0 ) NXT; } // A000000
82
83
84 for (ulong k=0; k+1 < N; ++k) if ( T.branching_number(k) > 2 ) NXT; // A001190
85 // for (ulong k=0; k+1 < N; ++k) if ( T.branching_number(k) > 3 ) NXT; // A000598
86 // for (ulong k=0; k+1 < N; ++k) if ( T.branching_number(k) > 4 ) NXT; // A036718
87 // for (ulong k=0; k+1 < N; ++k) if ( T.branching_number(k) > 5 ) NXT; // A036721
88 }
89 #endif
90 #if 0
91 // only odd/even branching number at root:
92 // if ( (T.branching_number(0) & 1) == 0 ) continue; // A000000
93 // if ( (T.branching_number(0) & 1) == 1 ) continue; // A000000
94
95 // if ( ! T.is_identity_tree() ) continue; // A004111
96 if ( ! T.is_balanced() ) continue; // A048816
97
98 // if ( T.max_limb_length() >= 2 ) continue; // A002955
99 // if ( T.max_limb_length() > 2 ) continue; // A052321, cf. A003006
100 // if ( T.max_limb_length() > 3 ) continue; // A052327
101 // if ( T.max_limb_length() > 4 ) continue; // A052328
102 // if ( T.max_limb_length() > 5 ) continue; // A052329
103
104 // if ( T.min_limb_length() <= 1 ) continue; // A001678(!)
105 // if ( T.min_limb_length() <= 2 ) continue; // A000000
106
107 // if ( T.min_limb_length() != 1 ) continue; // A244455(!)
108 // if ( T.min_limb_length() != 2 ) continue; // A000000 (not: A155099)
109 #endif
110
111 ++ct;
112
113 #ifndef TIMING
114
115 cout << setw(4) << ct << ":";
116 T.print(" ");
117
118 // cout << " Bq =[ "; for (ulong i=0; i<n; ++i) cout << T.is_branch(i) << " "; cout << "]";
119 // cout << " Lq =[ "; for (ulong i=0; i<n; ++i) cout << T.is_leaf(i) << " "; cout << "]";
120 // cout << " LL =[ "; for (ulong i=0; i<n; ++i) cout << T.limb_length(i) << " "; cout << "]";
121 // cout << setw(4) << T.min_limb_length();
122 // cout << setw(4) << T.max_limb_length();
123 // cout << setw(4) << T.height();
124
125 // T.print_branching_numbers(" "); // out-degrees (dots for zeros)
126 // T.print_base_seq(" ");
127
128 // T.print_paren_word(" ", "()");
129 // T.print_paren_word(" ", "1.");
130
131 // T.print_composition(" "); // for balanced trees only
132
133 if ( aa )
134 {
135 cout << endl;
136 T.print_aa("");
137 cout << endl;
138 }
139
140 cout << endl;
141 jjassert( T.OK() );
142 #endif
143 }
144 while ( 0 != T.next() );
145
146 cout << " ct=" << ct << endl;
147
148 return 0;
149 }
150 // -------------------------
151
152 /*
153 Timing: (Intel Xeon CPU E3-1275 V2 @ 3.50GHz)
154
155 GCC 4.9.2:
156
157 time ./bin 23
158 arg 1: 23 == n [Number of non-root nodes] default=6
159 arg 2: 0 == aa [Whether to render trees as ASCII art] default=0
160 ct=743724984
161 ./bin 23 2.84s user 0.00s system 99% cpu 2.839 total
162 ==> 743724984/2.84 == 261,874,994 per second
163
164 */
165
166 /*
167
168 Timing: (AMD Phenom II X4 945 3000MHz)
169
170 GCC 4.9.1:
171
172 // with easy case optimization:
173
174 time ./bin 23
175 arg 1: 23 == n [Number of non-root nodes] default=6
176 arg 2: 0 == aa [Whether to render trees as ASCII art] default=0
177 ct=743724984
178 ./bin 23 5.38s user 0.00s system 99% cpu 5.386 total
179 ==> 743724984/5.38 == 138,238,844 per second
180
181
182 // without easy case optimization:
183
184 time ./bin 23
185 arg 1: 23 == n [Number of non-root nodes] default=6
186 arg 2: 0 == aa [Whether to render trees as ASCII art] default=0
187 ct=743724984
188 ./bin 23 10.65s user 0.00s system 99% cpu 10.656 total
189 ==> 743724984/10.65 == 69,833,331 per second
190
191 */
192
193
194 /// Emacs:
195 /// Local Variables:
196 /// MyRelDir: "demo/comb"
197 /// makefile-dir: "../../"
198 /// make-target: "1demo DSRC=demo/comb/tree-lev-seq-demo.cc"
199 /// make-target2: "1demo DSRC=demo/comb/tree-lev-seq-demo.cc DEMOFLAGS=-DTIMING"
200 /// End:
201