C++ Reference: permutation

This documentation is automatically generated.

Classes for permuting indexable, ordered containers of data without depending on that data to be accessible in any particular way. The client needs to give us two things: 1. a permutation to apply to some container(s) of data, and 2. a description of how to move data around in the container(s).

The permutation (1) comes to us in the form of an array argument to PermutationApplier::Apply(), along with index values that tell us where in that array the permutation of interest lies. Typically those index values will span the entire array that describes the permutation.

Applying a permutation involves decomposing the permutation into disjoint cycles and walking each element of the underlying data one step around the unique cycle in which it participates. The decomposition into disjoint cycles is done implicitly on the fly as the code in PermutationApplier::Apply() advances through the array describing the permutation. As an important piece of bookkeeping to support the decomposition into cycles, the elements of the permutation array typically get modified somehow to indicate which ones have already been used.

At first glance, it would seem that if the containers are indexable, we don't need anything more complicated than just the permutation and the container of data we want to permute; it would seem we can just use the container's operator[] to retrieve and assign elements within the container. Unfortunately it's not so simple because the containers of interest can be indexable without providing any consistent way of accessing their contents that applies to all the containers of interest. For instance, if we could insist that every indexable container must define an lvalue operator[]() we could simply use that for the assignments we need to do while walking around cycles of the permutation. But we cannot insist on any such thing. To see why, consider the PackedArray class template in ortools/util/packed_array.h where operator[] is supplied for rvalues, but because each logical array element is packed across potentially multiple instances of the underlying data type that the C++ language knows about, there is no way to have a C++ reference to an element of a PackedArray. There are other such examples besides PackedArray, too. This is the main reason we need a codified description (2) of how to move data around in the indexable container. That description comes to us via the PermutationApplier constructor's argument which is a PermutationCycleHandler instance. Such an object has three important methods defined: SetTempFromIndex(), SetIndexFromIndex(), and SetIndexFromTemp(). Those methods embody all we need to know about how to move data in the indexable container(s) underlying the PermutationCycleHandler.

Another reason we need the description (2) of how to move elements around in the container(s) is that it is often important to permute side-by-side containers of elements according to the same permutation. This situation, too, is covered by defining a PermutationCycleHandler that knows about multiple underlying indexable containers.

The above-mentioned PermutationCycleHandler methods embody knowledge of how to assign elements. It happens that PermutationCycleHandler is also a convenient place to embody the knowledge of how to keep track of which permutation elements have been consumed by the process of walking data around cycles. We depend on the PermutationCycleHandler instance we're given to define SetSeen() and Unseen() methods for that purpose.

For the common case in which elements can be accessed using operator[](), we provide the class template ArrayIndexCycleHandler.

Classes

ArrayIndexCycleHandler
PermutationApplier
PermutationCycleHandler

Send feedback about...