1
2 #include "sort/equivclasses.h" // equivalence_classes()
3 #include "sort/sortbykey.h" // sort_by_key()
4
5 #include "bits/bitcyclic-dist.h" // bit_cyclic_dist()
6 //#include "bits/revbin.h" // revbin()
7
8
9 //#include "perm/permrand.h" // random_permute()
10
11 #include "bits/print-bin.h" // print_bin()
12 #include "nextarg.h" // NXARG()
13 #include "fxttypes.h" // ulong
14 //#include "bits/bitsperlong.h"
15
16 #include "fxtio.h"
17 #include "fxtalloca.h"
18
19
20 //% Equivalence classes: binary necklaces.
21
22
23 static ulong nb; // number of bits
24 static ulong mm; // mask to complement
25
n_equiv_q(ulong x,ulong y)26 bool n_equiv_q(ulong x, ulong y) // necklaces
27 {
28 ulong d = bit_cyclic_dist(x, y, nb);
29 return (0==d);
30 }
31 // -------------------------
32
nu_equiv_q(ulong x,ulong y)33 bool nu_equiv_q(ulong x, ulong y) // unlabeled necklaces
34 {
35 ulong d = bit_cyclic_dist(x, y, nb);
36 if ( 0!=d ) d = bit_cyclic_dist(mm^x, y, nb);
37 return (0==d);
38 }
39 // -------------------------
40
41
42
43 int
main(int argc,char ** argv)44 main(int argc, char **argv)
45 {
46 nb = 4;
47 NXARG(nb, "Number of bits of necklaces (0<nb<BITS_PER_LONG).");
48 ulong n = 1UL<<nb;
49 mm = n-1;
50
51 ulong cq = 0;
52 NXARG(cq, "Whether equivalence includes complements (==> unlabeled necklaces).");
53
54 ulong ksq = 0;
55 NXARG(ksq, "Whether to print key-sorted array.");
56
57 ALLOCA(ulong, s, n);
58 for (ulong k=0; k<n; ++k) s[k] = k;
59 // random_permute(s, n);
60
61 ulong *e = new ulong[n];
62 if ( 0==cq ) equivalence_classes(s, n, n_equiv_q, e);
63 else equivalence_classes(s, n, nu_equiv_q, e);
64
65 // --- print all elements with 'coset leaders':
66 for (ulong k=0; k<n; ++k)
67 {
68 cout << setw(3) << k << ": ";
69 print_bin(" ", s[k], nb);
70 cout << " " << setw(2) << e[k];
71 cout << endl;
72 }
73 cout << endl;
74
75
76 sort_by_key(s, n, e, nullptr, true);
77 if ( ksq )
78 {
79 for (ulong k=0; k<n; ++k)
80 {
81 cout << setw(3) << k << ": ";
82 print_bin(" ", s[k], nb);
83 cout << " " << setw(2) << e[k];
84 cout << endl;
85 }
86 cout << endl;
87 }
88
89 // --- print all elements in each equivalence class:
90 ulong cct = 0; // count number of classes
91 for (ulong k=0; k<n; /**/ )
92 {
93 ++cct;
94 ulong el = e[k];
95 cout << setw(3) << el << ": ";
96 ulong ct;
97 for (ct=0; k<n; ++ct, ++k)
98 {
99 ulong ek = e[k];
100 if ( ek != el )
101 {
102 break;
103 }
104 print_bin(" ", s[k], nb);
105 }
106 cout << " [#=" << ct << "]";
107 cout << endl;
108 }
109 cout << endl;
110 cout << " # of equivalence classes = " << cct << "";
111 cout << endl;
112
113 delete [] e;
114
115 return 0;
116 }
117 // -------------------------
118
119 /*
120 # of necklaces:
121 % for n in $(seq 1 14); do echo -n "$n: "; ./bin $n 0 | grep 'equivalence classes' | cut -d= -f2; done
122 1: 2
123 2: 3
124 3: 4
125 4: 6
126 5: 8
127 6: 14
128 7: 20
129 8: 36
130 9: 60
131 10: 108
132 11: 188
133 12: 352
134 13: 632
135 14: 1182
136
137 # of unlabeled necklaces:
138 % for n in $(seq 1 14); do echo -n "$n: "; ./bin $n 1 | grep 'equivalence classes' | cut -d= -f2; done
139 1: 1
140 2: 2
141 3: 2
142 4: 4
143 5: 4
144 6: 8
145 7: 10
146 8: 20
147 9: 30
148 10: 56
149 11: 94
150 12: 180
151 13: 316
152 14: 596
153
154 */
155
156 /// Emacs:
157 /// Local Variables:
158 /// MyRelDir: "demo/sort"
159 /// makefile-dir: "../../"
160 /// make-target: "1demo DSRC=demo/sort/equivclass-necklaces-demo.cc"
161 /// make-target2: "1demo DSRC=demo/sort/equivclass-necklaces-demo.cc DEMOFLAGS=-DTIMING"
162 /// End:
163
164