1
2 #include "comb/setpart-zero-map-rgs.h"
3 #include "comb/is-zero-map-rgs.h"
4 #include "comb/print-zero-map-rgs.h"
5
6 #include "comb/comb-print.h"
7
8 #include "fxtio.h"
9
10 #include "jjassert.h"
11
12 #include "fxttypes.h"
13 #include "nextarg.h"
14
15
16 //% Restricted growth strings (RGS) for set partitions:
17 //% each digit a[k] is either zero or a[k] < k and a[a[k]] == 0.
18 //% Same as: maps from {1, 2, 3, ..., n} to {0, 1, 2, 3, ..., n}
19 //% such that f(x) < x and f(f(x)) == 0.
20 //% Cf. OEIS sequence A000110.
21
22 // Cf. comb/setpart-s-zero-map-rgs-demo.cc for set partitions into parts <= s+1
23 // Cf. comb/setpart-rgs-lex-demo.cc for the "usual" RGS for set partitions
24 // Cf. comb/setpart-p-rgs-lex-demo.cc for the "usual" RGS for set partitions into p parts
25 // Cf. comb/setpart-ck-rgs-demo.cc for the Cooper-Kennedy RGS
26
27 //#define TIMING // uncomment to disable printing
28
29 int
main(int argc,char ** argv)30 main(int argc, char **argv)
31 {
32 ulong n = 5;
33 NXARG(n, "RGS of length n");
34
35 setpart_zero_map_rgs P(n);
36
37 ulong ct = 0;
38
39 #ifdef TIMING
40 do { ++ct; } while ( P.next() );
41 #else
42
43 do
44 {
45 ++ct;
46 cout << setw(4) << ct << ":";
47
48 P.print(" ", true);
49 P.print_fp_rgs(" ", true, true);
50 P.print_setpart(" ", false);
51
52 cout << endl;
53
54 jjassert( P.OK() );
55 // jjassert( is_zero_map_rgs(P.data(), n) );
56 }
57 while ( (P.next()) );
58 #endif // TIMING
59
60 cout << " ct=" << ct << endl; // A000110
61
62 return 0;
63 }
64 // -------------------------
65
66 /*
67 Timing: (AMD Phenom II X4 945 3000MHz)
68
69 time ./bin 15
70 arg 1: 15 == n [RGS of length n] default=4
71 ct=1382958545
72 ./bin 15 6.33s user 0.00s system 99% cpu 6.338 total
73 ==> 1382958545/6.33 == 218,476,863 per second
74
75
76 // using the "slight optimization" in next():
77 time ./bin 15
78 arg 1: 15 == n [RGS of length n] default=5
79 ct=1382958545
80 ./bin 15 5.99s user 0.00s system 99% cpu 5.988 total
81 ==> 1382958545/5.99 == 230,877,887 per second
82 */
83
84
85 /// Emacs:
86 /// Local Variables:
87 /// MyRelDir: "demo/comb"
88 /// makefile-dir: "../../"
89 /// make-target: "1demo DSRC=demo/comb/setpart-zero-map-rgs-demo.cc"
90 /// make-target2: "1demo DSRC=demo/comb/setpart-zero-map-rgs-demo.cc DEMOFLAGS=-DTIMING"
91 /// End:
92
93