| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/libsemigroups/tests/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.5.2025 mit Größe 209 kB |
|
Quelle test-schreier-sims.cpp Sprache: C |
|||||||||
|
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019 James D. Mitchell // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // These tests are derived from: // // https://github.com/james-d-mitchell/libsemigroups/pull/39 // // by Alex Levine and Luke Elliott. Many examples here taken from // // http://brauer.maths.qmul.ac.uk/Atlas/ #include <cstddef> // for size_t #include <cstdint> // for uint64_t #include "catch.hpp" // for LIBSEMIGROUPS_TEST_CASE #include "libsemigroups/config.hpp" // for LIBSEMIGROUPS_HPCOMBI_ENABLED #include "libsemigroups/report.hpp" // for ReportGuard #include "libsemigroups/schreier-sims.hpp" // for SchreierSims, SchreierSims<>::ele... #include "libsemigroups/transf.hpp" // for Perm #include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE namespace libsemigroups { struct LibsemigroupsException; constexpr bool REPORT = false; LIBSEMIGROUPS_TEST_CASE("SchreierSims", "001", "trivial perm. group (degree 1)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<1> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({0})); REQUIRE(S.size() == 1); REQUIRE(S.contains(Perm({0}))); // REQUIRE(!S.contains(Perm({1, 0}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "002", "trivial perm. group (degree 2)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<2> S; using Perm = SchreierSims<2>::element_type; S.add_generator(Perm({0, 1})); REQUIRE(S.size() == 1); REQUIRE(S.sift(Perm({1, 0})) == Perm({1, 0})); REQUIRE(!S.contains(Perm({1, 0}))); REQUIRE(S.contains(Perm({0, 1}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "003", "trivial perm. group (degree 500)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); size_t constexpr N = 100; // We allocate using "new" to avoid allocation on the stack, // since 100 is too large, and causes this test to seg fault. auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; auto p = Perm::identity(N); S->add_generator(p); REQUIRE(S->size() == 1); REQUIRE(S->contains(p)); std::swap(p[30], p[31]); REQUIRE(!S->contains(p)); std::swap(p[73], p[32]); REQUIRE(!S->contains(p)); std::swap(p[73], p[32]); std::swap(p[30], p[31]); std::swap(p[0], p[99]); REQUIRE(!S->contains(p)); delete S; } // The next tests fail (04 to 09, inclusive), with default template // parameters, due to HPCombi 0.0.3 currently composing functions from // right to left. LIBSEMIGROUPS_TEST_CASE("SchreierSims", "004", "symmetric perm. group (degree 5)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<5> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({1, 0, 2, 3, 4})); S.add_generator(Perm({1, 2, 3, 4, 0})); REQUIRE(S.size() == 120); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "005", "symmetric perm. group (degree 8)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<8> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({0, 6, 2, 3, 4, 5, 1, 7})); S.add_generator(Perm({1, 2, 3, 4, 5, 6, 7, 0})); REQUIRE(S.size() == 40320); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "006", "symmetric perm. group (degree 9)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<9> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({1, 0, 2, 3, 4, 5, 6, 7, 8})); S.add_generator(Perm({1, 2, 3, 4, 5, 6, 7, 8, 0})); REQUIRE(S.size() == 362880); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "007", "alternating perm. group (degree 12)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<12> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11})); S.add_generator(Perm({0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1})); REQUIRE(!S.contains(Perm({11, 10, 0, 6, 8, 2, 3, 5, 4, 7, 9, 1}))); REQUIRE(S.contains(Perm({7, 11, 2, 3, 0, 6, 9, 10, 8, 5, 4, 1}))); // REQUIRE(!S.contains(Perm({11, 10, 0, 6, 8, 2, 3, 5, 4, 7, 9, 1, 12}))); REQUIRE(S.size() == 239500800); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "008", "symmetric perm. group (degree 16)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<16> S; using Perm = decltype(S)::element_type; S.add_generator( Perm({1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15})); S.add_generator( Perm({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0})); REQUIRE(S.size() == static_cast<uint64_t>(20922789888000)); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "009", "alternating perm. group (degree 15)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<15> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14})); S.add_generator(Perm({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0})); REQUIRE(S.size() == static_cast<uint64_t>(653837184000)); REQUIRE( S.contains(Perm({0, 1, 7, 8, 9, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6}))); REQUIRE( S.contains(Perm({1, 12, 0, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}))); REQUIRE( S.contains(Perm({12, 0, 1, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}))); REQUIRE( !S.contains(Perm({12, 0, 1, 13, 14, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11}))); REQUIRE( !S.contains(Perm({1, 12, 0, 14, 13, 3, 2, 5, 4, 6, 7, 8, 9, 10, 11}))); REQUIRE( !S.contains(Perm({0, 1, 7, 9, 8, 11, 10, 12, 13, 14, 2, 3, 6, 5, 4}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "010", "alternating perm. group (degree 16)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<16> S; using Perm = decltype(S)::element_type; S.add_generator( Perm({1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15})); S.add_generator( Perm({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15})); S.add_generator( Perm({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13})); REQUIRE(S.size() == static_cast<uint64_t>(10461394944000)); REQUIRE(S.contains( Perm({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13}))); REQUIRE(!S.contains( Perm({1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13}))); REQUIRE(S.contains( Perm({1, 0, 3, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13}))); REQUIRE(S.contains( Perm({1, 2, 0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}))); REQUIRE(S.contains(S.generator(0))); REQUIRE(S.contains(S.generator(1))); REQUIRE(S.contains(S.generator(2))); REQUIRE(S.contains( Perm({0, 1, 7, 8, 9, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 15}))); REQUIRE(S.contains( Perm({1, 12, 0, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15}))); REQUIRE(S.contains( Perm({12, 0, 1, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15}))); REQUIRE(!S.contains( Perm({12, 0, 1, 13, 14, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11, 15}))); REQUIRE(!S.contains( Perm({1, 12, 0, 14, 13, 3, 2, 5, 4, 6, 7, 8, 9, 10, 11, 15}))); REQUIRE(!S.contains( Perm({0, 1, 7, 9, 8, 11, 10, 12, 13, 14, 2, 3, 6, 5, 4, 15}))); REQUIRE(!S.contains( Perm({1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13}))); S.add_generator( Perm({1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13})); REQUIRE(S.contains( Perm({1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "011", "dihedral perm. group (order 10)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<5> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({0, 4, 3, 2, 1})); S.add_generator(Perm({1, 2, 3, 4, 0})); REQUIRE(S.size() == 10); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "012", "dihedral perm. group (order 200)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); // At N = 4000 or so, this starts to take an appreciable amount of time. constexpr size_t N = 200; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; Perm::container_type cntnr; std::fill(cntnr.begin(), cntnr.end(), 0); std::iota(cntnr.begin(), cntnr.end() - 1, 1); S->add_generator(Perm(cntnr)); std::iota(cntnr.rbegin(), cntnr.rend() - 1, 1); cntnr[0] = 0; S->add_generator(Perm(cntnr)); REQUIRE(S->size() == 2 * N); REQUIRE(S->contains(S->generator(0))); REQUIRE(S->contains(S->generator(1))); REQUIRE(S->contains(S->generator(1) * S->generator(0))); std::iota(cntnr.begin(), cntnr.end(), 0); for (auto it = cntnr.begin(); it < cntnr.end(); it += 2) { std::swap(*it, *(it + 1)); } REQUIRE(!S->contains(Perm(cntnr))); std::swap(*cntnr.begin(), *(cntnr.begin() + 1)); REQUIRE(!S->contains(Perm(cntnr))); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "013", "perm. group T (order 12)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<12> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6})); S.add_generator(Perm({6, 11, 10, 9, 8, 7, 3, 2, 1, 0, 5, 4})); REQUIRE(S.size() == 12); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "014", "quaternion perm. group (order 8)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); SchreierSims<9> S; using Perm = decltype(S)::element_type; S.add_generator(Perm({0, 2, 4, 6, 7, 3, 8, 1, 5})); S.add_generator(Perm({0, 3, 5, 4, 8, 7, 2, 6, 1})); REQUIRE(S.generator(0) == Perm({0, 2, 4, 6, 7, 3, 8, 1, 5})); REQUIRE(S.size() == 8); REQUIRE(S.sift(S.generator(0)) == S.identity()); REQUIRE(S.contains(S.generator(0))); REQUIRE(S.contains(S.generator(1))); REQUIRE(S.contains(Perm({0, 6, 3, 7, 5, 1, 4, 8, 2}))); REQUIRE(S.contains(Perm({0, 8, 6, 1, 3, 2, 7, 5, 4}))); REQUIRE(!S.contains(Perm({0, 1, 5, 4, 8, 7, 2, 6, 3}))); REQUIRE(!S.contains(Perm({3, 5, 4, 6, 1, 8, 2, 7, 0}))); REQUIRE(!S.contains(Perm({1, 3, 2, 5, 7, 8, 6, 4, 0}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "015", "perm. group (order 84129611558952960)", "[quick][schreier-sims][no-valgrind]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 729; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator(Perm( {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 486, 487, 488, 489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546, 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 577, 578, 579, 580, 581, 582, 583, 584, 585, 586, 587, 588, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 630, 631, 632, 633, 634, 635, 636, 637, 638, 639, 640, 641, 642, 643, 644, 645, 646, 647, 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676, 677, 678, 679, 680, 681, 682, 683, 684, 685, 686, 687, 688, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698, 699, 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 717, 718, 719, 720, 721, 722, 723, 724, 725, 726, 727, 728, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480, 481, 482, 483, 484, 485})); S->add_generator(Perm( {0, 6, 3, 18, 24, 21, 9, 15, 12, 54, 60, 57, 72, 78, 75, 63, 69, 66, 27, 33, 30, 45, 51, 48, 36, 42, 39, 162, 168, 165, 180, 186, 183, 171, 177, 174, 216, 222, 219, 234, 240, 237, 225, 231, 228, 189, 195, 192, 207, 213, 210, 198, 204, 201, 81, 87, 84, 99, 105, 102, 90, 96, 93, 135, 141, 138, 153, 159, 156, 144, 150, 147, 108, 114, 111, 126, 132, 129, 117, 123, 120, 486, 492, 489, 504, 510, 507, 495, 501, 498, 540, 546, 543, 558, 564, 561, 549, 555, 552, 513, 519, 516, 531, 537, 534, 522, 528, 525, 648, 654, 651, 666, 672, 669, 657, 663, 660, 702, 708, 705, 720, 726, 723, 711, 717, 714, 675, 681, 678, 693, 699, 696, 684, 690, 687, 567, 573, 570, 585, 591, 588, 576, 582, 579, 621, 627, 624, 639, 645, 642, 630, 636, 633, 594, 600, 597, 612, 618, 615, 603, 609, 606, 243, 249, 246, 261, 267, 264, 252, 258, 255, 297, 303, 300, 315, 321, 318, 306, 312, 309, 270, 276, 273, 288, 294, 291, 279, 285, 282, 405, 411, 408, 423, 429, 426, 414, 420, 417, 459, 465, 462, 477, 483, 480, 468, 474, 471, 432, 438, 435, 450, 456, 453, 441, 447, 444, 324, 330, 327, 342, 348, 345, 333, 339, 336, 378, 384, 381, 396, 402, 399, 387, 393, 390, 351, 357, 354, 369, 375, 372, 360, 366, 363, 487, 493, 490, 505, 511, 508, 496, 502, 499, 541, 547, 544, 559, 565, 562, 550, 556, 553, 514, 520, 517, 532, 538, 535, 523, 529, 526, 649, 655, 652, 667, 673, 670, 658, 664, 661, 703, 709, 706, 721, 727, 724, 712, 718, 715, 676, 682, 679, 694, 700, 697, 685, 691, 688, 568, 574, 571, 586, 592, 589, 577, 583, 580, 622, 628, 625, 640, 646, 643, 631, 637, 634, 595, 601, 598, 613, 619, 616, 604, 610, 607, 244, 250, 247, 262, 268, 265, 253, 259, 256, 298, 304, 301, 316, 322, 319, 307, 313, 310, 271, 277, 274, 289, 295, 292, 280, 286, 283, 406, 412, 409, 424, 430, 427, 415, 421, 418, 460, 466, 463, 478, 484, 481, 469, 475, 472, 433, 439, 436, 451, 457, 454, 442, 448, 445, 325, 331, 328, 343, 349, 346, 334, 340, 337, 379, 385, 382, 397, 403, 400, 388, 394, 391, 352, 358, 355, 370, 376, 373, 361, 367, 364, 1, 7, 4, 19, 25, 22, 10, 16, 13, 55, 61, 58, 73, 79, 76, 64, 70, 67, 28, 34, 31, 46, 52, 49, 37, 43, 40, 163, 169, 166, 181, 187, 184, 172, 178, 175, 217, 223, 220, 235, 241, 238, 226, 232, 229, 190, 196, 193, 208, 214, 211, 199, 205, 202, 82, 88, 85, 100, 106, 103, 91, 97, 94, 136, 142, 139, 154, 160, 157, 145, 151, 148, 109, 115, 112, 127, 133, 130, 118, 124, 121, 245, 251, 248, 263, 269, 266, 254, 260, 257, 299, 305, 302, 317, 323, 320, 308, 314, 311, 272, 278, 275, 290, 296, 293, 281, 287, 284, 407, 413, 410, 425, 431, 428, 416, 422, 419, 461, 467, 464, 479, 485, 482, 470, 476, 473, 434, 440, 437, 452, 458, 455, 443, 449, 446, 326, 332, 329, 344, 350, 347, 335, 341, 338, 380, 386, 383, 398, 404, 401, 389, 395, 392, 353, 359, 356, 371, 377, 374, 362, 368, 365, 2, 8, 5, 20, 26, 23, 11, 17, 14, 56, 62, 59, 74, 80, 77, 65, 71, 68, 29, 35, 32, 47, 53, 50, 38, 44, 41, 164, 170, 167, 182, 188, 185, 173, 179, 176, 218, 224, 221, 236, 242, 239, 227, 233, 230, 191, 197, 194, 209, 215, 212, 200, 206, 203, 83, 89, 86, 101, 107, 104, 92, 98, 95, 137, 143, 140, 155, 161, 158, 146, 152, 149, 110, 116, 113, 128, 134, 131, 119, 125, 122, 488, 494, 491, 506, 512, 509, 497, 503, 500, 542, 548, 545, 560, 566, 563, 551, 557, 554, 515, 521, 518, 533, 539, 536, 524, 530, 527, 650, 656, 653, 668, 674, 671, 659, 665, 662, 704, 710, 707, 722, 728, 725, 713, 719, 716, 677, 683, 680, 695, 701, 698, 686, 692, 689, 569, 575, 572, 587, 593, 590, 578, 584, 581, 623, 629, 626, 641, 647, 644, 632, 638, 635, 596, 602, 599, 614, 620, 617, 605, 611, 608})); REQUIRE(S->size() == static_cast<uint64_t>(84129611558952960)); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "016", "perm. group SL(3, 5) (order 372000)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 126; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator( Perm({0, 1, 76, 101, 26, 51, 6, 81, 106, 31, 56, 11, 86, 111, 36, 61, 16, 91, 116, 41, 66, 21, 96, 121, 46, 71, 2, 77, 102, 27, 52, 7, 82, 107, 32, 57, 12, 87, 112, 37, 62, 17, 92, 117, 42, 67, 22, 97, 122, 47, 72, 3, 78, 103, 28, 53, 8, 83, 108, 33, 58, 13, 88, 113, 38, 63, 18, 93, 118, 43, 68, 23, 98, 123, 48, 73, 4, 79, 104, 29, 54, 9, 84, 109, 34, 59, 14, 89, 114, 39, 64, 19, 94, 119, 44, 69, 24, 99, 124, 49, 74, 5, 80, 105, 30, 55, 10, 85, 110, 35, 60, 15, 90, 115, 40, 65, 20, 95, 120, 45, 70, 25, 100, 125, 50, 75})); S->add_generator( Perm({0, 1, 77, 103, 29, 55, 6, 82, 108, 34, 60, 11, 87, 113, 39, 65, 16, 92, 118, 44, 70, 21, 97, 123, 49, 75, 2, 78, 105, 26, 54, 7, 83, 110, 31, 59, 12, 88, 115, 36, 64, 17, 93, 120, 41, 69, 22, 98, 125, 46, 74, 3, 80, 104, 27, 51, 8, 85, 109, 32, 56, 13, 90, 114, 37, 61, 18, 95, 119, 42, 66, 23, 100, 124, 47, 71, 4, 76, 102, 30, 53, 9, 81, 107, 35, 58, 14, 86, 112, 40, 63, 19, 91, 117, 45, 68, 24, 96, 122, 50, 73, 5, 79, 101, 28, 52, 10, 84, 106, 33, 57, 15, 89, 111, 38, 62, 20, 94, 116, 43, 67, 25, 99, 121, 48, 72})); S->add_generator( Perm({0, 1, 81, 111, 41, 71, 6, 86, 121, 26, 66, 11, 96, 116, 31, 51, 16, 76, 106, 46, 61, 21, 91, 101, 36, 56, 2, 82, 112, 42, 72, 7, 87, 122, 27, 67, 12, 97, 117, 32, 52, 17, 77, 107, 47, 62, 22, 92, 102, 37, 57, 3, 83, 113, 43, 73, 8, 88, 123, 28, 68, 13, 98, 118, 33, 53, 18, 78, 108, 48, 63, 23, 93, 103, 38, 58, 4, 84, 114, 44, 74, 9, 89, 124, 29, 69, 14, 99, 119, 34, 54, 19, 79, 109, 49, 64, 24, 94, 104, 39, 59, 5, 85, 115, 45, 75, 10, 90, 125, 30, 70, 15, 100, 120, 35, 55, 20, 80, 110, 50, 65, 25, 95, 105, 40, 60})); S->add_generator( Perm({0, 1, 76, 101, 26, 51, 7, 82, 107, 32, 57, 13, 88, 113, 38, 63, 19, 94, 119, 44, 69, 25, 100, 125, 50, 75, 2, 77, 102, 27, 52, 8, 83, 108, 33, 58, 15, 90, 115, 40, 65, 16, 91, 116, 41, 66, 24, 99, 124, 49, 74, 3, 78, 103, 28, 53, 10, 85, 110, 35, 60, 14, 89, 114, 39, 64, 17, 92, 117, 42, 67, 21, 96, 121, 46, 71, 4, 79, 104, 29, 54, 6, 81, 106, 31, 56, 12, 87, 112, 37, 62, 20, 95, 120, 45, 70, 23, 98, 123, 48, 73, 5, 80, 105, 30, 55, 9, 84, 109, 34, 59, 11, 86, 111, 36, 61, 18, 93, 118, 43, 68, 22, 97, 122, 47, 72})); REQUIRE(S->size() == 372000); REQUIRE(S->contains(S->generator(0))); REQUIRE(S->contains(S->generator(1))); REQUIRE(S->contains(S->generator(2))); REQUIRE(S->contains(S->generator(3))); REQUIRE(!S->contains( Perm({0, 1, 76, 101, 26, 51, 7, 82, 107, 32, 57, 13, 88, 113, 38, 63, 19, 94, 119, 44, 69, 25, 100, 125, 50, 75, 2, 77, 102, 27, 52, 8, 83, 108, 33, 58, 15, 90, 115, 40, 65, 16, 91, 116, 41, 66, 24, 99, 124, 49, 74, 3, 78, 103, 28, 53, 10, 85, 110, 35, 60, 14, 89, 114, 39, 64, 17, 92, 117, 42, 67, 21, 96, 121, 46, 71, 4, 79, 104, 29, 54, 6, 81, 106, 31, 56, 12, 87, 112, 37, 62, 20, 120, 95, 45, 70, 23, 98, 123, 48, 73, 5, 80, 105, 30, 55, 9, 84, 109, 34, 59, 11, 86, 111, 36, 61, 18, 93, 118, 43, 68, 22, 97, 122, 47, 72}))); REQUIRE(!S->contains( Perm({1, 77, 103, 109, 55, 6, 82, 108, 34, 60, 11, 87, 113, 39, 65, 16, 92, 118, 44, 70, 21, 97, 123, 49, 75, 2, 78, 105, 26, 54, 7, 83, 110, 31, 59, 12, 88, 115, 36, 64, 17, 93, 120, 41, 69, 22, 98, 125, 46, 74, 3, 80, 104, 27, 51, 8, 85, 29, 32, 56, 13, 90, 114, 37, 61, 18, 95, 119, 42, 66, 23, 100, 124, 47, 71, 4, 76, 0, 102, 30, 53, 9, 81, 107, 35, 58, 14, 86, 112, 40, 63, 19, 91, 117, 45, 68, 24, 96, 122, 50, 73, 5, 79, 101, 28, 52, 10, 84, 106, 33, 57, 15, 89, 111, 38, 62, 20, 94, 116, 43, 67, 25, 99, 121, 48, 72}))); REQUIRE(!S->contains(Perm( {0, 1, 80, 77, 103, 109, 55, 6, 82, 108, 34, 60, 11, 87, 113, 39, 65, 16, 92, 118, 44, 70, 21, 97, 123, 49, 75, 2, 78, 105, 26, 54, 7, 83, 110, 31, 59, 12, 88, 115, 36, 64, 17, 93, 120, 41, 69, 22, 98, 125, 46, 74, 3, 104, 27, 51, 8, 85, 29, 32, 56, 13, 90, 114, 37, 61, 18, 95, 119, 42, 66, 23, 100, 124, 47, 71, 4, 76, 102, 30, 53, 9, 81, 107, 35, 58, 14, 86, 112, 40, 63, 19, 91, 117, 45, 68, 24, 96, 122, 50, 73, 5, 79, 101, 28, 52, 10, 84, 106, 33, 57, 15, 89, 111, 38, 62, 20, 94, 116, 43, 67, 25, 99, 121, 48, 72}))); REQUIRE(S->contains( Perm({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 41, 42, 43, 44, 45, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 46, 47, 48, 49, 50, 36, 37, 38, 39, 40, 71, 72, 73, 74, 75, 66, 67, 68, 69, 70, 51, 52, 53, 54, 55, 61, 62, 63, 64, 65, 56, 57, 58, 59, 60, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 96, 97, 98, 99, 100, 76, 77, 78, 79, 80, 91, 92, 93, 94, 95, 111, 112, 113, 114, 115, 121, 122, 123, 124, 125, 116, 117, 118, 119, 120, 106, 107, 108, 109, 110, 101, 102, 103, 104, 105}))); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "017", "perm. group PSL(4, 8) (order 34558531338240)", "[quick][schreier-sims][no-valgrind]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 585; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator(Perm( {1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97, 105, 113, 121, 129, 137, 145, 153, 161, 169, 177, 185, 193, 201, 209, 217, 225, 233, 241, 249, 257, 265, 273, 281, 289, 297, 305, 313, 321, 329, 337, 345, 353, 361, 369, 377, 385, 393, 401, 409, 417, 425, 433, 441, 449, 457, 465, 473, 481, 489, 497, 505, 513, 521, 529, 537, 545, 553, 561, 569, 577, 74, 82, 90, 98, 106, 114, 122, 130, 138, 146, 154, 162, 170, 178, 186, 194, 202, 210, 218, 226, 234, 242, 250, 258, 266, 274, 282, 290, 298, 306, 314, 322, 330, 338, 346, 354, 362, 370, 378, 386, 394, 402, 410, 418, 426, 434, 442, 450, 458, 466, 474, 482, 490, 498, 506, 514, 522, 530, 538, 546, 554, 562, 570, 578, 0, 2, 8, 7, 6, 5, 4, 3, 10, 18, 26, 34, 42, 50, 58, 66, 16, 72, 24, 32, 40, 48, 56, 64, 15, 63, 71, 23, 31, 39, 47, 55, 14, 54, 62, 70, 22, 30, 38, 46, 13, 45, 53, 61, 69, 21, 29, 37, 12, 36, 44, 52, 60, 68, 20, 28, 11, 27, 35, 43, 51, 59, 67, 19, 78, 118, 126, 134, 86, 94, 102, 110, 398, 438, 446, 454, 406, 414, 422, 430, 462, 502, 510, 518, 470, 478, 486, 494, 526, 566, 574, 582, 534, 542, 550, 558, 142, 182, 190, 198, 150, 158, 166, 174, 206, 246, 254, 262, 214, 222, 230, 238, 270, 310, 318, 326, 278, 286, 294, 302, 334, 374, 382, 390, 342, 350, 358, 366, 75, 91, 99, 107, 115, 123, 131, 83, 203, 219, 227, 235, 243, 251, 259, 211, 267, 283, 291, 299, 307, 315, 323, 275, 331, 347, 355, 363, 371, 379, 387, 339, 395, 411, 419, 427, 435, 443, 451, 403, 459, 475, 483, 491, 499, 507, 515, 467, 523, 539, 547, 555, 563, 571, 579, 531, 139, 155, 163, 171, 179, 187, 195, 147, 80, 136, 88, 96, 104, 112, 120, 128, 528, 584, 536, 544, 552, 560, 568, 576, 144, 200, 152, 160, 168, 176, 184, 192, 208, 264, 216, 224, 232, 240, 248, 256, 272, 328, 280, 288, 296, 304, 312, 320, 336, 392, 344, 352, 360, 368, 376, 384, 400, 456, 408, 416, 424, 432, 440, 448, 464, 520, 472, 480, 488, 496, 504, 512, 76, 100, 108, 116, 124, 132, 84, 92, 268, 292, 300, 308, 316, 324, 276, 284, 332, 356, 364, 372, 380, 388, 340, 348, 396, 420, 428, 436, 444, 452, 404, 412, 460, 484, 492, 500, 508, 516, 468, 476, 524, 548, 556, 564, 572, 580, 532, 540, 140, 164, 172, 180, 188, 196, 148, 156, 204, 228, 236, 244, 252, 260, 212, 220, 77, 109, 117, 125, 133, 85, 93, 101, 333, 365, 373, 381, 389, 341, 349, 357, 397, 429, 437, 445, 453, 405, 413, 421, 461, 493, 501, 509, 517, 469, 477, 485, 525, 557, 565, 573, 581, 533, 541, 549, 141, 173, 181, 189, 197, 149, 157, 165, 205, 237, 245, 253, 261, 213, 221, 229, 269, 301, 309, 317, 325, 277, 285, 293, 79, 127, 135, 87, 95, 103, 111, 119, 463, 511, 519, 471, 479, 487, 495, 503, 527, 575, 583, 535, 543, 551, 559, 567, 143, 191, 199, 151, 159, 167, 175, 183, 207, 255, 263, 215, 223, 231, 239, 247, 271, 319, 327, 279, 287, 295, 303, 311, 335, 383, 391, 343, 351, 359, 367, 375, 399, 447, 455, 407, 415, 423, 431, 439})); S->add_generator(Perm( {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 10, 25, 27, 28, 29, 30, 31, 32, 26, 33, 35, 36, 37, 38, 39, 40, 34, 41, 43, 44, 45, 46, 47, 48, 42, 49, 51, 52, 53, 54, 55, 56, 50, 57, 59, 60, 61, 62, 63, 64, 58, 65, 67, 68, 69, 70, 71, 72, 66, 17, 19, 20, 21, 22, 23, 24, 18, 73, 80, 74, 75, 76, 77, 78, 79, 129, 136, 130, 131, 132, 133, 134, 135, 81, 88, 82, 83, 84, 85, 86, 87, 89, 96, 90, 91, 92, 93, 94, 95, 97, 104, 98, 99, 100, 101, 102, 103, 105, 112, 106, 107, 108, 109, 110, 111, 113, 120, 114, 115, 116, 117, 118, 119, 121, 128, 122, 123, 124, 125, 126, 127, 457, 464, 458, 459, 460, 461, 462, 463, 513, 520, 514, 515, 516, 517, 518, 519, 465, 472, 466, 467, 468, 469, 470, 471, 473, 480, 474, 475, 476, 477, 478, 479, 481, 488, 482, 483, 484, 485, 486, 487, 489, 496, 490, 491, 492, 493, 494, 495, 497, 504, 498, 499, 500, 501, 502, 503, 505, 512, 506, 507, 508, 509, 510, 511, 521, 528, 522, 523, 524, 525, 526, 527, 577, 584, 578, 579, 580, 581, 582, 583, 529, 536, 530, 531, 532, 533, 534, 535, 537, 544, 538, 539, 540, 541, 542, 543, 545, 552, 546, 547, 548, 549, 550, 551, 553, 560, 554, 555, 556, 557, 558, 559, 561, 568, 562, 563, 564, 565, 566, 567, 569, 576, 570, 571, 572, 573, 574, 575, 137, 144, 138, 139, 140, 141, 142, 143, 193, 200, 194, 195, 196, 197, 198, 199, 145, 152, 146, 147, 148, 149, 150, 151, 153, 160, 154, 155, 156, 157, 158, 159, 161, 168, 162, 163, 164, 165, 166, 167, 169, 176, 170, 171, 172, 173, 174, 175, 177, 184, 178, 179, 180, 181, 182, 183, 185, 192, 186, 187, 188, 189, 190, 191, 201, 208, 202, 203, 204, 205, 206, 207, 257, 264, 258, 259, 260, 261, 262, 263, 209, 216, 210, 211, 212, 213, 214, 215, 217, 224, 218, 219, 220, 221, 222, 223, 225, 232, 226, 227, 228, 229, 230, 231, 233, 240, 234, 235, 236, 237, 238, 239, 241, 248, 242, 243, 244, 245, 246, 247, 249, 256, 250, 251, 252, 253, 254, 255, 265, 272, 266, 267, 268, 269, 270, 271, 321, 328, 322, 323, 324, 325, 326, 327, 273, 280, 274, 275, 276, 277, 278, 279, 281, 288, 282, 283, 284, 285, 286, 287, 289, 296, 290, 291, 292, 293, 294, 295, 297, 304, 298, 299, 300, 301, 302, 303, 305, 312, 306, 307, 308, 309, 310, 311, 313, 320, 314, 315, 316, 317, 318, 319, 329, 336, 330, 331, 332, 333, 334, 335, 385, 392, 386, 387, 388, 389, 390, 391, 337, 344, 338, 339, 340, 341, 342, 343, 345, 352, 346, 347, 348, 349, 350, 351, 353, 360, 354, 355, 356, 357, 358, 359, 361, 368, 362, 363, 364, 365, 366, 367, 369, 376, 370, 371, 372, 373, 374, 375, 377, 384, 378, 379, 380, 381, 382, 383, 393, 400, 394, 395, 396, 397, 398, 399, 449, 456, 450, 451, 452, 453, 454, 455, 401, 408, 402, 403, 404, 405, 406, 407, 409, 416, 410, 411, 412, 413, 414, 415, 417, 424, 418, 419, 420, 421, 422, 423, 425, 432, 426, 427, 428, 429, 430, 431, 433, 440, 434, 435, 436, 437, 438, 439, 441, 448, 442, 443, 444, 445, 446, 447})); REQUIRE(S->size() == static_cast<uint64_t>(34558531338240)); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "018", "perm. Mathieu group M11 (order 7920)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 11; using Perm = Perm<0, size_t>; auto S = SchreierSims<N, size_t, Perm>(); S.add_generator(Perm({0, 9, 2, 10, 6, 5, 4, 8, 7, 1, 3})); S.add_generator(Perm({3, 4, 7, 2, 5, 8, 6, 0, 1, 9, 10})); REQUIRE(S.size() == 7920); REQUIRE(S.contains(S.generator(0))); REQUIRE(S.contains(S.generator(1))); REQUIRE(S.contains(Perm({10, 8, 5, 0, 1, 2, 4, 9, 7, 6, 3}))); REQUIRE(S.contains(Perm({3, 6, 0, 9, 4, 10, 7, 5, 2, 8, 1}))); REQUIRE(!S.contains(Perm({4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3}))); REQUIRE(!S.contains(Perm({6, 7, 8, 9, 10, 0, 2, 1, 3, 5, 4}))); REQUIRE(!S.contains(Perm({9, 10, 1, 2, 3, 4, 0, 5, 6, 7, 8}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "019", "perm. Mathieu group M24 (order 244823040)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 24; auto S = SchreierSims<N>(); using Perm = decltype(S)::element_type; S.add_generator(Perm({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 0, 23})); S.add_generator(Perm({0, 1, 16, 12, 3, 5, 8, 17, 2, 6, 11, 22, 13, 18, 19, 14, 9, 10, 4, 21, 15, 20, 7, 23})); S.add_generator(Perm({23, 22, 11, 15, 17, 9, 19, 13, 20, 5, 16, 2, 21, 7, 18, 3, 10, 4, 14, 6, 8, 12, 1, 0})); REQUIRE(S.size() == 244823040); REQUIRE(S.contains(S.generator(0))); REQUIRE(S.contains(S.generator(1))); REQUIRE(S.contains(Perm({1, 16, 12, 3, 5, 8, 17, 2, 6, 11, 22, 13, 18, 19, 14, 9, 10, 4, 21, 15, 20, 7, 0, 23}))); REQUIRE(S.contains(Perm({12, 16, 18, 10, 20, 14, 21, 6, 17, 3, 22, 8, 19, 4, 11, 5, 15, 7, 9, 13, 2, 23, 0, 1}))); REQUIRE(S.contains(Perm({19, 9, 21, 13, 10, 22, 6, 16, 7, 8, 11, 17, 12, 5, 15, 1, 14, 0, 4, 18, 20, 3, 23, 2}))); REQUIRE( !S.contains(Perm({0, 3, 2, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}))); REQUIRE( !S.contains(Perm({0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}))); REQUIRE( !S.contains(Perm({0, 1, 3, 4, 2, 6, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}))); } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "020", "perm. Janko Group J1 (order 175560)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 267; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator(Perm( {0, 262, 107, 21, 213, 191, 22, 133, 234, 232, 151, 139, 176, 202, 253, 222, 16, 195, 206, 68, 55, 3, 6, 179, 217, 216, 256, 87, 70, 131, 44, 105, 170, 77, 104, 198, 137, 243, 56, 124, 223, 134, 42, 174, 30, 45, 51, 128, 94, 250, 264, 46, 183, 231, 115, 20, 38, 85, 233, 261, 95, 235, 177, 249, 91, 247, 155, 67, 19, 219, 28, 237, 211, 84, 192, 130, 251, 33, 78, 260, 112, 193, 156, 242, 73, 57, 238, 27, 143, 168, 148, 64, 119, 212, 48, 60, 150, 199, 140, 189, 180, 147, 111, 159, 34, 31, 162, 2, 194, 166, 200, 102, 80, 120, 141, 54, 182, 181, 225, 92, 113, 254, 125, 146, 39, 122, 208, 221, 47, 210, 75, 29, 255, 7, 41, 135, 175, 36, 207, 11, 98, 114, 240, 88, 172, 185, 123, 101, 90, 224, 96, 10, 169, 241, 190, 66, 82, 214, 161, 103, 236, 158, 106, 239, 229, 230, 109, 188, 89, 152, 32, 258, 144, 186, 43, 136, 12, 62, 245, 23, 100, 117, 116, 52, 205, 145, 173, 228, 167, 99, 154, 5, 74, 81, 108, 17, 196, 203, 35, 97, 110, 252, 13, 197, 204, 184, 18, 138, 126, 248, 129, 72, 93, 4, 157, 259, 25, 24, 246, 69, 227, 127, 15, 40, 149, 118, 226, 220, 187, 164, 165, 53, 9, 58, 8, 61, 160, 71, 86, 163, 142, 153, 83, 37, 244, 178, 218, 65, 209, 63, 49, 76, 201, 14, 121, 132, 26, 263, 171, 215, 79, 59, 1, 257, 50, 266, 265})); S->add_generator(Perm( {0, 146, 132, 3, 156, 242, 107, 125, 245, 174, 241, 264, 248, 36, 116, 47, 178, 170, 197, 233, 121, 1, 228, 48, 201, 15, 136, 212, 6, 175, 77, 237, 30, 226, 31, 129, 44, 161, 232, 219, 78, 139, 9, 211, 13, 222, 97, 25, 173, 70, 153, 186, 29, 203, 35, 169, 140, 260, 91, 199, 108, 208, 206, 11, 55, 103, 65, 95, 73, 151, 131, 41, 221, 225, 18, 143, 7, 32, 159, 217, 93, 181, 2, 258, 163, 154, 182, 38, 133, 117, 33, 243, 191, 122, 27, 205, 20, 135, 98, 229, 138, 61, 194, 66, 104, 149, 62, 28, 164, 123, 17, 137, 16, 69, 37, 238, 128, 247, 57, 167, 134, 96, 80, 193, 185, 76, 83, 218, 14, 54, 8, 49, 82, 215, 189, 46, 190, 183, 188, 71, 230, 231, 239, 202, 224, 158, 21, 119, 214, 184, 250, 113, 72, 200, 213, 22, 166, 102, 220, 40, 92, 114, 257, 177, 60, 179, 4, 147, 168, 64, 110, 171, 148, 23, 42, 52, 195, 84, 112, 246, 19, 252, 196, 111, 105, 265, 209, 24, 100, 120, 26, 160, 39, 109, 157, 266, 86, 74, 204, 227, 50, 187, 75, 216, 207, 67, 106, 198, 101, 51, 141, 251, 94, 85, 172, 88, 53, 254, 261, 192, 145, 152, 240, 262, 249, 68, 90, 59, 155, 263, 56, 210, 87, 180, 12, 115, 142, 34, 235, 236, 45, 244, 253, 58, 10, 130, 165, 89, 234, 144, 259, 43, 81, 5, 79, 223, 162, 256, 126, 150, 118, 127, 255, 99, 63, 124, 176})); REQUIRE(S->size() == 175560); REQUIRE(S->contains(S->generator(0))); REQUIRE(S->contains(S->generator(1))); REQUIRE(S->contains(Perm( {0, 174, 56, 262, 210, 214, 81, 21, 160, 230, 148, 170, 67, 91, 126, 238, 25, 85, 260, 32, 16, 29, 181, 66, 248, 143, 167, 39, 241, 115, 98, 139, 226, 20, 12, 73, 152, 10, 141, 165, 121, 117, 169, 84, 11, 211, 112, 116, 234, 38, 131, 48, 219, 222, 68, 217, 9, 265, 188, 176, 74, 173, 69, 255, 163, 40, 77, 45, 264, 147, 225, 63, 33, 58, 212, 17, 51, 261, 3, 119, 59, 65, 6, 41, 103, 80, 231, 43, 184, 201, 151, 189, 47, 49, 42, 245, 124, 92, 206, 71, 123, 61, 259, 239, 105, 178, 113, 183, 96, 104, 111, 195, 199, 194, 192, 216, 83, 97, 64, 180, 94, 130, 8, 156, 134, 144, 246, 89, 110, 221, 82, 243, 190, 76, 154, 28, 120, 249, 114, 87, 23, 102, 150, 218, 34, 202, 57, 235, 127, 26, 253, 257, 258, 108, 205, 37, 132, 177, 208, 18, 191, 233, 54, 35, 182, 251, 55, 27, 247, 254, 19, 266, 44, 99, 5, 122, 186, 88, 60, 136, 24, 30, 242, 166, 50, 263, 75, 256, 118, 52, 187, 158, 53, 1, 237, 209, 240, 14, 4, 204, 140, 155, 90, 145, 146, 153, 86, 198, 175, 252, 236, 125, 109, 193, 223, 250, 227, 215, 72, 129, 93, 13, 15, 213, 7, 168, 172, 224, 128, 203, 244, 22, 200, 133, 161, 142, 171, 135, 138, 31, 2, 106, 197, 157, 196, 185, 164, 159, 137, 79, 107, 149, 228, 62, 179, 101, 100, 229, 162, 220, 70, 232, 95, 78, 36, 46, 207}))); REQUIRE(S->contains(Perm( {0, 56, 118, 229, 217, 125, 79, 100, 1, 259, 190, 122, 60, 260, 52, 206, 189, 71, 120, 23, 44, 160, 186, 148, 265, 170, 243, 195, 204, 151, 179, 202, 254, 161, 169, 201, 235, 96, 46, 200, 37, 90, 121, 54, 3, 212, 130, 248, 156, 143, 141, 246, 106, 146, 43, 234, 116, 171, 178, 105, 64, 20, 29, 164, 137, 113, 182, 209, 31, 163, 159, 227, 197, 262, 107, 66, 22, 59, 58, 244, 73, 230, 115, 2, 165, 152, 6, 240, 158, 167, 4, 264, 36, 255, 191, 101, 261, 192, 239, 62, 117, 231, 30, 17, 241, 14, 75, 144, 40, 147, 119, 132, 203, 174, 133, 136, 78, 16, 155, 18, 139, 95, 11, 68, 258, 228, 13, 8, 5, 177, 193, 124, 238, 50, 112, 70, 157, 218, 61, 224, 85, 55, 166, 104, 142, 97, 84, 232, 129, 74, 24, 266, 123, 215, 108, 49, 173, 87, 127, 126, 45, 28, 245, 249, 47, 69, 226, 21, 138, 196, 63, 57, 72, 91, 53, 111, 140, 48, 88, 149, 199, 187, 216, 222, 32, 172, 33, 253, 131, 225, 81, 256, 221, 237, 109, 211, 210, 250, 114, 183, 150, 15, 236, 154, 181, 39, 25, 214, 134, 207, 175, 220, 251, 145, 180, 233, 77, 7, 94, 80, 162, 213, 247, 67, 103, 41, 102, 110, 27, 184, 38, 185, 205, 198, 153, 99, 252, 242, 26, 83, 219, 98, 10, 34, 263, 128, 12, 223, 35, 65, 42, 93, 176, 76, 168, 257, 51, 89, 135, 92, 188, 208, 82, 86, 19, 194, 9}))); REQUIRE(S->contains(Perm( {0, 201, 243, 31, 229, 136, 122, 223, 164, 155, 185, 45, 3, 81, 166, 48, 14, 105, 162, 169, 228, 94, 212, 43, 167, 190, 93, 202, 224, 55, 56, 29, 118, 116, 194, 161, 184, 39, 134, 22, 181, 66, 8, 216, 112, 110, 58, 183, 131, 156, 103, 244, 144, 203, 5, 59, 9, 231, 108, 238, 52, 111, 255, 178, 226, 23, 92, 82, 173, 51, 145, 26, 146, 138, 196, 143, 163, 37, 249, 246, 53, 191, 117, 245, 200, 4, 30, 106, 247, 32, 192, 263, 49, 142, 171, 34, 188, 151, 65, 260, 36, 6, 68, 259, 265, 123, 20, 73, 193, 63, 258, 100, 2, 41, 16, 7, 124, 132, 230, 86, 135, 113, 83, 17, 149, 33, 256, 84, 42, 128, 180, 236, 47, 187, 11, 74, 253, 61, 67, 209, 211, 70, 237, 198, 25, 266, 130, 182, 125, 213, 250, 257, 141, 199, 147, 13, 175, 102, 91, 27, 205, 75, 222, 242, 153, 206, 76, 88, 1, 140, 96, 18, 69, 85, 189, 10, 50, 208, 227, 21, 139, 165, 40, 87, 35, 204, 179, 99, 158, 176, 79, 251, 38, 109, 57, 89, 221, 90, 24, 219, 252, 214, 159, 157, 239, 262, 129, 121, 160, 232, 80, 97, 77, 60, 54, 44, 177, 195, 19, 154, 28, 225, 114, 62, 240, 248, 150, 120, 126, 133, 168, 119, 218, 64, 172, 217, 197, 98, 170, 78, 174, 15, 186, 101, 220, 115, 254, 137, 46, 207, 261, 95, 152, 235, 148, 215, 107, 72, 264, 234, 210, 127, 71, 104, 241, 12, 233}))); REQUIRE(!S->contains(Perm( {0, 250, 199, 41, 146, 23, 54, 53, 254, 33, 40, 80, 184, 78, 34, 92, 102, 263, 45, 195, 153, 106, 58, 192, 127, 93, 209, 70, 126, 143, 152, 166, 85, 87, 112, 49, 222, 159, 42, 210, 238, 150, 191, 239, 52, 179, 174, 55, 75, 51, 142, 165, 1, 81, 56, 9, 198, 225, 64, 197, 234, 38, 178, 132, 183, 226, 265, 202, 241, 129, 26, 36, 116, 103, 28, 90, 252, 57, 119, 67, 171, 211, 161, 60, 94, 18, 180, 134, 236, 136, 131, 176, 201, 66, 167, 182, 124, 137, 220, 181, 262, 50, 27, 256, 135, 74, 113, 245, 118, 91, 160, 109, 186, 97, 215, 105, 20, 175, 24, 149, 71, 17, 144, 125, 207, 43, 59, 224, 242, 235, 82, 189, 84, 13, 227, 156, 120, 7, 208, 139, 117, 257, 2, 30, 35, 244, 6, 114, 217, 72, 44, 63, 89, 145, 31, 266, 76, 121, 204, 240, 115, 163, 98, 264, 233, 260, 162, 65, 219, 253, 194, 151, 111, 123, 5, 39, 46, 212, 99, 108, 16, 22, 138, 83, 104, 148, 69, 203, 187, 157, 206, 3, 246, 29, 243, 232, 101, 168, 229, 221, 140, 213, 231, 47, 228, 188, 100, 248, 185, 128, 200, 88, 155, 122, 14, 107, 95, 73, 77, 110, 169, 79, 193, 32, 223, 249, 11, 205, 173, 190, 251, 196, 10, 218, 62, 37, 21, 86, 147, 258, 214, 130, 237, 164, 133, 19, 172, 247, 177, 255, 12, 158, 48, 261, 259, 170, 216, 154, 230, 96, 15, 141, 4, 61, 25, 68, 8}))); REQUIRE(!S->contains(Perm( {0, 89, 18, 6, 159, 73, 100, 91, 110, 216, 66, 56, 144, 22, 62, 15, 23, 146, 188, 11, 245, 148, 86, 96, 156, 114, 221, 103, 217, 7, 129, 26, 111, 51, 232, 12, 141, 243, 212, 167, 225, 219, 177, 34, 104, 64, 54, 255, 165, 250, 136, 202, 227, 20, 246, 124, 134, 65, 84, 61, 77, 97, 162, 259, 247, 263, 215, 139, 150, 48, 196, 181, 106, 187, 95, 44, 2, 33, 5, 260, 19, 127, 195, 69, 58, 75, 142, 32, 203, 224, 45, 251, 4, 99, 88, 233, 184, 189, 173, 85, 163, 249, 16, 43, 93, 27, 264, 140, 208, 166, 101, 39, 211, 14, 206, 192, 230, 107, 87, 63, 102, 204, 205, 70, 115, 145, 8, 3, 198, 182, 24, 153, 168, 174, 200, 154, 55, 40, 53, 59, 125, 30, 112, 38, 265, 236, 223, 242, 262, 76, 190, 133, 28, 194, 183, 213, 130, 60, 257, 123, 171, 253, 234, 149, 94, 109, 83, 118, 256, 126, 176, 164, 31, 228, 151, 42, 261, 201, 226, 248, 244, 78, 258, 220, 120, 178, 239, 71, 90, 67, 119, 197, 50, 199, 143, 175, 92, 52, 29, 9, 80, 82, 157, 160, 147, 240, 49, 122, 191, 170, 252, 13, 131, 209, 161, 254, 266, 74, 113, 41, 179, 116, 21, 185, 1, 137, 17, 108, 214, 193, 172, 238, 105, 152, 218, 47, 117, 25, 222, 35, 79, 180, 210, 138, 46, 37, 241, 81, 135, 169, 237, 128, 121, 98, 158, 132, 235, 10, 36, 68, 207, 155, 231, 72, 57, 186, 229}))); REQUIRE(!S->contains(Perm( {0, 56, 118, 229, 217, 125, 79, 100, 1, 259, 190, 122, 60, 260, 52, 206, 189, 71, 120, 23, 44, 160, 186, 148, 265, 170, 243, 195, 204, 151, 179, 202, 254, 161, 169, 201, 235, 96, 46, 200, 37, 90, 121, 54, 4, 212, 130, 248, 156, 143, 141, 246, 106, 146, 43, 234, 116, 171, 178, 105, 64, 20, 29, 164, 137, 113, 182, 209, 31, 163, 159, 227, 197, 262, 107, 66, 22, 59, 58, 244, 73, 230, 115, 3, 165, 152, 2, 240, 158, 167, 5, 264, 36, 255, 191, 101, 261, 192, 239, 62, 117, 231, 30, 17, 241, 14, 75, 144, 40, 147, 119, 132, 203, 174, 133, 136, 78, 16, 155, 18, 139, 95, 11, 68, 258, 228, 13, 8, 6, 177, 193, 124, 238, 50, 112, 70, 157, 218, 61, 224, 85, 55, 166, 104, 142, 97, 84, 232, 129, 74, 24, 266, 123, 215, 108, 49, 173, 87, 127, 126, 45, 28, 245, 249, 47, 69, 226, 21, 138, 196, 63, 57, 72, 91, 53, 111, 140, 48, 88, 149, 199, 187, 216, 222, 32, 172, 33, 253, 131, 225, 81, 256, 221, 237, 109, 211, 210, 250, 114, 183, 150, 15, 236, 154, 181, 39, 25, 214, 134, 207, 175, 220, 251, 145, 180, 233, 77, 7, 94, 80, 162, 213, 247, 67, 103, 41, 102, 110, 27, 184, 38, 185, 205, 198, 153, 99, 252, 242, 26, 83, 219, 98, 10, 34, 263, 128, 12, 223, 35, 65, 42, 93, 176, 76, 168, 257, 51, 89, 135, 92, 188, 208, 82, 86, 19, 194, 9}))); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "021", "perm. Hall-Janko group (order 604800)", "[quick][schreier-sims]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 101; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator(Perm( {0, 84, 20, 48, 56, 82, 67, 55, 41, 35, 40, 78, 100, 49, 37, 94, 76, 19, 44, 17, 2, 34, 85, 92, 57, 75, 28, 64, 26, 90, 97, 38, 68, 69, 21, 9, 53, 14, 31, 61, 10, 8, 73, 91, 18, 86, 81, 89, 3, 13, 93, 96, 72, 36, 74, 7, 4, 24, 99, 95, 63, 39, 83, 60, 27, 70, 88, 6, 32, 33, 65, 87, 52, 42, 54, 25, 16, 98, 11, 80, 79, 46, 5, 62, 1, 22, 45, 71, 66, 47, 29, 43, 23, 50, 15, 59, 51, 30, 77, 58, 12})); S->add_generator(Perm( {0, 80, 9, 53, 23, 51, 37, 7, 27, 11, 62, 2, 65, 64, 61, 98, 73, 39, 5, 13, 97, 96, 1, 78, 6, 15, 93, 60, 57, 71, 69, 12, 16, 17, 86, 28, 36, 24, 59, 33, 43, 41, 68, 91, 42, 30, 85, 10, 76, 92, 66, 18, 14, 87, 95, 29, 54, 35, 20, 94, 8, 52, 47, 74, 19, 31, 88, 21, 44, 45, 81, 55, 63, 32, 72, 70, 90, 49, 4, 100, 22, 75, 34, 79, 84, 89, 82, 3, 50, 46, 48, 40, 77, 99, 38, 56, 67, 58, 25, 26, 83})); REQUIRE(S->size() == 604800); REQUIRE(S->contains(S->generator(0))); REQUIRE(S->contains(S->generator(1))); REQUIRE(S->contains(Perm( {0, 22, 11, 87, 78, 18, 24, 7, 60, 2, 47, 9, 31, 19, 52, 25, 32, 33, 51, 64, 58, 67, 80, 4, 37, 98, 99, 8, 35, 55, 45, 65, 73, 39, 82, 57, 36, 6, 94, 17, 91, 41, 44, 40, 68, 69, 89, 62, 90, 77, 88, 5, 61, 3, 56, 71, 95, 28, 97, 38, 27, 14, 10, 72, 13, 12, 50, 96, 42, 30, 75, 29, 74, 16, 63, 81, 48, 92, 23, 83, 1, 70, 86, 100, 84, 46, 34, 53, 66, 85, 76, 43, 49, 26, 59, 54, 21, 20, 15, 93, 79}))); REQUIRE(S->contains(Perm( {0, 59, 20, 76, 38, 35, 13, 73, 45, 94, 84, 82, 10, 14, 58, 39, 68, 95, 37, 54, 52, 16, 89, 26, 51, 81, 50, 23, 18, 71, 60, 43, 7, 25, 9, 88, 48, 97, 2, 96, 46, 92, 53, 62, 32, 66, 80, 40, 5, 28, 57, 90, 93, 29, 70, 55, 33, 77, 6, 78, 74, 19, 31, 12, 24, 72, 99, 17, 30, 42, 100, 3, 27, 67, 21, 98, 36, 41, 8, 15, 79, 56, 34, 75, 47, 91, 86, 44, 69, 49, 87, 65, 85, 4, 22, 64, 63, 11, 83, 61, 1}))); REQUIRE(S->contains(Perm( {0, 74, 78, 68, 70, 20, 98, 18, 21, 75, 85, 44, 43, 67, 50, 37, 42, 31, 72, 60, 54, 3, 83, 9, 34, 47, 28, 13, 32, 36, 52, 91, 87, 46, 24, 93, 71, 86, 99, 82, 65, 56, 53, 12, 73, 88, 62, 89, 45, 58, 14, 7, 66, 16, 100, 55, 97, 94, 51, 35, 4, 69, 15, 80, 26, 39, 30, 27, 2, 76, 38, 29, 49, 57, 5, 23, 48, 63, 8, 95, 84, 11, 6, 77, 22, 10, 33, 96, 61, 17, 90, 25, 79, 59, 81, 41, 64, 92, 40, 19, 1}))); REQUIRE(!S->contains(Perm( {0, 2, 1, 4, 3, 5, 6, 8, 9, 10, 7, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100}))); REQUIRE(!S->contains(Perm( {0, 3, 100, 4, 8, 5, 6, 7, 1, 33, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 89, 27, 28, 29, 30, 31, 32, 2, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 93, 83, 84, 85, 86, 87, 88, 82, 90, 91, 92, 26, 94, 95, 96, 97, 98, 99, 9}))); REQUIRE(!S->contains(Perm( {0, 5, 3, 1, 4, 100, 6, 7, 23, 9, 19, 11, 12, 13, 14, 15, 16, 17, 18, 8, 20, 21, 22, 45, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 10, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 2, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 83}))); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "022", "perm. Hall-Janko group (alt.) (order 604800)", "[quick][schreier-sims][no-valgrind]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 841; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator(Perm( {0, 2, 1, 5, 7, 3, 10, 4, 12, 13, 6, 16, 8, 9, 20, 21, 11, 24, 25, 27, 14, 15, 31, 32, 17, 18, 36, 19, 38, 39, 41, 22, 23, 45, 46, 48, 26, 51, 28, 29, 55, 30, 57, 58, 59, 33, 34, 63, 35, 65, 66, 37, 67, 68, 70, 40, 73, 42, 43, 44, 77, 78, 80, 47, 83, 49, 50, 52, 53, 89, 54, 91, 72, 56, 92, 93, 95, 60, 61, 99, 62, 101, 102, 64, 103, 104, 106, 108, 110, 69, 113, 71, 74, 75, 118, 76, 120, 121, 123, 79, 126, 81, 82, 84, 85, 132, 86, 134, 87, 136, 88, 138, 139, 90, 140, 141, 142, 144, 94, 147, 96, 97, 151, 98, 153, 154, 100, 155, 156, 158, 160, 162, 105, 165, 107, 168, 109, 171, 111, 112, 114, 115, 116, 177, 117, 179, 180, 119, 181, 182, 184, 122, 187, 124, 125, 127, 128, 193, 129, 195, 130, 197, 131, 199, 200, 133, 201, 202, 135, 205, 206, 137, 207, 208, 210, 212, 214, 143, 217, 145, 146, 148, 149, 223, 150, 224, 186, 152, 225, 226, 228, 230, 192, 157, 234, 159, 237, 161, 240, 163, 164, 166, 167, 204, 203, 169, 170, 172, 173, 251, 174, 253, 175, 255, 176, 257, 258, 178, 259, 260, 262, 264, 266, 183, 185, 188, 189, 272, 190, 274, 191, 276, 277, 278, 194, 279, 280, 196, 283, 284, 198, 285, 286, 288, 290, 292, 294, 295, 297, 250, 249, 209, 302, 211, 305, 213, 308, 215, 216, 218, 219, 314, 220, 316, 221, 318, 222, 320, 321, 322, 323, 325, 227, 328, 229, 331, 231, 232, 233, 235, 236, 282, 281, 238, 239, 241, 242, 342, 243, 344, 244, 345, 245, 347, 246, 247, 350, 248, 298, 352, 353, 354, 252, 355, 356, 254, 359, 360, 256, 361, 362, 364, 366, 368, 261, 371, 263, 374, 265, 377, 267, 268, 269, 270, 382, 271, 384, 385, 273, 386, 387, 275, 390, 391, 392, 335, 395, 397, 398, 400, 402, 379, 287, 406, 289, 291, 409, 293, 412, 414, 296, 407, 299, 300, 301, 303, 304, 358, 357, 306, 307, 309, 310, 422, 311, 423, 312, 425, 313, 427, 428, 315, 429, 430, 317, 433, 434, 319, 435, 341, 437, 439, 324, 442, 326, 327, 329, 330, 389, 388, 332, 333, 334, 450, 451, 336, 417, 337, 338, 454, 339, 456, 340, 458, 459, 460, 343, 351, 461, 346, 410, 462, 348, 465, 349, 467, 469, 396, 471, 473, 420, 476, 363, 365, 480, 367, 483, 369, 370, 372, 373, 432, 431, 375, 376, 378, 493, 380, 495, 381, 497, 498, 383, 444, 443, 501, 503, 504, 506, 507, 393, 394, 511, 470, 399, 487, 401, 516, 403, 404, 405, 408, 411, 523, 524, 413, 527, 415, 530, 416, 453, 418, 533, 419, 535, 536, 421, 538, 539, 540, 424, 543, 544, 426, 545, 546, 548, 455, 488, 513, 550, 532, 509, 436, 518, 438, 556, 440, 441, 560, 500, 445, 561, 446, 447, 564, 448, 449, 566, 492, 567, 452, 552, 489, 568, 569, 457, 572, 494, 573, 575, 577, 578, 463, 464, 581, 582, 466, 583, 576, 468, 586, 491, 472, 590, 474, 475, 594, 477, 478, 479, 542, 541, 481, 482, 484, 485, 604, 486, 606, 490, 608, 512, 609, 610, 611, 496, 612, 613, 615, 499, 502, 617, 619, 505, 622, 508, 510, 514, 515, 571, 570, 517, 519, 629, 520, 529, 521, 522, 632, 633, 525, 526, 528, 637, 638, 531, 607, 639, 640, 534, 641, 642, 643, 537, 644, 645, 647, 649, 651, 602, 653, 600, 656, 547, 659, 549, 587, 551, 553, 554, 555, 557, 558, 668, 559, 669, 562, 672, 563, 636, 674, 565, 675, 676, 678, 661, 681, 682, 574, 685, 687, 579, 580, 691, 693, 620, 584, 585, 588, 589, 591, 592, 593, 595, 596, 699, 597, 701, 598, 684, 599, 704, 601, 706, 707, 603, 709, 710, 605, 711, 626, 662, 703, 712, 714, 697, 717, 614, 616, 721, 722, 618, 725, 621, 623, 624, 728, 625, 679, 729, 627, 628, 732, 650, 630, 686, 631, 733, 724, 735, 634, 737, 635, 739, 740, 742, 666, 745, 646, 720, 648, 749, 663, 652, 751, 654, 655, 727, 657, 658, 660, 664, 713, 665, 756, 757, 667, 759, 760, 700, 670, 671, 762, 689, 673, 763, 708, 677, 680, 765, 767, 683, 688, 770, 690, 772, 692, 774, 694, 695, 776, 696, 778, 779, 698, 781, 782, 775, 702, 783, 705, 752, 784, 755, 754, 715, 716, 786, 718, 719, 789, 723, 726, 773, 730, 793, 731, 795, 796, 734, 798, 736, 764, 738, 748, 741, 801, 743, 744, 803, 746, 747, 750, 753, 806, 758, 808, 809, 761, 805, 812, 813, 766, 816, 768, 769, 819, 771, 820, 821, 777, 807, 780, 814, 790, 785, 802, 787, 788, 822, 825, 791, 792, 804, 827, 794, 828, 829, 797, 799, 800, 810, 830, 833, 811, 834, 815, 817, 818, 823, 832, 831, 824, 826, 835, 839, 837, 840, 836, 838})); S->add_generator(Perm( {0, 3, 4, 6, 8, 9, 1, 11, 2, 14, 15, 17, 18, 19, 5, 22, 23, 7, 26, 28, 29, 30, 10, 33, 34, 35, 12, 37, 13, 40, 42, 43, 44, 16, 47, 49, 50, 52, 53, 54, 20, 56, 21, 59, 60, 61, 62, 24, 64, 25, 51, 36, 27, 69, 71, 72, 74, 75, 76, 31, 32, 79, 81, 82, 84, 85, 86, 87, 88, 38, 90, 39, 73, 55, 41, 94, 96, 97, 98, 45, 100, 46, 83, 63, 48, 105, 107, 109, 111, 112, 114, 115, 116, 117, 57, 119, 58, 122, 124, 125, 127, 128, 129, 130, 131, 65, 133, 66, 135, 67, 137, 68, 113, 89, 70, 142, 143, 145, 146, 148, 149, 150, 77, 152, 78, 126, 99, 80, 157, 159, 161, 163, 164, 166, 167, 169, 170, 172, 173, 174, 175, 176, 91, 92, 178, 93, 147, 118, 95, 183, 185, 186, 188, 189, 190, 191, 192, 101, 194, 102, 196, 103, 198, 104, 165, 132, 106, 203, 204, 108, 171, 136, 110, 209, 211, 213, 215, 216, 218, 219, 220, 221, 222, 120, 223, 121, 187, 151, 123, 227, 229, 231, 232, 233, 235, 236, 238, 239, 241, 242, 243, 244, 245, 134, 246, 247, 248, 249, 250, 138, 252, 139, 254, 140, 256, 141, 217, 177, 144, 261, 263, 265, 267, 268, 269, 270, 271, 153, 273, 154, 275, 155, 156, 234, 193, 158, 281, 282, 160, 240, 197, 162, 287, 289, 291, 293, 168, 296, 298, 299, 300, 301, 303, 304, 306, 307, 309, 310, 311, 312, 313, 179, 315, 180, 317, 181, 319, 182, 184, 323, 324, 326, 327, 329, 330, 332, 333, 276, 334, 335, 336, 195, 337, 338, 339, 340, 341, 199, 343, 200, 295, 201, 346, 202, 348, 349, 205, 351, 206, 207, 208, 302, 251, 210, 357, 358, 212, 308, 255, 214, 363, 365, 367, 369, 370, 372, 373, 375, 376, 378, 379, 380, 381, 224, 225, 383, 226, 328, 272, 228, 388, 389, 230, 277, 393, 394, 396, 237, 399, 401, 403, 404, 405, 354, 407, 408, 410, 411, 413, 290, 344, 353, 352, 297, 288, 415, 416, 253, 417, 418, 419, 420, 421, 257, 422, 258, 424, 259, 426, 260, 371, 314, 262, 431, 432, 264, 377, 318, 266, 436, 438, 440, 441, 386, 443, 444, 325, 445, 274, 446, 447, 448, 449, 278, 279, 452, 280, 453, 430, 283, 455, 284, 457, 285, 286, 406, 342, 350, 409, 345, 292, 463, 464, 294, 466, 468, 470, 305, 472, 474, 475, 477, 478, 479, 481, 482, 484, 485, 486, 487, 488, 316, 489, 490, 491, 492, 320, 494, 321, 496, 322, 442, 382, 499, 500, 502, 331, 505, 507, 508, 509, 510, 512, 513, 429, 514, 515, 517, 518, 519, 520, 521, 522, 347, 525, 526, 528, 529, 355, 531, 356, 532, 359, 534, 360, 361, 537, 362, 364, 541, 542, 366, 483, 425, 368, 547, 549, 454, 398, 374, 551, 552, 553, 458, 554, 555, 557, 558, 559, 384, 385, 498, 387, 562, 563, 390, 565, 391, 392, 567, 511, 451, 395, 397, 400, 570, 571, 402, 493, 574, 576, 578, 579, 580, 523, 412, 527, 465, 414, 584, 585, 587, 588, 589, 591, 592, 593, 595, 596, 597, 598, 423, 599, 600, 601, 602, 603, 427, 605, 428, 607, 433, 434, 435, 437, 556, 495, 439, 614, 501, 560, 616, 618, 620, 621, 623, 624, 450, 625, 626, 456, 627, 628, 609, 459, 630, 460, 631, 461, 462, 524, 634, 635, 636, 467, 586, 530, 469, 471, 590, 533, 473, 643, 594, 536, 476, 646, 648, 650, 480, 652, 654, 655, 657, 658, 660, 661, 640, 662, 663, 664, 665, 666, 667, 497, 668, 670, 671, 503, 673, 504, 622, 564, 506, 677, 679, 680, 516, 683, 684, 686, 688, 689, 690, 692, 674, 687, 649, 694, 608, 550, 695, 696, 535, 697, 698, 538, 700, 539, 702, 540, 703, 543, 705, 544, 545, 708, 546, 659, 604, 548, 678, 639, 573, 713, 715, 716, 718, 719, 720, 561, 723, 724, 726, 582, 710, 727, 566, 606, 568, 569, 730, 731, 572, 685, 629, 575, 583, 577, 734, 736, 735, 581, 738, 740, 741, 743, 744, 746, 669, 747, 748, 637, 728, 750, 752, 753, 676, 754, 709, 755, 693, 732, 610, 712, 611, 612, 758, 613, 615, 699, 761, 721, 617, 725, 672, 619, 707, 651, 764, 766, 768, 714, 769, 632, 771, 633, 773, 711, 775, 638, 641, 777, 642, 644, 780, 645, 647, 749, 701, 751, 704, 653, 783, 656, 675, 785, 778, 787, 742, 788, 722, 790, 733, 791, 792, 681, 794, 682, 763, 797, 691, 772, 774, 737, 799, 800, 759, 786, 802, 804, 805, 760, 706, 784, 807, 757, 717, 782, 810, 811, 729, 814, 815, 817, 818, 796, 798, 770, 739, 801, 776, 803, 779, 745, 822, 823, 756, 808, 821, 824, 762, 826, 812, 765, 816, 793, 767, 830, 825, 831, 832, 781, 827, 789, 834, 813, 806, 835, 836, 795, 837, 809, 833, 819, 838, 840, 820, 828, 839, 829})); REQUIRE(S->size() == 604800); delete S; } LIBSEMIGROUPS_TEST_CASE("SchreierSims", "023", "perm. Conway group Co3 (order 495766656000)", "[quick][schreier-sims][no-valgrind]") { auto rg = ReportGuard(REPORT); constexpr size_t N = 277; auto S = new SchreierSims<N>(); using Perm = std::remove_pointer<decltype(S)>::type::element_type; S->add_generator(Perm( {0, 245, 42, 112, 15, 131, 7, 188, 75, 132, 10, 11, 187, 186, 265, 22, 159, 256, 43, 101, 123, 134, 4, 32, 209, 238, 35, 45, 235, 126, 5, 19, 60, 66, 80, 154, 251, 117, 206, 71, 118, 93, --> -------------------- --> maximum size reached --> -------------------- ¤ Dauer der Verarbeitung: 0.13 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28