1
2 #include "comb/perm-rec.h"
3 #include "comb/fact2perm.h"
4
5 #include "perm/perminvert.h"
6
7 #include "comb/comb-print.h"
8 #include "perm/printcycles.h"
9
10 #include "fxtio.h"
11 #include "nextarg.h"
12 #include "fxttypes.h"
13
14
15 //% All cyclic permutations by an recursive algorithm.
16
17 //#define TIMING // uncomment to disable printing
18
19 static ulong ct = 0;
20 bool cq;
21
22 #ifdef TIMING
visit(const perm_rec &)23 void visit(const perm_rec &) { ++ct; }
24 #else
visit(const perm_rec & P)25 void visit(const perm_rec &P) // function to call with each permutation
26 {
27 bool dfz = true; // whether to print dots for zeros
28
29 static ulong ff[32];
30
31 cout << setw(4) << ct << ":";
32 ++ct;
33
34 ulong n = P.n_;
35 const ulong * p = P.data();
36
37 print_perm(" ", p, n, dfz);
38
39 print_cycles(" ", p, n);
40
41 static ulong ii[32];
42 make_inverse(p, ii, n);
43 print_perm(" ", ii, n, dfz);
44
45 perm2ffact_swp(p, n, ff);
46 print_mixedradix(" ", ff, n-1, dfz);
47
48 cout << endl;
49 }
50 // -------------------------
51 #endif
52
53
54 int
main(int argc,char ** argv)55 main(int argc, char **argv)
56 {
57 ulong n = 5;
58 NXARG(n, "Number of elements to permute");
59 cq = 1;
60 NXARG(cq, "Whether to generate only cyclic permutations");
61
62 perm_rec P(n);
63
64 if ( cq ) P.generate_cyclic(visit);
65 else P.generate(visit);
66
67 cout << "ct=" << ct << endl;
68 // cout << "rct=" << P.rct_ << endl;
69
70 return 0;
71 }
72 // -------------------------
73
74 /*
75 Timing:
76
77 all:
78 time ./bin 12 0
79 ct=479001600
80 ./bin 12 0 8.39s user 0.04s system 99% cpu 8.433 total
81 ==> 12!/8.39 == 57,091,966 per second
82
83 cyclic:
84 time ./bin 13 1
85 ct=479001600
86 ./bin 13 1 12.87s user 0.07s system 99% cpu 12.937 total
87 ==> 12!/12.87 == 37,218,461 per second
88
89 BENCHARGS=12 0
90 BENCHARGS=13 1
91
92 */
93
94
95 /// Emacs:
96 /// Local Variables:
97 /// MyRelDir: "demo/comb"
98 /// makefile-dir: "../../"
99 /// make-target: "1demo DSRC=demo/comb/perm-rec-demo.cc"
100 /// make-target2: "1demo DSRC=demo/comb/perm-rec-demo.cc DEMOFLAGS=-DTIMING"
101 /// End:
102
103