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
void	AddToCurrentCycle (int x)
void	CloseCurrentCycle ()
void	RemoveCycles (absl::Span< const int > cycle_indices)
std::string	DebugString () 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 85 of file sparse_permutation.h.

CloseCurrentCycle()

void operations_research::SparsePermutation::CloseCurrentCycle ( )

inline

Definition at line 91 of file sparse_permutation.h.

Cycle()

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

inline

Definition at line 118 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.

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 125 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