Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class SparsePermutation
Note: This documentation is automatically generated.
A compact representation for permutations of {0..N-1} that displaces few
elements: it needs only O(K) memory for a permutation that displaces
K elements.
To add a cycle to the permutation, repeatedly call AddToCurrentCycle()
with the cycle's orbit, then call CloseCurrentCycle();
This shouldn't be called on trivial cycles (of length 1).
Output all non-identity cycles of the permutation, sorted
lexicographically (each cycle is described starting by its smallest
element; and all cycles are sorted lexicographically against each other).
This isn't efficient; use for debugging only.
Example: "(1 4 3) (5 9) (6 8 7)".
This is useful for iterating over the pair {element, image}
of a permutation:
for (int c = 0; c < perm.NumCycles(); ++c) {
int element = LastElementInCycle(c);
for (int image : perm.Cycle(c)) {
// The pair is (element, image).
...
element = image;
}
}
TODO(user): Provide a full iterator for this? Note that we have more
information with the loop above. Not sure it is needed though.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["`SparsePermutation` is a compact representation for permutations, needing only O(K) memory for a permutation that displaces K elements."],["It provides methods for adding, closing, and removing cycles within the permutation."],["Users can access information like the number of cycles, support (displaced elements), and debug strings."],["Iteration functionalities are available to traverse cycles and elements, although full iterator support is still under consideration."]]],["The `SparsePermutation` class represents permutations of elements, efficiently storing those that displace few elements. Key actions include constructing a permutation with `SparsePermutation`, adding cycles via `AddToCurrentCycle` and `CloseCurrentCycle`. One can iterate through the cycles with `Cycle` and identify the last element within a cycle using `LastElementInCycle`. The number of cycles and the size can be obtained via `NumCycles` and `Size`. `Support` lists displaced elements, and cycles can be removed via `RemoveCycles`. `DebugString` provides a readable output of non-identity cycles.\n"]]
