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."],[[["\u003cp\u003e\u003ccode\u003eSparsePermutation\u003c/code\u003e is a compact representation for permutations, needing only O(K) memory for a permutation that displaces K elements.\u003c/p\u003e\n"],["\u003cp\u003eIt provides methods for adding, closing, and removing cycles within the permutation.\u003c/p\u003e\n"],["\u003cp\u003eUsers can access information like the number of cycles, support (displaced elements), and debug strings.\u003c/p\u003e\n"],["\u003cp\u003eIteration functionalities are available to traverse cycles and elements, although full iterator support is still under consideration.\u003c/p\u003e\n"]]],["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"],null,["# SparsePermutation\n\nC++ Reference: class SparsePermutation\n======================================\n\n\nNote: This documentation is automatically generated.\nA 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.\n\n| Method ||\n|------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [`AddToCurrentCycle`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L64) | Return type: `void ` Arguments: `int x` 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). |\n| [`CloseCurrentCycle`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L65) | Return type: `void ` \u003cbr /\u003e |\n| [`Cycle`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L43) | Return type: `Iterator ` Arguments: `int i` \u003cbr /\u003e |\n| [`DebugString`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L76) | Return type: `std::string ` 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)\". |\n| [`LastElementInCycle`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L59) | Return type: `int ` Arguments: `int i` This is useful for iterating over the pair {element, image} of a permutation: for (int c = 0; c \\\u003c 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. |\n| [`NumCycles`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L33) | Return type: `int ` \u003cbr /\u003e |\n| [`RemoveCycles`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L69) | Return type: `void ` Arguments: `const std::vector\u003cint\u003e& cycle_indices` Removes the cycles with given indices from the permutation. This works in O(K) for a permutation displacing K elements. |\n| [`Size`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L32) | Return type: `int ` TODO(user): complete the reader API. |\n| [`SparsePermutation`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L29) | Return type: `explicit ` Arguments: `int size` \u003cbr /\u003e |\n| [`Support`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/sparse_permutation.h#L37) | Return type: `const std::vector\u003cint\u003e& ` Returns the \"support\" of this permutation; that is, the set of elements displaced by it. |"]]
