1 #ifndef UTILS_PERMUTATION_H 2 #define UTILS_PERMUTATION_H 5 #include <KrisLibrary/errors.h> 18 inline void IdentityPermutation(
int v[],
int n)
20 for(
int i=0;i<n;i++) v[i]=i;
24 inline void RandomlyPermute(T v[],
int n)
26 for(
int i=0;i<n;i++) {
32 inline void RandomPermutation(
int v[],
int n)
34 IdentityPermutation(v,n);
38 inline void IdentityPermutation(std::vector<int>& v)
41 for(
int i=0;i<n;i++) v[i]=i;
45 inline void RandomlyPermute(std::vector<T>& v)
48 for(
int i=0;i<n;i++) {
54 inline void RandomPermutation(std::vector<int>& v)
56 IdentityPermutation(v);
61 inline void FirstPermutation(
int v[],
int k,
int n)
63 for(
int i=0;i<k;i++) v[i]=0;
66 inline void FirstPermutation(std::vector<int>& v,
int n)
68 std::fill(v.begin(),v.end(),0);
71 inline void LastPermutation(
int v[],
int k,
int n)
73 for(
int i=0;i<k;i++) v[i]=n-1;
76 inline void LastPermutation(std::vector<int>& v,
int n)
78 std::fill(v.begin(),v.end(),n-1);
86 for(
int i=k-1;i>=0;i--) {
99 for(
int i=k-1;i>=0;i--) {
101 if(v[i] >= n) v[i]=0;
111 for(
int i=k-1;i>=0;i--) {
113 if(v[i] < 0) v[i]=n-1;
124 for(
int i=k-1;i>=0;i--) {
126 if(v[i] < 0) v[i]=n-1;
138 inline Permutation(
int _n) :value(_n,0),n(_n),numCycles(0) {}
139 inline Permutation(
int _k,
int _n) :value(_k,0),n(_n),numCycles(0) {}
144 inline const Permutation& operator ++(
int) {
return operator ++(); }
149 inline const Permutation& operator --(
int) {
return operator --(); }
150 inline int cycleCount()
const {
return numCycles; }
151 inline bool isDone()
const {
return numCycles>0; }
152 inline const std::vector<int>& operator*()
const {
return value; }
153 inline const std::vector<int>* operator ->()
const {
return &value; }
157 numCycles = c.numCycles;
160 inline bool operator == (
const Permutation& c)
const {
return n == c.n && numCycles == c.numCycles && value == c.value; }
161 inline bool operator < (
const Permutation& c)
const {
163 if(numCycles < c.numCycles)
return true;
164 else if(numCycles > c.numCycles)
return false;
165 return std::lexicographical_compare(value.begin(),value.end(),c.value.begin(),c.value.end());
169 std::vector<int> value;
A class that enumerates permutations.
Definition: permutation.h:135
int NextPermutation(int v[], int k, int n)
Definition: permutation.h:84
int PrevPermutation(int v[], int k, int n)
Definition: permutation.h:109