operations_research::SparsePermutation Class Reference

#include <sparse_permutation.h>

Classes
struct	Iterator

Public Member Functions
	SparsePermutation (int size)
int	Size () const
int	NumCycles () const
const std::vector< int > &	Support () const
Iterator	Cycle (int i) const
int	LastElementInCycle (int i) const
int	Image (int element) const
int	InverseImage (int element) const
void	AddToCurrentCycle (int x)
void	CloseCurrentCycle ()
void	RemoveCycles (absl::Span< const int > cycle_indices)
std::string	DebugString () const
template<typename Collection>
void	ApplyToDenseCollection (Collection &span) const

Detailed Description

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.

Definition at line 28 of file sparse_permutation.h.

Constructor & Destructor Documentation

SparsePermutation()

operations_research::SparsePermutation::SparsePermutation ( int size )

inlineexplicit

Definition at line 30 of file sparse_permutation.h.

Member Function Documentation

AddToCurrentCycle()

void operations_research::SparsePermutation::AddToCurrentCycle ( int x )

inline

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

Definition at line 93 of file sparse_permutation.h.

ApplyToDenseCollection()

template<typename Collection>

void operations_research::SparsePermutation::ApplyToDenseCollection

(

Collection &

span

)

const

Definition at line 141 of file sparse_permutation.h.

CloseCurrentCycle()

void operations_research::SparsePermutation::CloseCurrentCycle ( )

inline

Definition at line 99 of file sparse_permutation.h.

Cycle()

SparsePermutation::Iterator operations_research::SparsePermutation::Cycle ( int i ) const

inline

Definition at line 126 of file sparse_permutation.h.

DebugString()

std::string operations_research::SparsePermutation::DebugString

(

)

const

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

Find the minimum.

Definition at line 56 of file sparse_permutation.cc.

Image()

int operations_research::SparsePermutation::Image

(

int

element

)

const

Returns the image of the given element or element itself if it is stable under the permutation.

Definition at line 84 of file sparse_permutation.cc.

InverseImage()

int operations_research::SparsePermutation::InverseImage

(

int

element

)

const

Definition at line 97 of file sparse_permutation.cc.

LastElementInCycle()

int operations_research::SparsePermutation::LastElementInCycle ( int i ) const

inline

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.

Definition at line 133 of file sparse_permutation.h.

NumCycles()

int operations_research::SparsePermutation::NumCycles ( ) const

inline

Definition at line 34 of file sparse_permutation.h.

RemoveCycles()

void operations_research::SparsePermutation::RemoveCycles

(

absl::Span< const int >

cycle_indices

)

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

Todo

(user): make this a class member to avoid allocation if the complexity becomes an issue. In this case, also optimize the loop below by not copying the first cycles.

Definition at line 27 of file sparse_permutation.cc.

Size()

int operations_research::SparsePermutation::Size ( ) const

inline

Todo

(user): complete the reader API.

Definition at line 33 of file sparse_permutation.h.

Support()

const std::vector< int > & operations_research::SparsePermutation::Support ( ) const

inline

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

Definition at line 38 of file sparse_permutation.h.

---

The documentation for this class was generated from the following files:

• ortools/algorithms/sparse_permutation.h
• ortools/algorithms/sparse_permutation.cc