1
2 #include "comb/descent-rgs.h"
3
4 #include "comb/comb-print.h"
5
6 //#include "comb/is-descent-rgs.h"
7
8 #include "fxtio.h"
9 #include "fxttypes.h"
10 #include "jjassert.h"
11
12 #include "nextarg.h"
13
14 //% Descent sequences (restricted growth strings, RGS).
15 //% A descent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0,
16 //% d(k)>=0, and d(k) <= 1 + desc([d(1), d(2), ..., d(k-1)]) and desc(.)
17 //% counts the number of descents of its argument.
18 //% Lexicographic order.
19 //% See OEIS sequence A225588.
20
21 // Cf. comb/descent-rgs-stats-demo.cc for stats for descent RGS
22 // Cf. comb/ascent-rgs-demo.cc for ascent RGS
23
24 //#define TIMING // uncomment to disable printing
25
26
27 int
main(int argc,char ** argv)28 main(int argc, char **argv)
29 {
30 ulong n = 6;
31 NXARG(n, "Length of strings");
32
33 descent_rgs D(n);
34
35 ulong ct = 0;
36
37
38 #ifdef TIMING
39 bool bw = 0;
40 NXARG(bw, "Whether to generate in backward order");
41 #ifdef DESCENT_RGS_FIXARRAYS
42 cout << "DESCENT_RGS_FIXARRAYS defined." << endl;
43 #endif
44 if ( bw )
45 {
46 cout << "backward:" << endl;
47 D.last();
48 do { ++ct; } while ( D.prev() );
49 }
50 else
51 {
52 cout << "forward:" << endl;
53 D.first();
54 do { ++ct; } while ( D.next() );
55 }
56 #else
57
58 ulong j = 0;
59 do
60 {
61 #if 0
62 { // limit max digit:
63 const ulong *x = D.data();
64 bool q = true;
65 const ulong b = 3;
66 // b = 1 ==> 2^(n-1)
67 // b = 2 ==> A164039: a(n+1) = 3*a(n) - n
68 // b = 3 ==> A000000
69 for (ulong i=0; i<n; ++i)
70 if ( x[i] > b ) { q=false; break; }
71 if ( ! q ) continue;
72 }
73 #endif
74 #if 0 // no flat-steps: A238425:
75 {
76 const ulong *x = D.data();
77 bool q = true;
78 for (ulong i=1; i<n; ++i)
79 if ( 0==( x[i] - x[i-1] ) ) { q=false; break; }
80 if ( ! q ) continue;
81 }
82 #endif
83 // if ( is_ascent_rgs( D.data(), n) ) continue;
84 // such descent RGS exists for n>=7
85
86 ++ct;
87
88
89 #if 1
90 cout << setw(4) << ct << ": ";
91
92 // print RGS:
93 D.print(" ", true );
94 print_vec(" ", D.m_, n, true );
95
96 cout << setw(4) << j;
97
98 cout << endl;
99 jjassert( D.OK() );
100 #endif
101 }
102 while ( (j=D.next()) );
103
104 #endif // TIMING
105
106 cout << " ct=" << ct; // OEIS sequence A022493
107 cout << endl;
108
109 return 0;
110 }
111 // -------------------------
112
113
114 /*
115 Timing: (AMD Phenom II X4 945 3000MHz)
116
117
118 time ./bin 16 0
119 arg 1: 16 == n [Length of strings] default=6
120 arg 2: 0 == bw [Whether to generate in backward order] default=0
121 forward:
122 ct=1146389206
123 ./bin 16 0 4.17s user 0.00s system 99% cpu 4.171 total
124 ==> 1146389206/4.17 == 274,913,478 per second
125
126 time ./bin 16 1
127 arg 1: 16 == n [Length of strings] default=6
128 arg 2: 1 == bw [Whether to generate in backward order] default=0
129 backward:
130 ct=1146389206
131 ./bin 16 1 4.98s user 0.00s system 99% cpu 4.982 total
132 ==> 1146389206/4.98 == 230,198,635 per second
133
134
135 time ./bin 16 0
136 arg 1: 16 == n [Length of strings] default=6
137 arg 2: 0 == bw [Whether to generate in backward order] default=0
138 DESCENT_RGS_FIXARRAYS defined.
139 forward:
140 ct=1146389206
141 ./bin 16 0 4.04s user 0.00s system 99% cpu 4.039 total
142 ==> 1146389206/4.04 == 283,759,704 per second
143
144 time ./bin 16 1
145 arg 1: 16 == n [Length of strings] default=6
146 arg 2: 1 == bw [Whether to generate in backward order] default=0
147 DESCENT_RGS_FIXARRAYS defined.
148 backward:
149 ct=1146389206
150 ./bin 16 1 4.93s user 0.00s system 99% cpu 4.933 total
151 ==> 1146389206/4.93 == 232,533,307 per second
152
153 */
154
155
156 /// Emacs:
157 /// Local Variables:
158 /// MyRelDir: "demo/comb"
159 /// makefile-dir: "../../"
160 /// make-target: "1demo DSRC=demo/comb/descent-rgs-demo.cc"
161 /// make-target2: "1demo DSRC=demo/comb/descent-rgs-demo.cc DEMOFLAGS=-DTIMING"
162 /// End:
163
164