C++ Reference

C++ Reference: Algorithms

sparse_permutation.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_ALGORITHMS_SPARSE_PERMUTATION_H_
15#define OR_TOOLS_ALGORITHMS_SPARSE_PERMUTATION_H_
16
17#include <string>
18#include <vector>
19
20#include "ortools/base/logging.h"
21
22namespace operations_research {
23
24// A compact representation for permutations of {0..N-1} that displaces few
25// elements: it needs only O(K) memory for a permutation that displaces
26// K elements.
28 public:
29 explicit SparsePermutation(int size) : size_(size) {} // Identity.
30
31 // TODO(user,user): complete the reader API.
32 int Size() const { return size_; }
33 int NumCycles() const { return cycle_ends_.size(); }
34
35 // Returns the "support" of this permutation; that is, the set of elements
36 // displaced by it.
37 const std::vector<int>& Support() const { return cycles_; }
38
39 // The permutation has NumCycles() cycles numbered 0 .. NumCycles()-1.
40 // To iterate over cycle #i of the permutation, do this:
41 // for (const int e : permutation.Cycle(i)) { ...
42 struct Iterator;
43 Iterator Cycle(int i) const;
44
45 // This is useful for iterating over the pair {element, image}
46 // of a permutation:
47 //
48 // for (int c = 0; c < perm.NumCycles(); ++c) {
49 // int element = LastElementInCycle(c);
50 // for (int image : perm.Cycle(c)) {
51 // // The pair is (element, image).
52 // ...
53 // element = image;
54 // }
55 // }
56 //
57 // TODO(user): Provide a full iterator for this? Note that we have more
58 // information with the loop above. Not sure it is needed though.
59 int LastElementInCycle(int i) const;
60
61 // To add a cycle to the permutation, repeatedly call AddToCurrentCycle()
62 // with the cycle's orbit, then call CloseCurrentCycle();
63 // This shouldn't be called on trivial cycles (of length 1).
64 void AddToCurrentCycle(int x);
65 void CloseCurrentCycle();
66
67 // Removes the cycles with given indices from the permutation. This
68 // works in O(K) for a permutation displacing K elements.
69 void RemoveCycles(const std::vector<int>& cycle_indices);
70
71 // Output all non-identity cycles of the permutation, sorted
72 // lexicographically (each cycle is described starting by its smallest
73 // element; and all cycles are sorted lexicographically against each other).
74 // This isn't efficient; use for debugging only.
75 // Example: "(1 4 3) (5 9) (6 8 7)".
76 std::string DebugString() const;
77
78 private:
79 const int size_;
80 std::vector<int> cycles_;
81 std::vector<int> cycle_ends_;
82};
83
85 DCHECK_GE(x, 0);
86 DCHECK_LT(x, size_);
87 cycles_.push_back(x);
88}
89
91 if (cycle_ends_.empty()) {
92 DCHECK_GE(cycles_.size(), 2);
93 } else {
94 DCHECK_GE(cycles_.size(), cycle_ends_.back() + 2);
95 }
96 cycle_ends_.push_back(cycles_.size());
97}
98
100 // These typedefs allow this iterator to be used within testing::ElementsAre.
101 typedef int value_type;
102 typedef std::vector<int>::const_iterator const_iterator;
103
105 Iterator(const std::vector<int>::const_iterator& b,
106 const std::vector<int>::const_iterator& e)
107 : begin_(b), end_(e) {}
108
109 std::vector<int>::const_iterator begin() const { return begin_; }
110 std::vector<int>::const_iterator end() const { return end_; }
111 const std::vector<int>::const_iterator begin_;
112 const std::vector<int>::const_iterator end_;
113
114 int size() const { return end_ - begin_; }
115};
116
118 DCHECK_GE(i, 0);
119 DCHECK_LT(i, NumCycles());
120 return Iterator(cycles_.begin() + (i == 0 ? 0 : cycle_ends_[i - 1]),
121 cycles_.begin() + cycle_ends_[i]);
122}
123
125 DCHECK_GE(i, 0);
126 DCHECK_LT(i, cycle_ends_.size());
127 DCHECK_GT(cycle_ends_[i], i == 0 ? 0 : cycle_ends_[i - 1]);
128 return cycles_[cycle_ends_[i] - 1];
129}
130
131} // namespace operations_research
132
133#endif // OR_TOOLS_ALGORITHMS_SPARSE_PERMUTATION_H_
const std::vector< int > & Support() const
void RemoveCycles(const std::vector< int > &cycle_indices)
Iterator(const std::vector< int >::const_iterator &b, const std::vector< int >::const_iterator &e)
std::vector< int >::const_iterator end() const
const std::vector< int >::const_iterator end_
std::vector< int >::const_iterator const_iterator
std::vector< int >::const_iterator begin() const
const std::vector< int >::const_iterator begin_