1
2 #include "comb/young-tab-rgs.h"
3 // demo-include "comb/print-young-tab-rgs-aa.cc"
4 // demo-include "comb/is-shifted-young-tab-rgs.h"
5
6 #include "fxtio.h"
7 #include "fxttypes.h"
8 #include "jjassert.h"
9
10 #include "nextarg.h"
11
12
13 //% Restricted growth strings (RGS) for standard Young tableaux:
14 //% the k-th occurrence of a digit d in the RGS must precede
15 //% the k-th occurrence of the digit d+1.
16 //% Lexicographic order.
17 //% The strings are also called ballot sequences.
18 //% Cf. OEIS sequences A000085 (all tableaux),
19 //% A001405 (tableaux with height <= 2, central binomial coefficients)
20 //% A001006 (tableaux with height <= 3, Motzkin numbers)
21 //% A005817 (height <= 4), A049401 (height <= 5), A007579 (height <= 6)
22 //% A007578 (height <= 7), A007580 (height <= 8), A212915 (height <= 9),
23 //% A212916 (height <= 10).
24 //% A001189 (height <= n-1),
25 //% A014495 (height = 2), A217323 (height = 3), A217324 (height = 4),
26 //% A217325 (height = 5), A217326 (height = 6), A217327 (height = 7),
27 //% A217328 (height = 8).
28 //% Cf. A182172 (tableaux of n cells and height <= k).
29 //% Cf. OEIS sequences A061343 (all shifted tableaux; using condition is_shifted(1)),
30 //% A210736 (shifted, height <= 2), A082395 (shifted, height <= 3).
31 //% Cf. OEIS sequences A161125 (descent numbers), A225617 (strict inversions),
32 //% and A225618 (weak inversions).
33
34
35 // Cf. comb/young-tab-rgs-subset-lex-demo.cc for subset-lex order
36
37 //#define TIMING // uncomment to disable printing
38
39
40 int
main(int argc,char ** argv)41 main(int argc, char **argv)
42 {
43 ulong n = 6;
44 NXARG(n, "Length of strings");
45 ulong m = 0;
46 NXARG(m, "Number of allowed values for digits\n"
47 " == max height of tableaux, 0 ==> all");
48 if ( m>n ) m = n;
49 if ( m==0 ) m = n;
50
51 young_tab_rgs Y(n, m);
52
53 ulong ct = 0;
54
55
56 #ifdef TIMING
57
58 Y.first();
59 do { ++ct; } while ( Y.next() );
60
61 #else // TIMING
62
63 bool tq = 0;
64 NXARG(tq, "Whether do draw tableaux (as ASCII art)");
65
66 ulong j = 0;
67 do
68 {
69 #if 0 // impose certain conditions
70 // if ( Y.height() != 4 ) continue;
71 // if ( ! Y.is_falling(1) ) continue; // A218293
72 // if ( ! Y.is_falling(2) ) continue; // A225121
73 // if ( ! Y.is_falling(3) ) continue; // A000000
74 // if ( ! Y.is_delayed(1) ) continue; // A000000
75
76 if ( ! Y.is_shifted(1) ) continue; // A061343
77 // if ( ! Y.is_shifted(2) ) continue; // A000000
78 // 1, 1, 1, 1, 3, 4, 10, 15, 35, 98, 226, 606, 1760, 4523, ...
79
80 // const ulong st[] = { 4, 2, 1 };
81 // ulong hh = sizeof(st)/sizeof(st[0]);
82 //// cout << " :: hh=" << hh << endl;
83 // if ( ! Y.has_shape(st, hh) ) continue;
84
85 #endif
86 #if 0 // strict tableaux: A061343 (same as Y.is_shifted(1) )
87 // cf. A003121: ./bin 10 . 1 | g -F ' [ 4 3 2 1 '
88 if ( ! Y.is_strict() ) continue;
89 #endif
90 #if 0 // no succession v, v+1 in a row: A237770
91 { const ulong *x = Y.data();
92 bool q = true;
93 for (ulong k=1; k<n; ++k)
94 if ( x[k] == x[k-1] ) { q=0; break; }
95 if ( !q ) continue;
96 }
97 #endif
98 #if 0 // chess tableaux: A238014
99 if ( ! Y.is_chess_tableau() ) continue;
100 #endif
101
102 ++ct;
103
104 #if 1 // whether to print anything
105 cout << setw(4) << ct << ": ";
106
107 Y.print(" "); // RGS, starting with cell 0
108 // Y.print1(" "); // RGS, starting with cell 1
109 cout << setw(3) << j << " "; // leftmost change
110
111 Y.print_stats(" "); // stats: partition of n
112 cout << setw(3) << Y.height(); // height
113
114 #if 0 // list positions of first occurrence of digits:
115 ulong h = Y.height();
116 cout << " [ ";
117 for (ulong d=0; d<h; ++d)
118 {
119 ulong p = 0;
120 while ( Y.a_[p] != d ) ++p;
121 cout << p << " ";
122 }
123 cout << "]";
124 #endif
125
126 if ( tq )
127 {
128 cout << endl;
129 Y.print_aa( 1 ); // arg is offset (0 or 1)
130 cout << endl;
131 }
132
133
134 cout << endl;
135
136 jjassert( Y.OK() );
137 #endif
138 }
139 while ( (j=Y.next()) );
140
141
142 #endif // TIMING
143
144 cout << " ct=" << ct;
145 cout << endl;
146
147 return 0;
148 }
149 // -------------------------
150
151 /*
152 Timing: (AMD Phenom II X4 945 3000MHz)
153
154 time ./bin 18
155 arg 1: 18 == n [Length of strings] default=5
156 arg 2: 0 == m [Number of allowed values for digits
157 == max height of tableaux, 0 ==> all] default=0
158 ct=997313824
159 ./bin 18 10.14s user 0.00s system 99% cpu 10.147 total
160 ==> 997313824/10.14 == 98,354,420 per second
161
162
163 time ./bin 19 5
164 arg 1: 19 == n [Length of strings] default=5
165 arg 2: 5 == m [Number of allowed values for digits
166 == max height of tableaux, 0 ==> all] default=0
167 ct=1212962072
168 ./bin 19 5 11.00s user 0.00s system 99% cpu 11.000 total
169 ==> 1212962072/11.00 == 110,269,279 per second
170
171
172 time ./bin 32 2
173 arg 1: 32 == n [Length of strings] default=5
174 arg 2: 2 == m [Number of allowed values for digits
175 == max height of tableaux, 0 ==> all] default=0
176 ct=601080390
177 ./bin 32 2 6.16s user 0.00s system 99% cpu 6.159 total
178 ==> 601080390/6.16 == 97,577,985 per second
179
180
181 GCC 4.8.0:
182
183 time ./bin 18
184 arg 1: 18 == n [Length of strings] default=6
185 arg 2: 0 == m [Number of allowed values for digits
186 == max height of tableaux, 0 ==> all] default=0
187 ct=997313824
188 ./bin 18 10.70s user 0.00s system 99% cpu 10.701 total
189 ==> 997313824/10.70 == 93,206,899 per second
190
191 */
192
193 /*
194 BENCHARGS=18
195 BENCHARGS=19 5
196 BENCHARGS=32 2
197 */
198
199 /// Emacs:
200 /// Local Variables:
201 /// MyRelDir: "demo/comb"
202 /// makefile-dir: "../../"
203 /// make-target: "1demo DSRC=demo/comb/young-tab-rgs-demo.cc"
204 /// make-target2: "1demo DSRC=demo/comb/young-tab-rgs-demo.cc DEMOFLAGS=-DTIMING"
205 /// End:
206
207