1
2 #include "comb/young-tab-rgs-subset-lex.h"
3 // demo-include "comb/print-young-tab-rgs-aa.cc"
4
5 //#include "comb/comb-print.h"
6
7
8 #include "fxtio.h"
9 #include "fxttypes.h"
10 #include "jjassert.h"
11
12 #include "nextarg.h"
13
14
15 //% Restricted growth strings (RGS) for standard Young tableaux:
16 //% the k-th occurrence of a digit d in the RGS must precede
17 //% the k-th occurrence of the digit d+1.
18 //% Subset-lex order.
19 //% Cf. OEIS sequences A000085 (all tableaux),
20 //% A061343 (all shifted tableaux; using condition is_shifted(1)),
21 //% A210736 (shifted, height <= 2), A082395 (shifted, height <= 3).
22
23 // Cf. comb/young-tab-rgs-demo.cc for lexicographic order
24
25 //#define TIMING // uncomment to disable printing
26
27
28 int
main(int argc,char ** argv)29 main(int argc, char **argv)
30 {
31 ulong n = 6;
32 NXARG(n, "Length of strings");
33 // ulong m = 0;
34 // NXARG(m, "Number of allowed values for digits\n"
35 // " == max height of tableaux, 0 ==> all");
36 // if ( m>n ) m = n;
37 // if ( m==0 ) m = n;
38
39 young_tab_rgs_subset_lex Y(n);
40
41 ulong ct = 0;
42
43
44 #ifdef TIMING
45
46 Y.first();
47 do { ++ct; } while ( Y.next() );
48
49 #else // TIMING
50
51 bool tq = 0;
52 NXARG(tq, "Whether do draw tableaux (as ASCII art)");
53
54 ulong j = 0;
55 do
56 {
57 #if 0 // impose certain conditions
58 // if ( Y.height() != 4 ) continue;
59 // if ( ! Y.is_falling(1) ) continue; // A218293
60 // if ( ! Y.is_falling(2) ) continue; // A225121
61 // if ( ! Y.is_falling(3) ) continue; // A000000
62 // if ( ! Y.is_delayed(1) ) continue; // A000000
63
64 // if ( ! Y.is_shifted(1) ) continue; // A061343
65 if ( ! Y.is_shifted(2) ) continue; // A000000
66 // 1, 1, 1, 1, 3, 4, 10, 15, 35, 98, 226, 606, 1760, 4523, ...
67
68 // const ulong st[] = { 4, 2, 1 };
69 // ulong hh = sizeof(st)/sizeof(st[0]);
70 //// cout << " :: hh=" << hh << endl;
71 // if ( ! Y.has_shape(st, hh) ) continue;
72
73 #endif
74
75 ++ct;
76
77 #if 1
78 cout << setw(4) << ct << ": ";
79
80 Y.print(" "); // RGS
81 cout << setw(3) << j << " "; // leftmost change
82
83 Y.print_stats(" "); // stats: partition of n
84 cout << setw(3) << Y.height(); // height
85
86 #if 0 // list positions of first occurrence of digits:
87 ulong h = Y.height();
88 cout << " [ ";
89 for (ulong d=0; d<h; ++d)
90 {
91 ulong p = 0;
92 while ( Y.a_[p] != d ) ++p;
93 cout << p << " ";
94 }
95 cout << "]";
96 #endif
97
98 if ( tq )
99 {
100 cout << endl;
101 Y.print_aa( 1 ); // arg is offset (0 or 1)
102 cout << endl;
103 }
104
105
106 cout << endl;
107
108 jjassert( Y.OK() );
109 #endif
110 }
111 while ( (j=Y.next()) );
112
113
114 #endif // TIMING
115
116 cout << " ct=" << ct;
117 cout << endl;
118
119 return 0;
120 }
121 // -------------------------
122
123 /*
124 Timing: (Intel Xeon CPU E3-1275 V2 @ 3.50GHz)
125
126 GCC 4.9.2:
127
128 time ./bin 18
129 arg 1: 18 == n [Length of strings] default=6
130 ct=997313824
131 ./bin 18 8.45s user 0.00s system 99% cpu 8.464 total
132 ==> 997313824/8.45 == 118,025,304 per second
133 */
134
135 /*
136 Timing: (AMD Phenom II X4 945 3000MHz)
137
138 GCC 4.8.0:
139
140 time ./bin 18
141 arg 1: 18 == n [Length of strings] default=6
142 ct=997313824
143 ./bin 18 17.15s user 0.00s system 99% cpu 17.150 total
144 ==> 997313824/17.15 == 58,152,409 per second
145 */
146
147
148 /// Emacs:
149 /// Local Variables:
150 /// MyRelDir: "demo/comb"
151 /// makefile-dir: "../../"
152 /// make-target: "1demo DSRC=demo/comb/young-tab-rgs-subset-lex-demo.cc"
153 /// make-target2: "1demo DSRC=demo/comb/young-tab-rgs-subset-lex-demo.cc DEMOFLAGS=-DTIMING"
154 /// End:
155
156