1
2 #include "comb/perm-trotter.h"
3
4 //#include "comb/fact2perm.h"
5
6 //#include "perm/perm2ccf.h"
7 //#include "perm/printcycles.h"
8 //#include "perm/permq.h"
9 //#include "perm/perm-genus.h"
10
11 #include "fxttypes.h"
12 #include "fxtio.h"
13 #include "nextarg.h"
14 #include "jjassert.h"
15
16
17 //% Generate all permutations in strong minimal-change order using Trotter's algorithm.
18 //% Smallest element moves most often.
19
20 //#define TIMING // uncomment to disable printing
21
22 int
main(int argc,char ** argv)23 main(int argc, char **argv)
24 {
25 ulong n = 4;
26 NXARG(n, "Permutations of n elements.");
27 bool bq = 0;
28 NXARG(bq, "Whether to go backwards.");
29
30 perm_trotter P(n);
31 if ( bq ) P.last();
32
33
34 #ifdef TIMING
35 #ifdef PERM_TROTTER_OPT
36 cout << "PERM_TROTTER_OPT is defined." << endl;
37 #endif
38 ulong ct = 0;
39 if ( !bq )
40 {
41 cout << "forward:" << endl;
42 do { ++ct; } while ( P.next() );
43 }
44 else
45 {
46 cout << "backward:" << endl;
47 do { ++ct; } while ( P.prev() );
48 }
49 cout << "ct=" << ct << endl;
50
51 #else // TIMING
52
53 const bool dfz = true; // whether to print dots for zeros
54
55 ulong ct = 0;
56 // ulong fc[32];
57 do
58 {
59 #if 0
60 // if ( ! is_involution(P.data(), n) ) continue;
61 // if ( ! is_simple(P.data(), n) ) continue;
62
63 { ulong cpi[n];
64 if ( 0 != perm_genus(P.data(), n, cpi) ) continue;
65 }
66 #endif
67 cout << setw(4) << ct << ":";
68 ++ct;
69
70 P.print(" ", dfz);
71
72 ulong sw1, sw2;
73 P.get_swap(sw1, sw2);
74 cout << " (" << sw1 << ", " << sw2 << ") ";
75
76 P.print_inv(" ", dfz);
77
78 // print directions:
79 cout << " ";
80 for (ulong j=0; j<n; ++j) cout << " " << (P.d_[j]==1?'+':'-');
81
82 // perm2ffact(P.invdata(), n, fc);
83 // print_mixedradix(" fc = ", fc, n-1);
84 // print_cycles(" ", P.data(), n);
85 // print_ccf(" ", P.data(), n);
86
87 cout << endl;
88 }
89 while ( ( ! bq ? P.next() : P.prev()) );
90 cout << " ct=" << ct << endl;
91 #endif // TIMING
92
93 return 0;
94 }
95 // -------------------------
96
97 /*
98 Timing: (Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz)
99 GCC 8.3.0
100
101 time ./bin 13 0
102 arg 1: 13 == n [Permutations of n elements.] default=4
103 arg 2: 0 == bq [Whether to go backwards.] default=0
104 PERM_TROTTER_OPT is defined.
105 forward:
106 ct=6227020800
107 ./bin 13 0 14.66s user 0.00s system 99% cpu 14.658 total
108 ==> 6227020800 / 14.66 == 424,762,673 per second
109
110 time ./bin 13 1
111 arg 1: 13 == n [Permutations of n elements.] default=4
112 arg 2: 1 == bq [Whether to go backwards.] default=0
113 PERM_TROTTER_OPT is defined.
114 backward:
115 ct=6227020800
116 ./bin 13 1 14.70s user 0.00s system 99% cpu 14.703 total
117 ==> 6227020800 / 14.70 == 423,606,857 per second
118
119
120 time ./bin 13 0
121 arg 1: 13 == n [Permutations of n elements.] default=4
122 arg 2: 0 == bq [Whether to go backwards.] default=0
123 forward:
124 ct=6227020800
125 ./bin 13 0 26.82s user 0.00s system 99% cpu 26.821 total
126
127 time ./bin 13 1
128 arg 1: 13 == n [Permutations of n elements.] default=4
129 arg 2: 1 == bq [Whether to go backwards.] default=0
130 backward:
131 ct=6227020800
132 ./bin 13 1 28.45s user 0.00s system 99% cpu 28.458 total
133
134 */
135
136 /*
137 Timing: (AMD Phenom II X4 945 3000MHz)
138
139 time ./bin 13 0
140 PERM_TROTTER_OPT is defined.
141 forward:
142 ct=6227020800
143 ./bin 13 0 12.52s user 0.00s system 99% cpu 12.518 total
144 ==> 6227020800/12.52 == 497,365,878 per second
145
146 time ./bin 13 1
147 arg 1: 13 == n [Permutations of n elements (n>=1).] default=4
148 arg 2: 1 == bq [Whether to go backwards.] default=0
149 PERM_TROTTER_OPT is defined.
150 backward:
151 ct=6227020800
152 ./bin 13 1 13.28s user 0.00s system 99% cpu 13.285 total
153 ==> 6227020800/13.28 == 468,902,168 per second
154
155
156 ---- Regression with GCC 4.8.0:
157
158 time ./bin 13 0
159 arg 1: 13 == n [Permutations of n elements.] default=4
160 arg 2: 0 == bq [Whether to go backwards.] default=0
161 PERM_TROTTER_OPT is defined.
162 forward:
163 ct=6227020800
164 ./bin 13 0 27.82s user 0.01s system 99% cpu 27.835 total
165 ==> 6227020800/27.82 == 223,832,523 per second
166
167 time ./bin 13 1
168 arg 1: 13 == n [Permutations of n elements.] default=4
169 arg 2: 1 == bq [Whether to go backwards.] default=0
170 PERM_TROTTER_OPT is defined.
171 backward:
172 ct=6227020800
173 ./bin 13 1 29.83s user 0.00s system 99% cpu 29.840 total
174 ==> 6227020800/29.83 == 208,750,278 per second
175
176 */
177
178 /*
179 BENCHARGS=13 0
180 BENCHARGS=13 1
181 */
182
183
184 /// Emacs:
185 /// Local Variables:
186 /// MyRelDir: "demo/comb"
187 /// makefile-dir: "../../"
188 /// make-target: "1demo DSRC=demo/comb/perm-trotter-demo.cc"
189 /// make-target2: "1demo DSRC=demo/comb/perm-trotter-demo.cc DEMOFLAGS=-DTIMING"
190 /// End:
191
192