1
2 // demo-is-self-contained
3
4 #include "comb/composition-nz-rank.h"
5
6 #include "comb/comb-print.h"
7 #include "bits/print-bin.h"
8
9 #include "fxtio.h"
10
11 #include "jjassert.h"
12
13 #include "fxttypes.h"
14 #include "nextarg.h"
15
16 //% Compositions of n into positive parts.
17 //% Gray code with moves of only one unit, all moves are one-close or
18 //% two-close, two-close moves always cross a part =1 and all moves are
19 //% at the end, involving the last element.
20 //% Recursive algorithm.
21
22
23 // Cf. comb/composition-nz-gray-demo.cc iterative version.
24 // Cf. comb/composition-nz-demo.cc for compositions in lexicographic order.
25 // Cf. comb/composition-nz-rl-demo.cc for compositions in run-length order
26 // Cf. comb/composition-nz-subset-lex-demo.cc for compositions in subset-lex order
27
28
29 //#define TIMING // uncomment to disable printing
30
31 ulong N;
32 ulong *a; // composition
33
visit(ulong m)34 void visit(ulong m)
35 {
36 // for (ulong j=1; j<m; ++j)
37 // if ( a[j-1] < a[j] ) return; // partitions
38 // for (ulong j=1; j<m; ++j)
39 // if ( a[j-1] == a[j] ) return; // distinct parts
40
41 static ulong ct = 0;
42 cout << setw(4) << ct << ":";
43 print_vec(" ", a, m);
44 cout << endl;
45
46 ulong s = 0;
47 for (ulong j=0; j<m; ++j) s += a[j];
48 jjassert( s == N );
49
50 #if 0 // check rank (only with forward order)
51 const ulong r = composition_nz_gray_rank( a, m, N );
52 // print_bin(" ", r, (N>1 ? N-1 : 1) );
53 jjassert( r == ct );
54 #endif
55 ++ct;
56 }
57 // -------------------------
58
59
60 void F(ulong n, ulong m);
61 void B(ulong n, ulong m);
62
F(ulong n,ulong m=0)63 void F(ulong n, ulong m=0)
64 {
65 if ( n==0 )
66 {
67 #ifndef TIMING
68 visit(m);
69 #endif
70 return;
71 }
72
73 for (ulong f=n; f!=0; --f) // first part decreasing
74 {
75 a[m] = f;
76 if ( 0 == (f & 1) ) F(n-f, m+1);
77 else B(n-f, m+1);
78 }
79 }
80 // -------------------------
81
82
B(ulong n,ulong m=0)83 void B(ulong n, ulong m=0)
84 {
85 if ( n==0 )
86 {
87 #ifndef TIMING
88 visit(m);
89 #endif
90 return;
91 }
92
93 for (ulong f=1; f<=n; ++f) // first part increasing
94 {
95 a[m] = f;
96 if ( 0 == (f & 1) ) B(n-f, m+1);
97 else F(n-f, m+1);
98 }
99 }
100 // -------------------------
101
102
103 int
main(int argc,char ** argv)104 main(int argc, char **argv)
105 {
106 ulong n = 7;
107 NXARG(n, "compositions of n");
108 N = n;
109 bool bq = 0;
110 NXARG(bq, "whether to generate backward order");
111
112 a = new ulong[n];
113
114 if ( bq )
115 {
116 cout << "backward:" << endl;
117 B(n);
118 }
119 else
120 {
121 cout << "forward:" << endl;
122 F(n);
123 }
124
125 #ifdef TIMING
126 cout << " ct=" << ( n ? 1UL<<(n-1) : 1 ) << endl;
127 #endif
128
129 delete [] a;
130
131 return 0;
132 }
133 // -------------------------
134
135 /*
136 Timing: (AMD Phenom II X4 945 3000MHz)
137
138 GCC 4.9.0:
139
140 time ./bin 30 0
141 arg 1: 30 == n [compositions of n] default=7
142 arg 2: 0 == bq [whether to generate backward order] default=0
143 forward:
144 ct=536870912
145 ./bin 30 0 4.50s user 0.00s system 99% cpu 4.504 total
146 ==> 536870912/4.50 == 119,304,647 per second
147
148 time ./bin 30 1
149 arg 1: 30 == n [compositions of n] default=7
150 arg 2: 1 == bq [whether to generate backward order] default=0
151 backward:
152 ct=536870912
153 ./bin 30 1 3.79s user 0.00s system 99% cpu 3.791 total
154 ==> 536870912/3.79 == 141,654,594 per second
155
156 */
157
158 /*
159 BENCHARGS=30 0
160 BENCHARGS=30 1
161 */
162
163
164
165 /// Emacs:
166 /// Local Variables:
167 /// MyRelDir: "demo/comb"
168 /// makefile-dir: "../../"
169 /// make-target: "1demo DSRC=demo/comb/composition-nz-gray-rec-demo.cc"
170 /// make-target2: "1demo DSRC=demo/comb/composition-nz-gray-rec-demo.cc DEMOFLAGS=-DTIMING"
171 /// End:
172
173