C++ Reference: class SparsePermutation

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.
Method
AddToCurrentCycle

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).

CloseCurrentCycle

Return type: void

Cycle

Return type: Iterator

Arguments: int i

DebugString

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)".

LastElementInCycle

Return type: int

Arguments: int i

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.

NumCycles

Return type: int

RemoveCycles

Return type: void

Arguments: const std::vector<int>& cycle_indices

Removes the cycles with given indices from the permutation. This works in O(K) for a permutation displacing K elements.

Size

Return type: int

TODO(user,user): complete the reader API.

SparsePermutation

Return type: explicit

Arguments: int size

Support

Return type: const std::vector<int>&

Returns the "support" of this permutation; that is, the set of elements displaced by it.