1
2 #include "sort/equivclasses.h" // equivalence_classes()
3 #include "sort/sortbykey.h" // sort_by_key()
4
5 #include "bits/revbin.h" // revbin()
6
7
8 //#include "perm/permrand.h" // random_permute()
9
10 #include "bits/print-bin.h" // print_bin()
11 #include "nextarg.h" // NXARG()
12 #include "fxttypes.h" // ulong
13 //#include "bits/bitsperlong.h"
14
15 #include "fxtio.h"
16 #include "fxtalloca.h"
17
18
19 //% Equivalence classes: bit-strings with reversal and complement.
20 // Entry A005418 in the OEIS.
21
22 static ulong nb; // number of bits
23 static ulong mm; // mask to complement
24
bs_equiv_q(ulong x,ulong y)25 bool bs_equiv_q(ulong x, ulong y) // identify words that are mutal reverses
26 {
27 if ( x==y ) return 1;
28 if ( x==revbin(y, nb) ) return 1;
29 return 0;
30 }
31 // -------------------------
32
bsu_equiv_q(ulong x,ulong y)33 bool bsu_equiv_q(ulong x, ulong y) // unlabeled bit-strings
34 {
35 if ( bs_equiv_q(y, x) ) return 1;
36 x ^= mm;
37 if ( bs_equiv_q(y, x) ) return 1;
38 return 0;
39 }
40 // -------------------------
41
42
43 int
main(int argc,char ** argv)44 main(int argc, char **argv)
45 {
46 nb = 6;
47 NXARG(nb, "Number of bits of bit-strings (0<nb<BITS_PER_LONG).");
48 ulong n = 1UL<<nb;
49 mm = n-1;
50
51 ulong cq = 1;
52 NXARG(cq, "Whether equivalence includes complements (==> unlabeled bit-strings).");
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, bs_equiv_q, e);
63 else equivalence_classes(s, n, bsu_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 % for n in $(seq 1 15) ; do echo -n $n:; ./bin $n 0 | grep 'of equiv'| cut -d= -f2; done
121 1: 2
122 2: 3
123 3: 6
124 4: 10
125 5: 20
126 6: 36
127 7: 72
128 8: 136
129 9: 272
130 10: 528
131 11: 1056
132 12: 2080
133 13: 4160
134 14: 8256
135 15: 16512
136
137 unlabled: (shifted version of the same sequence)
138 % for n in $(seq 1 15) ; do echo -n $n:; ./bin $n 1 | grep 'of equiv'| cut -d= -f2; done
139 1: 1
140 2: 2
141 3: 3
142 4: 6
143 5: 10
144 6: 20
145 7: 36
146 8: 72
147 9: 136
148 10: 272
149 11: 528
150 12: 1056
151 13: 2080
152 14: 4160
153 15: 8256
154 http://oeis.org/A005418
155 Number of n-bead black-white reversible strings; also binary grids;
156 */
157
158 /// Emacs:
159 /// Local Variables:
160 /// MyRelDir: "demo/sort"
161 /// makefile-dir: "../../"
162 /// make-target: "1demo DSRC=demo/sort/equivclass-bitstring-demo.cc"
163 /// make-target2: "1demo DSRC=demo/sort/equivclass-bitstring-demo.cc DEMOFLAGS=-DTIMING"
164 /// End:
165
166