HPCombi
High Performance Combinatorics in C++ using vector instructions v1.0.2
Loading...
Searching...
No Matches
perm16.hpp
Go to the documentation of this file.
1//****************************************************************************//
2// Copyright (C) 2016-2024 Florent Hivert <Florent.Hivert@lisn.fr>, //
3// //
4// This file is part of HP-Combi <https://github.com/libsemigroups/HPCombi> //
5// //
6// HP-Combi is free software: you can redistribute it and/or modify it //
7// under the terms of the GNU General Public License as published by the //
8// Free Software Foundation, either version 3 of the License, or //
9// (at your option) any later version. //
10// //
11// HP-Combi is distributed in the hope that it will be useful, but WITHOUT //
12// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or //
13// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License //
14// for more details. //
15// //
16// You should have received a copy of the GNU General Public License along //
17// with HP-Combi. If not, see <https://www.gnu.org/licenses/>. //
18//****************************************************************************//
19
28#ifndef HPCOMBI_PERM16_HPP_
29#define HPCOMBI_PERM16_HPP_
30
31#include <cstddef> // for size_t
32#include <cstdint> // for uint8_t, uint64_t, uint32_t
33#include <initializer_list> // for initializer_list
34#include <memory> // for hash
35#include <type_traits> // for is_trivial
36#include <vector> // for vector
37
38#include "epu8.hpp" // for epu8, permuted, etc
39#include "power.hpp" // for pow
40#include "vect16.hpp" // for hash, is_partial_permutation
41
42#if defined(__GNUC__) && !defined(__clang__)
43#pragma GCC diagnostic push
44#pragma GCC diagnostic ignored "-Wswitch-default"
45#pragma GCC diagnostic ignored "-Wpacked"
46#endif
47#include "simde/x86/sse4.1.h"
48#include "simde/x86/sse4.2.h"
49#if defined(__GNUC__) && !defined(__clang__)
50#pragma GCC diagnostic pop
51#endif
52
53namespace HPCombi {
54
55// Forward declaration
56struct Perm16;
57struct PTransf16;
58struct Transf16;
59
63struct alignas(16) PTransf16 : public Vect16 {
64 static constexpr size_t size() { return 16; }
65
67 using array = typename decltype(Epu8)::array;
68
69 PTransf16() = default;
70
71 constexpr PTransf16(const vect vv) : Vect16(vv) {}
72 constexpr PTransf16(const epu8 x) : Vect16(x) {}
73 PTransf16(std::vector<uint8_t> dom, std::vector<uint8_t> rng,
74 size_t = 0 /* unused */);
75 PTransf16(std::initializer_list<uint8_t> il);
76
78 bool validate(size_t k = 16) const {
80 }
81
83 static constexpr PTransf16 one() { return Epu8.id(); }
85 PTransf16 operator*(const PTransf16 &p) const {
86 return HPCombi::permuted(v, p.v) | (p.v == Epu8(0xFF));
87 }
88
90 epu8 image_mask_cmpestrm(bool complement = false) const;
92 epu8 image_mask_ref(bool complement = false) const;
93 epu8 image_mask(bool complement = false) const {
94#ifdef SIMDE_X86_SSE4_2_NATIVE
95 return image_mask_cmpestrm(complement);
96#else
97 return image_mask_ref(complement);
98#endif
99 }
101 uint32_t image_bitset(bool complement = false) const;
103 epu8 domain_mask(bool complement = false) const;
105 uint32_t domain_bitset(bool complement = false) const;
106
108 PTransf16 right_one() const;
110 PTransf16 left_one() const;
111
113 uint32_t rank_ref() const;
115 uint32_t rank() const;
117 uint32_t rank_cmpestrm() const;
118
120 epu8 fix_points_mask(bool complement = false) const;
122 uint32_t fix_points_bitset(bool complement = false) const;
124 uint8_t smallest_fix_point() const;
126 uint8_t smallest_moved_point() const;
128 uint8_t largest_fix_point() const;
130 uint8_t largest_moved_point() const;
132 uint8_t nb_fix_points() const;
133};
134
139struct Transf16 : public PTransf16 {
140 Transf16() = default;
141 constexpr Transf16(const Transf16 &vv) = default;
142 /* implicit */ constexpr Transf16(const vect vv) // NOLINT
143 : PTransf16(vv) {}
144 /* implicit */ constexpr Transf16(const epu8 x) : PTransf16(x) {} // NOLINT
145 Transf16(std::initializer_list<uint8_t> il) : PTransf16(il) {}
146 Transf16 &operator=(const Transf16 &) = default;
147
149 bool validate(size_t k = 16) const {
150 return HPCombi::is_transformation(v, k);
151 }
152
154 static constexpr Transf16 one() { return Epu8.id(); }
156 Transf16 operator*(const Transf16 &p) const {
157 return HPCombi::permuted(v, p.v);
158 }
159
161 explicit Transf16(uint64_t compressed);
163 explicit operator uint64_t() const;
164};
165
169struct PPerm16 : public PTransf16 {
170 PPerm16() = default;
171 constexpr PPerm16(const PPerm16 &vv) = default;
172 /* implicit */ constexpr PPerm16(const vect vv) // NOLINT
173 : PTransf16(vv) {}
174 /* implicit */ constexpr PPerm16(const epu8 x) : PTransf16(x) {} // NOLINT
175 PPerm16(std::vector<uint8_t> dom, std::vector<uint8_t> rng,
176 size_t = 0 /* unused */)
177 : PTransf16(dom, rng) {}
178 PPerm16(std::initializer_list<uint8_t> il) : PTransf16(il) {}
179 PPerm16 &operator=(const PPerm16 &) = default;
180
182 bool validate(size_t k = 16) const {
184 }
185
187 static constexpr PPerm16 one() { return Epu8.id(); }
189 PPerm16 operator*(const PPerm16 &p) const {
190 return this->PTransf16::operator*(p);
191 }
192
210 PPerm16 inverse_ref() const;
211
212#ifdef SIMDE_X86_SSE4_2_NATIVE
219 PPerm16 inverse_find() const;
220#endif
221
224};
225
230struct Perm16 : public Transf16 /* public PPerm : diamond problem */ {
231 Perm16() = default;
232 constexpr Perm16(const Perm16 &) = default;
233 /* implicit */ constexpr Perm16(const vect vv) : Transf16(vv) {} // NOLINT
234 /* implicit */ constexpr Perm16(const epu8 x) : Transf16(x) {} // NOLINT
235 Perm16 &operator=(const Perm16 &) = default;
236 Perm16(std::initializer_list<uint8_t> il) : Transf16(il) {}
237
239 bool validate(size_t k = 16) const { return HPCombi::is_permutation(v, k); }
240
241 // It's not possible to have a static constexpr member of same type as class
242 // being defined (see https://stackoverflow.com/questions/11928089/)
243 // therefore we chose to have functions.
245 static constexpr Perm16 one() { return Epu8.id(); }
247 Perm16 operator*(const Perm16 &p) const {
248 return HPCombi::permuted(v, p.v);
249 }
250
252 explicit Perm16(uint64_t compressed) : Transf16(compressed) {}
253
267 Perm16 inverse() const { return inverse_cycl(); }
268
274 Perm16 inverse_ref() const;
275
281 Perm16 inverse_arr() const;
282
290 Perm16 inverse_sort() const;
291
298 Perm16 inverse_find() const { return permutation_of(v, one()); }
299
308 Perm16 inverse_pow() const;
309
316 Perm16 inverse_cycl() const;
317
319 static Perm16 elementary_transposition(uint64_t i);
321 static Perm16 random(uint64_t n = 16);
325 static Perm16 unrankSJT(int n, int r);
326
341 epu8 lehmer() const;
342
348 epu8 lehmer_ref() const;
349
355 epu8 lehmer_arr() const;
356
370 uint8_t length() const;
371
377 uint8_t length_ref() const;
378
385 uint8_t length_arr() const;
386
400 uint8_t nb_descents() const;
401
407 uint8_t nb_descents_ref() const;
408
423 epu8 cycles_partition() const;
424
437 uint8_t nb_cycles() const { return nb_cycles_unroll(); }
438
444 uint8_t nb_cycles_ref() const;
445
451 uint8_t nb_cycles_unroll() const;
452
464 bool left_weak_leq(Perm16 other) const;
465
471 bool left_weak_leq_ref(Perm16 other) const;
472
478 bool left_weak_leq_length(Perm16 other) const;
479};
480
484
485static_assert(sizeof(epu8) == sizeof(Perm16),
486 "epu8 and Perm16 have a different memory layout !");
487static_assert(std::is_trivial<epu8>(), "epu8 is not a trivial class !");
488static_assert(std::is_trivial<Perm16>(), "Perm16 is not a trivial class !");
489
490} // namespace HPCombi
491
492#include "perm16_impl.hpp"
493
494namespace std {
495// Hash operators for Transf and Perm:
496
499template <> struct hash<HPCombi::PTransf16> {
501 size_t operator()(const HPCombi::PTransf16 &ar) const {
502 return std::hash<HPCombi::epu8>{}(ar.v);
503 }
504};
505
508template <> struct hash<HPCombi::Transf16> {
510 size_t operator()(const HPCombi::Transf16 &ar) const {
511 return static_cast<uint64_t>(ar);
512 }
513};
514
517template <> struct hash<HPCombi::PPerm16> {
519 size_t operator()(const HPCombi::PPerm16 &ar) const {
520 return std::hash<HPCombi::epu8>{}(ar.v);
521 }
522};
523
526template <> struct hash<HPCombi::Perm16> {
528 size_t operator()(const HPCombi::Perm16 &ar) const {
529 return static_cast<uint64_t>(ar);
530 }
531};
532
533} // namespace std
534
535#endif // HPCOMBI_PERM16_HPP_
declaration of HPCombi::epu8.
Perm16 Perm16
Definition perm16_impl.hpp:239
Definition bmat8.hpp:42
epu8 permuted(epu8 a, epu8 b) noexcept
Same as permuted_ref but with an optimized implementation using intrinsics.
Definition epu8.hpp:96
epu8 permutation_of(epu8 a, epu8 b) noexcept
Find if a vector is a permutation of another one.
Definition epu8_impl.hpp:304
bool is_permutation(epu8 v, const size_t k=16) noexcept
Definition epu8_impl.hpp:531
bool is_partial_permutation(epu8 v, const size_t k=16) noexcept
Test for partial permutations.
Definition epu8_impl.hpp:500
constexpr TPUBuild< epu8 > Epu8
Factory object acting as a class constructor for type HPCombi::epu8.
Definition epu8.hpp:74
uint8_t __attribute__((vector_size(16))) epu8
epu8 stands for Extended Packed Unsigned, grouped by 8 bits; this is the low level type chosen by Int...
Definition epu8.hpp:66
bool is_transformation(epu8 v, const size_t k=16) noexcept
Test for transformation.
Definition epu8_impl.hpp:494
bool is_partial_transformation(epu8 v, const size_t k=16) noexcept
Test for partial transformation.
Definition epu8_impl.hpp:486
Definition bmat8.hpp:367
implementation of perm16.hpp ; this file should not be included directly.
Generic compile-time unrolling of the fast exponentiation algorithm.
Partial permutation of ; see also HPCombi::Perm16; partial means it might not be defined everywhere (...
Definition perm16.hpp:169
PPerm16 right_one() const
Definition perm16.hpp:222
PPerm16 inverse_ref() const
The inverse of a partial permutation.
Definition perm16_impl.hpp:145
PPerm16 operator*(const PPerm16 &p) const
The product of two partial perrmutations.
Definition perm16.hpp:189
PPerm16()=default
PPerm16 & operator=(const PPerm16 &)=default
constexpr PPerm16(const PPerm16 &vv)=default
PPerm16(std::vector< uint8_t > dom, std::vector< uint8_t > rng, size_t=0)
Definition perm16.hpp:175
constexpr PPerm16(const vect vv)
Definition perm16.hpp:172
static constexpr PPerm16 one()
The identity partial permutations.
Definition perm16.hpp:187
PPerm16 left_one() const
Definition perm16.hpp:223
PPerm16(std::initializer_list< uint8_t > il)
Definition perm16.hpp:178
bool validate(size_t k=16) const
Return whether *this is a well constructed object.
Definition perm16.hpp:182
constexpr PPerm16(const epu8 x)
Definition perm16.hpp:174
Partial transformation of ; see HPCombi::Transf16; partial means it might not be defined everywhere.
Definition perm16.hpp:63
uint8_t nb_fix_points() const
Returns the number of fix points of *this.
Definition perm16_impl.hpp:120
constexpr PTransf16(const epu8 x)
Definition perm16.hpp:72
uint32_t fix_points_bitset(bool complement=false) const
Returns a bit mask for the fix point of *this.
Definition perm16_impl.hpp:98
static constexpr size_t size()
Definition perm16.hpp:64
PTransf16 operator*(const PTransf16 &p) const
The product of two partial transformations.
Definition perm16.hpp:85
static constexpr PTransf16 one()
The identity partial transformation.
Definition perm16.hpp:83
uint8_t largest_moved_point() const
Returns the largest non fix point of *this.
Definition perm16_impl.hpp:115
uint32_t domain_bitset(bool complement=false) const
Returns a bit mask for the domain of *this.
Definition perm16_impl.hpp:47
PTransf16 left_one() const
Returns the partial left identity for *this.
Definition perm16_impl.hpp:71
typename decltype(Epu8)::array array
Definition perm16.hpp:67
uint32_t rank_ref() const
Returns the size of the image of *this.
Definition perm16_impl.hpp:74
PTransf16 right_one() const
Returns the partial right identity for *this.
Definition perm16_impl.hpp:50
uint32_t image_bitset(bool complement=false) const
Returns a bit mask for the image of *this.
Definition perm16_impl.hpp:68
epu8 fix_points_mask(bool complement=false) const
Returns a mask for the fix point of *this.
Definition perm16_impl.hpp:95
constexpr PTransf16(const vect vv)
Definition perm16.hpp:71
uint8_t smallest_fix_point() const
Returns the smallest fix point of *this.
Definition perm16_impl.hpp:102
uint32_t rank_cmpestrm() const
Returns the size of the image of *this.
Definition perm16_impl.hpp:83
epu8 domain_mask(bool complement=false) const
Returns a mask for the domain of *this.
Definition perm16_impl.hpp:44
uint32_t rank() const
Returns the size of the image of *this.
Definition perm16_impl.hpp:87
epu8 image_mask_ref(bool complement=false) const
Returns a mask for the image of *this.
Definition perm16_impl.hpp:60
bool validate(size_t k=16) const
Return whether *this is a well constructed object.
Definition perm16.hpp:78
uint8_t largest_fix_point() const
Returns the largest fix point of *this.
Definition perm16_impl.hpp:110
epu8 image_mask(bool complement=false) const
Definition perm16.hpp:93
epu8 image_mask_cmpestrm(bool complement=false) const
Returns a mask for the image of *this.
uint8_t smallest_moved_point() const
Returns the smallest non fix point of *this.
Definition perm16_impl.hpp:106
Permutations of : A permutation is a bijective mapping of a set of n elements onto itself.
Definition perm16.hpp:230
Perm16 inverse_cycl() const
Same as inverse but with a different algorithm.
Definition perm16_impl.hpp:248
Perm16 inverse() const
The inverse permutation.
Definition perm16.hpp:267
epu8 lehmer() const
The Lehmer code of a permutation.
Definition perm16_impl.hpp:289
uint8_t length_ref() const
Same interface as length, with a different implementation.
Definition perm16_impl.hpp:298
epu8 cycles_partition() const
The set partition of the cycles of a permutation.
Definition perm16_impl.hpp:343
bool left_weak_leq_ref(Perm16 other) const
Same interface as left_weak_leq but with a different implementation.
Definition perm16_impl.hpp:361
uint8_t nb_descents_ref() const
Same interface as nb_descents, with a different implementation.
Definition perm16_impl.hpp:319
Perm16(uint64_t compressed)
Construct a permutations from its 64 bits compressed.
Definition perm16.hpp:252
Perm16 inverse_sort() const
Same as inverse but with a different algorithm.
Definition perm16_impl.hpp:224
Perm16 operator*(const Perm16 &p) const
The product of two permutations.
Definition perm16.hpp:247
Perm16(std::initializer_list< uint8_t > il)
Definition perm16.hpp:236
constexpr Perm16(const epu8 x)
Definition perm16.hpp:234
Perm16 inverse_find() const
Same as inverse but with a different algorithm.
Definition perm16.hpp:298
static constexpr Perm16 one()
The identity partial permutation.
Definition perm16.hpp:245
epu8 lehmer_ref() const
Same interface as lehmer but with a different implementation.
Definition perm16_impl.hpp:270
bool left_weak_leq_length(Perm16 other) const
Same interface as left_weak_leq but with a different implementation.
Definition perm16_impl.hpp:384
uint8_t length() const
The Coxeter length (ie: number of inversion) of a permutation.
Definition perm16_impl.hpp:317
constexpr Perm16(const Perm16 &)=default
Perm16 inverse_ref() const
Same as inverse but with a different algorithm.
Definition perm16_impl.hpp:208
uint8_t nb_descents() const
The number of descent of a permutation.
Definition perm16_impl.hpp:326
uint8_t nb_cycles() const
The number of cycles of a permutation.
Definition perm16.hpp:437
uint8_t nb_cycles_ref() const
Same interface as nb_cycles but with a different implementation.
Definition perm16_impl.hpp:330
bool validate(size_t k=16) const
Return whether *this is a well constructed object.
Definition perm16.hpp:239
static Perm16 elementary_transposition(uint64_t i)
The elementary transposition exchanging and .
Definition perm16_impl.hpp:200
epu8 lehmer_arr() const
Same interface as lehmer but with a different implementation.
Definition perm16_impl.hpp:279
static Perm16 unrankSJT(int n, int r)
The r -th permutation of size n for the Steinhaus–Johnson–Trotter order.
Definition perm16_impl.hpp:172
constexpr Perm16(const vect vv)
Definition perm16.hpp:233
bool left_weak_leq(Perm16 other) const
Compare two permutations for the left weak order.
Definition perm16_impl.hpp:371
uint8_t nb_cycles_unroll() const
Same interface as nb_cycles but with a different implementation.
Definition perm16_impl.hpp:356
Perm16 & operator=(const Perm16 &)=default
Perm16()=default
Perm16 inverse_pow() const
Same as inverse but with a different algorithm.
Definition perm16_impl.hpp:266
uint8_t length_arr() const
Same interface as length, with a different implementation.
Definition perm16_impl.hpp:307
Perm16 inverse_arr() const
Same as inverse but with a different algorithm.
Definition perm16_impl.hpp:215
static Perm16 random(uint64_t n=16)
A random permutation of size .
Definition perm16_impl.hpp:160
Full transformation of : a transformation is a mapping of a set of n elements into itself; ie as oppo...
Definition perm16.hpp:139
Transf16 operator*(const Transf16 &p) const
The product of two transformations.
Definition perm16.hpp:156
Transf16(std::initializer_list< uint8_t > il)
Definition perm16.hpp:145
constexpr Transf16(const epu8 x)
Definition perm16.hpp:144
Transf16 & operator=(const Transf16 &)=default
constexpr Transf16(const vect vv)
Definition perm16.hpp:142
Transf16()=default
bool validate(size_t k=16) const
Return whether *this is a well constructed object.
Definition perm16.hpp:149
constexpr Transf16(const Transf16 &vv)=default
static constexpr Transf16 one()
The identity transformation.
Definition perm16.hpp:154
Vector of 16 bytes, with some optimized methods, superclass of HPCombi::Transf16.
Definition vect16.hpp:39
epu8 v
Definition vect16.hpp:42
size_t operator()(const HPCombi::PPerm16 &ar) const
A hash operator for HPCombi::PPerm16.
Definition perm16.hpp:519
size_t operator()(const HPCombi::PTransf16 &ar) const
A hash operator for HPCombi::PTransf16.
Definition perm16.hpp:501
size_t operator()(const HPCombi::Perm16 &ar) const
A hash operator for HPCombi::Perm16.
Definition perm16.hpp:528
size_t operator()(const HPCombi::Transf16 &ar) const
A hash operator for HPCombi::Transf16.
Definition perm16.hpp:510
HPCombi::Vect16.