 |
Cayley
Pseudo-Random Bits from Finite Groups
|
|
Cayley
Pseudo-Random Bits from Finite Groups
|
Permutation. More...
#include <Permutation.h>
Public Member Functions | |
| CPerm (uint8_t n) | |
| Constructor. More... | |
| CPerm (uint8_t n, uintx_t m) | |
| Constructor. More... | |
| CPerm (uint8_t n, uint8_t init[]) | |
| Constructor. More... | |
| CPerm (const CPerm &p) | |
| Copy constructor. More... | |
| ~CPerm () | |
| Destructor. More... | |
| void | Randomize (uint64_t(*rng)(void)) |
| Set to random permutation. More... | |
| void | RandomizeOdd (uint64_t(*rng)(void)) |
| Set to random odd permutation. More... | |
| void | Randomize (uint32_t s[]) |
| Set to random permutation. More... | |
| uint8_t | GetSize () const |
| Get size. More... | |
| bool | IsIdentity () const |
| Identity permutation test. More... | |
| void | printmap () const |
| Print as a map. More... | |
| void | printnum () const |
| Print reverse lexicographic number. More... | |
| template<class uint > | |
| uint | GetNum () const |
| Get reverse lexicographic number. More... | |
| uint8_t | operator[] (uint8_t n) const |
| Get nth element of map. More... | |
| CPerm & | operator= (const CPerm &p) |
| Assignment operator. More... | |
| const CPerm & | operator *= (const CPerm &p) |
| Permutation composition. More... | |
Public Attributes | |
| std::vector< uint8_t > | m_vecCycle |
| Cycle notation. | |
Private Attributes | |
| uint8_t * | m_nMap |
| Permutation sends i to m_nMap[i]. | |
| uint8_t | m_nSize |
| Number of things being permuted. | |
Friends | |
| bool | operator== (const CPerm &p0, const CPerm &p1) |
| Equality test. More... | |
A permutation that can be created from an array, from a reverse lexicographic number or pseudorandomly using a PRNG. Functionality includes permutation composition and calculating its reverse lexicographic number. Permutations can have size at most 256 since it uses a table of 8-bit unsigned integers in order to improve caching by decreasing its memory footprint.
Definition at line 20 of file Permutation.h.
| CPerm::CPerm | ( | uint8_t | n | ) |
Construct the identity permutation, that is, the permutation that maps everything to itself.
| n | Size of permutation. |
Definition at line 17 of file Permutation.cpp.
| CPerm::CPerm | ( | uint8_t | n, |
| uintx_t | m | ||
| ) |
Use the method of Hall and Knuth, "Combinatorial analysis and computers", The American Mathematical Monthly 72(2):21-28, 1965, to construct a permutation from its reverse lexicographic number using mixed-radix arithmetic. This is the inverse of operator uintx_t().
| n | Size of permutation. |
| m | Reverse lexicographic number of permutation. |
Definition at line 31 of file Permutation.cpp.
| CPerm::CPerm | ( | uint8_t | n, |
| uint8_t | init[] | ||
| ) |
Construct a permutation from a permutation table. It is assumed that the permutation table has the right size and does indeed describe a permutation.
| n | Size of permutation. |
| init | Permutation table. |
Definition at line 76 of file Permutation.cpp.
| CPerm::CPerm | ( | const CPerm & | p | ) |
Construct a deep copy of a permutation.
| p | The permutation to copy from. |
Definition at line 84 of file Permutation.cpp.
| CPerm::~CPerm | ( | ) |
The destructor.
Definition at line 91 of file Permutation.cpp.
| template uint8_t CPerm::GetNum< uint8_t > | ( | ) | const |
Use the method of Hall and Knuth, "Combinatorial analysis and computers", The American Mathematical Monthly 72(2):21-28, 1965, to compute the index of the permutation in reverse lexicographic order using mixed-radix arithmetic. This is the inverse of the constructor CPerm(int, uintx_t).
| uint | An unsigned integer type. |
Definition at line 273 of file Permutation.cpp.
| uint8_t CPerm::GetSize | ( | ) | const |
Reader function for the size of the permutation, that is, the number of elements being permuted.
Definition at line 159 of file Permutation.cpp.
| bool CPerm::IsIdentity | ( | ) | const |
Test whether this is the identity permutation, that is, the permutation that maps everything to itself.
Definition at line 167 of file Permutation.cpp.
Permutation composition, that is, post-multiplication by a permutation.
| p | A permutation. |
Definition at line 255 of file Permutation.cpp.
Perform a deep copy of a permutation.
| p | A permutation. |
Definition at line 214 of file Permutation.cpp.
| uint8_t CPerm::operator[] | ( | uint8_t | n | ) | const |
Reader function for the map.
| n | Index into map. |
Definition at line 206 of file Permutation.cpp.
| void CPerm::printmap | ( | ) | const |
Print the permutation map on one line as a list of comma-separated numbers.
Definition at line 183 of file Permutation.cpp.
| void CPerm::printnum | ( | ) | const |
Print the reverse lexicographic number as a hexadecimal string.
Definition at line 191 of file Permutation.cpp.
| void CPerm::Randomize | ( | uint64_t(*)(void) | rng | ) |
Use the Mersenne Twister to choose a pseudo-random permutation with a uniform distribution, that is, each permutation is equally likely.
| rng | An external random number generator to use as a seed. |
Definition at line 106 of file Permutation.cpp.
| void CPerm::Randomize | ( | uint32_t | s[] | ) |
Choose a pseudo-random permutation with a uniform distribution, that is, each permutation is equally likely. The parameter consists of an array of numbers that are assumed to be pseudorandom. It is also assumed that the array contains at least m_nSize numbers.
| s | An array of pseudorandom numbers. |
Definition at line 139 of file Permutation.cpp.
| void CPerm::RandomizeOdd | ( | uint64_t(*)(void) | rng | ) |
Use the Mersenne Twister to choose a pseudo-random odd permutation with a uniform distribution, that is, each odd permutation is equally likely.
| rng | An external random number generator to use as a seed. |
Definition at line 117 of file Permutation.cpp.
Test whether a pair of permutations are identical. Permutations are identical iff they are the same size and they have identical maps.
| p0 | A permutation. |
| p1 | A permutation. |
Definition at line 240 of file Permutation.cpp.
1.8.15