1 //
2 // libsemigroups - C++ library for semigroups and monoids
3 // Copyright (C) 2019 James D. Mitchell
4 //
5 // This program is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 //
18 
19 #include <cstddef>  // for size_t
20 #include <vector>   // for vector
21 
22 #include "bmat8.hpp"                 // for BMat8
23 #include "catch.hpp"                 // for LIBSEMIGROUPS_TEST_CASE
24 #include "froidure-pin.hpp"          // for FroidurePin, FroidurePi...
25 #include "libsemigroups-config.hpp"  // for LIBSEMIGROUPS_SIZEOF_VO...
26 #include "test-main.hpp"
27 #include "types.hpp"  // for word_type
28 
29 namespace libsemigroups {
30   struct LibsemigroupsException;
31 
32   bool constexpr REPORT = false;
33 
34 #if (!(defined(LIBSEMIGROUPS_DENSEHASHMAP)) && LIBSEMIGROUPS_SIZEOF_VOID_P == 8)
35 
36   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
37                           "001",
38                           "(BMat8) regular boolean mat monoid 4",
39                           "[quick][froidure-pin][bmat8]") {
40     auto               rg = ReportGuard(REPORT);
41     std::vector<BMat8> gens
42         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
43            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
44            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}),
45            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}})};
46 
47     FroidurePin<BMat8> S(gens);
48 
49     REQUIRE(S.current_max_word_length() == 1);
50     REQUIRE(!S.finished());
51     REQUIRE(!S.started());
52     REQUIRE(S.current_position(S.generator(0) * S.generator(3)) == UNDEFINED);
53     REQUIRE(S.current_position(BMat8({{1, 0, 0, 1, 1},
54                                       {0, 1, 0, 0, 1},
55                                       {1, 0, 1, 0, 1},
56                                       {0, 0, 1, 0, 1},
57                                       {0, 0, 0, 0, 0}}))
58             == UNDEFINED);
59     REQUIRE(S.current_size() == 4);
60     REQUIRE(S.current_nr_rules() == 0);
61     REQUIRE(S.length_const(0) == 1);
62     REQUIRE(S.length_non_const(5) == 2);
63 
64     REQUIRE(S.size() == 63904);
65     REQUIRE(S.nr_idempotents() == 2360);
66     REQUIRE(S.word_to_pos({0, 1, 2, 0, 1, 2}) == 378);
67     REQUIRE(S.word_to_element({0, 1, 2, 0, 1, 2})
68             == BMat8({{1, 0, 0, 1}, {0, 1, 0, 0}, {1, 0, 1, 0}, {0, 0, 1, 0}}));
69     REQUIRE(S.current_max_word_length() == 21);
70     REQUIRE(S.degree() == 8);
71     REQUIRE(S.nr_generators() == 4);
72     REQUIRE(S.generator(0)
73             == BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}));
74     REQUIRE(S.generator(1)
75             == BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}));
76     REQUIRE(S.generator(2)
77             == BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}));
78     REQUIRE(S.generator(3)
79             == BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}}));
80     REQUIRE(S.finished());
81     REQUIRE(S.started());
82     REQUIRE(S.current_position(S.generator(0) * S.generator(3)) == 7);
83     REQUIRE(S.current_position(BMat8({{1, 0, 0, 1, 1},
84                                       {0, 1, 0, 0, 1},
85                                       {1, 0, 1, 0, 1},
86                                       {0, 0, 1, 0, 1},
87                                       {0, 0, 0, 0, 0}}))
88             == UNDEFINED);
89     REQUIRE(S.current_nr_rules() == 13716);
90     REQUIRE(S.prefix(0) == UNDEFINED);
91     REQUIRE(S.suffix(0) == UNDEFINED);
92     REQUIRE(S.first_letter(0) == 0);
93     REQUIRE(S.final_letter(0) == 0);
94     REQUIRE(S.batch_size() == 8192);
95     REQUIRE(S.length_const(0) == 1);
96     REQUIRE(S.length_const(7) == 2);
97     REQUIRE(S.length_const(63903) == 21);
98     REQUIRE(S.length_non_const(7) == 2);
99     REQUIRE(S.length_non_const(63903) == 21);
100     REQUIRE(S.product_by_reduction(0, 3) == 7);
101     REQUIRE(S.fast_product(0, 3) == 7);
102     REQUIRE(S.letter_to_pos(0) == 0);
103     REQUIRE(S.letter_to_pos(1) == 1);
104     REQUIRE(S.letter_to_pos(2) == 2);
105     REQUIRE(S.letter_to_pos(3) == 3);
106     REQUIRE(!S.is_idempotent(0));
107     REQUIRE(S.is_idempotent(3));
108     REQUIRE(!S.is_idempotent(7));
109     REQUIRE(S.nr_rules() == 13716);
110     REQUIRE(S.contains(S.generator(1)));
111     REQUIRE(!S.contains(BMat8({{1, 0, 0, 1, 1},
112                                {0, 1, 0, 0, 1},
113                                {1, 0, 1, 0, 1},
114                                {0, 0, 1, 0, 1},
115                                {0, 0, 0, 0, 0}})));
116     REQUIRE(S.position(S.generator(1)) == 1);
117     REQUIRE(S.position(S.generator(0) * S.generator(3)) == 7);
118     REQUIRE(S.position(BMat8({{1, 0, 0, 1, 1},
119                               {0, 1, 0, 0, 1},
120                               {1, 0, 1, 0, 1},
121                               {0, 0, 1, 0, 1},
122                               {0, 0, 0, 0, 0}}))
123             == UNDEFINED);
124 
125     REQUIRE(S.sorted_position(BMat8({{1, 0, 0, 1, 1},
126                                      {0, 1, 0, 0, 1},
127                                      {1, 0, 1, 0, 1},
128                                      {0, 0, 1, 0, 1},
129                                      {0, 0, 0, 0, 0}}))
130             == UNDEFINED);
131     REQUIRE(S.sorted_position(S.generator(0)) == 18185);
132     REQUIRE(S.sorted_position(S.generator(3)) == 33066);
133     REQUIRE(S.sorted_position(S.generator(0) * S.generator(3)) == 18184);
134     REQUIRE(S.position_to_sorted_position(0) == 18185);
135     REQUIRE(S.position_to_sorted_position(3) == 33066);
136     REQUIRE(S.position_to_sorted_position(7) == 18184);
137 
138     REQUIRE(S.at(7) == S.generator(0) * S.generator(3));
139     REQUIRE(S[7] == S[0] * S[3]);
140 
141     REQUIRE(S.sorted_at(18185) == S.at(0));
142     REQUIRE(S.sorted_at(33066) == S.at(3));
143     REQUIRE(S.sorted_at(18184) == S.generator(0) * S.generator(3));
144 
145     REQUIRE(S.right(0, 3) == 7);
146     REQUIRE(S.right(0, 3) == 7);
147 
148     REQUIRE(S.left(0, 3) == 7);
149     REQUIRE(S.left(0, 3) == 7);
150 
151     word_type w;
152     S.minimal_factorisation(w, 378);
153     REQUIRE(w == word_type({0, 1, 2, 0, 1, 2}));
154     REQUIRE(S.length_const(378) == 6);
155 
156     REQUIRE(S.minimal_factorisation(S.at(378))
157             == word_type({0, 1, 2, 0, 1, 2}));
158 
159     REQUIRE_THROWS_AS(S.minimal_factorisation(BMat8({{1, 0, 0, 1, 1},
160                                                      {0, 1, 0, 0, 1},
161                                                      {1, 0, 1, 0, 1},
162                                                      {0, 0, 1, 0, 1},
163                                                      {0, 0, 0, 0, 0}})),
164                       LibsemigroupsException);
165 
166     REQUIRE_THROWS_AS(S.minimal_factorisation(1000000), LibsemigroupsException);
167 
168     w.clear();
169     S.factorisation(w, 378);
170     REQUIRE(w == word_type({0, 1, 2, 0, 1, 2}));
171     REQUIRE(S.length_const(378) == 6);
172 
173     REQUIRE(S.factorisation(S.at(378)) == word_type({0, 1, 2, 0, 1, 2}));
174 
175     REQUIRE_THROWS_AS(S.factorisation(BMat8({{1, 0, 0, 1, 1},
176                                              {0, 1, 0, 0, 1},
177                                              {1, 0, 1, 0, 1},
178                                              {0, 0, 1, 0, 1},
179                                              {0, 0, 0, 0, 0}})),
180                       LibsemigroupsException);
181 
182     REQUIRE_THROWS_AS(S.factorisation(1000000), LibsemigroupsException);
183 
184     S.next_relation(w);
185     REQUIRE(w == std::vector<size_t>({2, 2, 2}));
186     S.next_relation(w);
187     REQUIRE(w == std::vector<size_t>({3, 0, 7}));
188     S.next_relation(w);
189     REQUIRE(w == std::vector<size_t>({3, 2, 3}));
190 
191     size_t pos = 0;
192     for (auto it = S.cbegin(); it < S.cend(); ++it) {
193       REQUIRE(S.position(*it) == pos);
194       pos++;
195     }
196     REQUIRE(pos == S.size());
197 
198     // Copy - after run
199     FroidurePin<BMat8> T(S);
200     REQUIRE(T.size() == 63904);
201     REQUIRE(T.nr_idempotents() == 2360);
202     REQUIRE(T.word_to_pos({0, 1, 2, 0, 1, 2}) == 378);
203     REQUIRE(T.word_to_element({0, 1, 2, 0, 1, 2})
204             == BMat8({{1, 0, 0, 1}, {0, 1, 0, 0}, {1, 0, 1, 0}, {0, 0, 1, 0}}));
205     REQUIRE(T.current_max_word_length() == 21);
206     REQUIRE(T.degree() == 8);
207     REQUIRE(T.nr_generators() == 4);
208     REQUIRE(T.generator(0)
209             == BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}));
210     REQUIRE(T.generator(1)
211             == BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}));
212     REQUIRE(T.generator(2)
213             == BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}));
214     REQUIRE(T.generator(3)
215             == BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}}));
216     REQUIRE(T.finished());
217     REQUIRE(T.started());
218   }
219 #endif
220 
221   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
222                           "002",
223                           "(BMat8) exception zero generators given",
224                           "[quick][froidure-pin][bmat8]") {
225     std::vector<BMat8> gens;
226 
227     REQUIRE_THROWS_AS(FroidurePin<BMat8>(gens), LibsemigroupsException);
228   }
229 
230   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
231                           "003",
232                           "(BMat8) exception word_to_element",
233                           "[quick][froidure-pin][bmat8]") {
234     std::vector<BMat8> gens
235         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
236            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
237            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}),
238            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}})};
239     FroidurePin<BMat8> S(gens);
240 
241     REQUIRE_THROWS_AS(S.word_to_element({}), LibsemigroupsException);
242     REQUIRE_NOTHROW(S.word_to_element({0}));
243     REQUIRE_NOTHROW(S.word_to_element({0, 3, 0, 3, 1}));
244     REQUIRE_THROWS_AS(S.word_to_element({0, 1, 0, 4}), LibsemigroupsException);
245   }
246 
247   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
248                           "004",
249                           "(BMat8) exception prefix",
250                           "[quick][froidure-pin][bmat8]") {
251     std::vector<BMat8> gens
252         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
253            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
254            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
255     FroidurePin<BMat8> S(gens);
256 
257     for (size_t i = 0; i < S.size(); ++i) {
258       REQUIRE_NOTHROW(S.prefix(i));
259       REQUIRE_THROWS_AS(S.prefix(i + S.size()), LibsemigroupsException);
260     }
261   }
262 
263   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
264                           "005",
265                           "(BMat8) exception suffix",
266                           "[quick][froidure-pin][bmat8]") {
267     std::vector<BMat8> gens
268         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
269            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
270            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
271     FroidurePin<BMat8> S(gens);
272   }
273 
274   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
275                           "006",
276                           "(BMat8) exception first_letter",
277                           "[quick][froidure-pin][bmat8]") {
278     std::vector<BMat8> gens
279         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
280            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
281            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
282     FroidurePin<BMat8> S(gens);
283 
284     for (size_t i = 0; i < S.size(); ++i) {
285       REQUIRE_NOTHROW(S.first_letter(i));
286       REQUIRE_THROWS_AS(S.first_letter(i + S.size()), LibsemigroupsException);
287     }
288   }
289 
290   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
291                           "007",
292                           "(BMat8) exception final_letter",
293                           "[quick][froidure-pin][bmat8]") {
294     std::vector<BMat8> gens
295         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
296            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
297            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
298     FroidurePin<BMat8> S(gens);
299   }
300 
301   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
302                           "008",
303                           "(BMat8) exception length_const",
304                           "[quick][froidure-pin][bmat8]") {
305     std::vector<BMat8> gens
306         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
307            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
308            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
309     FroidurePin<BMat8> S(gens);
310 
311     for (size_t i = 0; i < S.size(); ++i) {
312       REQUIRE_NOTHROW(S.length_const(i));
313       REQUIRE_THROWS_AS(S.length_const(i + S.size()), LibsemigroupsException);
314     }
315   }
316 
317   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
318                           "009",
319                           "(BMat8) exception product_by_reduction",
320                           "[quick][froidure-pin][bmat8]") {
321     std::vector<BMat8> gens
322         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
323            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
324     FroidurePin<BMat8> S(gens);
325 
326     for (size_t i = 1; i < S.size(); ++i) {
327       for (size_t j = 1; j < S.size(); ++j) {
328         REQUIRE_NOTHROW(S.product_by_reduction(i, j));
329         REQUIRE_THROWS_AS(S.product_by_reduction(i + S.size(), j),
330                           LibsemigroupsException);
331         REQUIRE_THROWS_AS(S.product_by_reduction(i, j + S.size()),
332                           LibsemigroupsException);
333         REQUIRE_THROWS_AS(S.product_by_reduction(i + S.size(), j + S.size()),
334                           LibsemigroupsException);
335       }
336     }
337   }
338 
339   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
340                           "010",
341                           "(BMat8) exception fast_product",
342                           "[quick][froidure-pin][bmat8]") {
343     std::vector<BMat8> gens
344         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
345            BMat8({{1, 1, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 1}, {0, 1, 1, 1}})};
346     FroidurePin<BMat8> S(gens);
347 
348     for (size_t i = 1; i < S.size(); ++i) {
349       for (size_t j = 1; j < S.size(); ++j) {
350         REQUIRE_NOTHROW(S.fast_product(i, j));
351         REQUIRE_THROWS_AS(S.fast_product(i + S.size(), j),
352                           LibsemigroupsException);
353         REQUIRE_THROWS_AS(S.fast_product(i, j + S.size()),
354                           LibsemigroupsException);
355         REQUIRE_THROWS_AS(S.fast_product(i + S.size(), j + S.size()),
356                           LibsemigroupsException);
357       }
358     }
359   }
360 
361   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
362                           "011",
363                           "(BMat8) exception is_idempotent",
364                           "[quick][froidure-pin][bmat8][no-valgrind]") {
365     std::vector<BMat8> gens
366         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
367            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
368            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}),
369            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}})};
370     FroidurePin<BMat8> S(gens);
371 
372     // S has size 63904
373     for (size_t i = 0; i < 63904; ++i) {
374       REQUIRE_NOTHROW(S.is_idempotent(i));
375     }
376     for (size_t i = 0; i < 20; ++i) {
377       REQUIRE_THROWS_AS(S.is_idempotent(63904 + i), LibsemigroupsException);
378     }
379   }
380 
381   LIBSEMIGROUPS_TEST_CASE("FroidurePin",
382                           "012",
383                           "(BMat8) copy constructor",
384                           "[quick][froidure-pin][bmat8][no-valgrind]") {
385     auto               rg = ReportGuard(REPORT);
386     std::vector<BMat8> gens
387         = {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
388            BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
389            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}),
390            BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}})};
391     FroidurePin<BMat8> S(gens);
392     SECTION("fully enumerated") {
393       REQUIRE(S.size() == 63904);
394       FroidurePin<BMat8> T(S);  // copy
395       REQUIRE(T.size() == 63904);
396     }
397     SECTION("partially enumerated") {
398       S.enumerate(8192);
399       REQUIRE(!S.finished());
400       FroidurePin<BMat8> T(S);  // copy
401       REQUIRE(T.size() == 63904);
402     }
403     SECTION("not enumerated") {
404       FroidurePin<BMat8> T(S);  // copy
405       REQUIRE(T.size() == 63904);
406     }
407   }
408 
409   // LIBSEMIGROUPS_TEST_CASE("FroidurePin",
410   //                         "013",
411   //                         "(BMat8) find an element",
412   //                         "[quick][froidure-pin][bmat8]") {
413   //   FroidurePin<BMat8> S({BMat8({{0, 1, 0}, {1, 0, 0}, {0, 0, 1}}),
414   //                         BMat8({{0, 1, 0}, {0, 0, 1}, {1, 0, 0}}),
415   //                         BMat8({{1, 0, 0}, {0, 1, 0}, {1, 0, 1}}),
416   //                         BMat8({{1, 0, 0}, {0, 1, 0}, {0, 0, 0}}),
417   //                         BMat8({{1, 1, 0}, {1, 0, 1}, {0, 1, 1}})});
418   //   REQUIRE(S.size() == 512);
419   //   BMat8 y({{1, 1, 0}, {1, 0, 1}, {0, 0, 0}});
420   //   for (auto x : S) {
421   //     if (y.row_space_basis() == (y.row_space_basis() * x).row_space_basis())
422   //     {
423   //     }
424   //   }
425   // }
426 
427   //  LIBSEMIGROUPS_TEST_CASE("FroidurePin",
428   //                          "014",
429   //                          "(BMat8) find an element",
430   //                          "[quick][froidure-pin][bmat8]") {
431   //    FroidurePin<BMat8> S(
432   //        {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
433   //         BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
434   //         BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}),
435   //         BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}})});
436   //    S.run();
437   //    for (auto y : S) {
438   //         std::cout << y.row_space_basis() << std::endl;
439   //        for (auto x : S) {
440   //            if (y.row_space_basis() == (y.row_space_basis() *
441   //            x).row_space_basis()) {
442   //                auto p = y.right_perm_action_on_basis(x);
443   //                if (p == Permutation<uint8_t>({2,0,3,1,4,5,6,7}))
444   //                    std::cout << "++++" << std::endl
445   //                              << y << std::endl
446   //                              << x << std::endl;
447   //            }
448   //        }
449   //    }
450   //  }
451 
452   //  LIBSEMIGROUPS_TEST_CASE("FroidurePin",
453   //                          "015",
454   //                          "(BMat8) find an element",
455   //                          "[quick][froidure-pin][bmat8]") {
456   //    FroidurePin<BMat8> S({BMat8({{1, 0, 0, 0, 0},
457   //                                 {0, 1, 0, 0, 0},
458   //                                 {0, 0, 1, 0, 0},
459   //                                 {0, 0, 0, 1, 0},
460   //                                 {0, 0, 0, 0, 1}}),
461   //                          BMat8({{0, 1, 0, 0, 0},
462   //                                 {0, 0, 1, 0, 0},
463   //                                 {0, 0, 0, 1, 0},
464   //                                 {0, 0, 0, 0, 1},
465   //                                 {1, 0, 0, 0, 0}}),
466   //                          BMat8({{0, 1, 0, 0, 0},
467   //                                 {1, 0, 0, 0, 0},
468   //                                 {0, 0, 1, 0, 0},
469   //                                 {0, 0, 0, 1, 0},
470   //                                 {0, 0, 0, 0, 1}}),
471   //                          BMat8({{1, 0, 0, 0, 0},
472   //                                 {0, 1, 0, 0, 0},
473   //                                 {0, 0, 1, 0, 0},
474   //                                 {0, 0, 0, 1, 0},
475   //                                 {1, 0, 0, 0, 1}}),
476   //                          BMat8({{1, 1, 0, 0, 0},
477   //                                 {1, 0, 1, 0, 0},
478   //                                 {0, 1, 0, 1, 0},
479   //                                 {0, 0, 1, 1, 0},
480   //                                 {0, 0, 0, 0, 1}}),
481   //                          BMat8({{1, 1, 0, 0, 0},
482   //                                 {1, 0, 1, 0, 0},
483   //                                 {0, 1, 1, 0, 0},
484   //                                 {0, 0, 0, 1, 0},
485   //                                 {0, 0, 0, 0, 1}}),
486   //                          BMat8({{1, 1, 1, 0, 0},
487   //                                 {1, 0, 0, 1, 0},
488   //                                 {0, 1, 0, 1, 0},
489   //                                 {0, 0, 1, 1, 0},
490   //                                 {0, 0, 0, 0, 1}}),
491   //                          BMat8({{1, 1, 0, 0, 0},
492   //                                 {1, 0, 1, 0, 0},
493   //                                 {0, 1, 0, 1, 0},
494   //                                 {0, 0, 1, 0, 1},
495   //                                 {0, 0, 0, 1, 1}}),
496   //                          BMat8({{1, 1, 1, 1, 0},
497   //                                 {1, 0, 0, 0, 1},
498   //                                 {0, 1, 0, 0, 1},
499   //                                 {0, 0, 1, 0, 1},
500   //                                 {0, 0, 0, 1, 1}}),
501   //                          BMat8({{1, 0, 0, 0, 0},
502   //                                 {0, 1, 0, 0, 0},
503   //                                 {0, 0, 1, 0, 0},
504   //                                 {0, 0, 0, 1, 0},
505   //                                 {0, 0, 0, 0, 0}}),
506   //                          BMat8({{1, 1, 1, 0, 0},
507   //                                 {1, 0, 0, 1, 0},
508   //                                 {0, 1, 0, 1, 0},
509   //                                 {0, 0, 1, 0, 1},
510   //                                 {0, 0, 0, 1, 1}}),
511   //                          BMat8({{1, 1, 1, 0, 0},
512   //                                 {1, 0, 0, 1, 0},
513   //                                 {1, 0, 0, 0, 1},
514   //                                 {0, 1, 0, 1, 0},
515   //                                 {0, 0, 1, 0, 1}}),
516   //                          BMat8({{1, 1, 1, 0, 0},
517   //                                 {1, 0, 0, 1, 1},
518   //                                 {0, 1, 0, 1, 0},
519   //                                 {0, 1, 0, 0, 1},
520   //                                 {0, 0, 1, 1, 0}}),
521   //                          BMat8({{1, 1, 1, 0, 0},
522   //                                 {1, 1, 0, 1, 0},
523   //                                 {1, 0, 0, 0, 1},
524   //                                 {0, 1, 0, 0, 1},
525   //                                 {0, 0, 1, 1, 1}})});
526   //    auto               rg = ReportGuard();
527   //    S.enumerate(100000);
528   //    for (auto y : S) {
529   //      for (auto x : S) {
530   //        if (y.row_space_basis()
531   //            == (y.row_space_basis() * x).row_space_basis()) {
532   //          auto p = y.right_perm_action_on_basis(x);
533   //          if (p == Permutation<uint8_t>({2, 0, 3, 1, 4, 5, 6, 7})) {
534   //          }
535   //        }
536   //      }
537   //    }
538   //  }
539 
540 }  // namespace libsemigroups
541