1
2 #include "comb/mixedradix-sod-lex.h"
3
4
5 #include "nextarg.h" // NXARG()
6 #include "fxttypes.h"
7 #include "fxtalloca.h"
8 #include "fxtio.h"
9 #include "jjassert.h"
10
11 #include <cstdlib> // strtoul()
12
13 //% Mixed radix numbers with fixed sum of digits.
14 //% Also: k-subsets (combinations) of a multiset.
15
16
17 //#define TIMING // uncomment to disable printing
18
19 int
main(int argc,char ** argv)20 main(int argc, char **argv)
21 {
22 ulong n = 5;
23 NXARG(n, "Number of digits");
24
25 ulong s = 4;
26 NXARG(s, "Sum of digits");
27
28 ulong rr = 0;
29 NXARG(rr, "Base (radix) of digits (0==>falling factorial, 1==>rising factorial)");
30
31 ALLOCA(ulong, r, n);
32 for (ulong j=0; j<n; ++j) r[j] = rr;
33 RESTARGS("Optionally supply radix for all digits (rr ignored)");
34 if ( argc>4 ) jjassert( argc == (int)n+4 );
35 for (ulong i=4; i<(ulong)argc; ++i) r[i-4] = strtoul(argv[i], nullptr, 10);
36
37 mixedradix_sod_lex M(n, rr, ( argc > 4 ? r : nullptr ) );
38 jjassert( M.first(s) );
39 M.print_nines("Nines: ");
40 cout << endl;
41 cout << endl;
42
43 ulong ct = 0;
44 do
45 {
46 ++ct;
47 #ifndef TIMING
48 cout << setw(4) << ct << ":";
49 M.print(" ", true );
50 // print_mixedradix(" ", M.data(), n+2, 1);
51
52 // cout << setw(6) << M.to_num(); // == ct
53 cout << setw(4) << M.pos(); // == rightmost position of change
54
55 // if ( ct>0 ) // print lowest nonzero digit
56 // {
57 // ulong j=0; while ( 0==M.data()[j] ) ++j;
58 // cout << " @ " << M.data()[j];
59 // }
60
61 cout << endl;
62 jjassert( M.OK() );
63 #endif // TIMING
64 }
65 while ( M.next() );
66
67 cout << " ct=" << ct << endl;
68
69 return 0;
70 }
71 // -------------------------
72
73 /*
74 Timing:
75
76 time ./bin 22 12 8
77 ct=354539020
78 ./bin 22 12 8 4.92s user 0.00s system 99% cpu 4.918 total
79 ==> 354539020/4.92 == 72,060,776 per second
80
81 time ./bin 22 12 4
82 ct=263310740
83 ./bin 22 12 4 3.54s user 0.00s system 99% cpu 3.545 total
84 ==> 263310740/3.54 == 74,381,564 per second
85
86 time ./bin 32 20 2
87 ct=225792840
88 ./bin 32 20 2 4.87s user 0.01s system 99% cpu 4.879 total
89 ==> 225792840/4.87 == 46,364,032 per second
90
91 time ./bin 32 12 2
92 ct=225792840
93 ./bin 32 12 2 3.84s user 0.00s system 99% cpu 3.852 total
94 ==> 225792840/3.84 == 58,800,218 per second
95
96 */
97
98 /*
99 Timing: (AMD Phenom II X4 945 3000MHz)
100
101 time ./bin 22 12 8
102 ct=354539020
103 ./bin 22 12 8 2.56s user 0.00s system 99% cpu 2.560 total
104 ==> 354539020/2.56 == 138,491,804 per second
105
106 time ./bin 22 12 4
107 ct=263310740
108 ./bin 22 12 4 1.78s user 0.00s system 99% cpu 1.787 total
109 ==> 263310740/1.78 == 147,927,382 per second
110
111 time ./bin 32 20 2
112 ct=225792840
113 ./bin 32 20 2 2.26s user 0.00s system 99% cpu 2.266 total
114 ==> 225792840/2.26 == 99,908,336 per second
115
116 time ./bin 32 12 2
117 ct=225792840
118 ./bin 32 12 2 2.03s user 0.00s system 99% cpu 2.037 total
119 ==> 225792840/2.03 == 111,228,000 per second
120
121 */
122
123 /// Emacs:
124 /// Local Variables:
125 /// MyRelDir: "demo/comb"
126 /// makefile-dir: "../../"
127 /// make-target: "1demo DSRC=demo/comb/mixedradix-sod-lex-demo.cc"
128 /// make-target2: "1demo DSRC=demo/comb/mixedradix-sod-lex-demo.cc DEMOFLAGS=-DTIMING"
129 /// End:
130
131