Created
February 2, 2011 16:50
-
-
Save klynch/807973 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template<class T> struct NullFunctor { boolean operator()(const std::vector<T>& perm) { return FALSE; } }; | |
//! Iterator to generate all permutations of a list. A functor can be specified for fast culling of entire subtrees of undesired permutations. | |
/** | |
* The permuations are in lexicographic order. ie. {1,2,3} , {1,3,2} , {2,1,3} , {2,3,1} , {3,1,2} , {3,2,1} | |
* The current permutation list can be accessed with the dereference/pointer operators. | |
* | |
* If a functor is provided then undesired subtrees can be culled. The functor must provide this function: | |
* | |
* boolean operator()(const std::vector<T>& perm) | |
* | |
* When an iter is stepped (++), its functor will be called before traversing each permutation subtree. | |
* For example, 'perm' will first contain {1}, if the functor returns true then the next test is {1,2}, then finally {1,2,3}. | |
* When the functor returns true for a full permutation (ex. {1,2,3}), then the iter step is complete. | |
* | |
* Copies of the iter share its permutation state, so a change to one iter affects all others. | |
* | |
* | |
* Note: RefObj and RefPtr is a non-intrusive smart pointer implementation, code not provided here. | |
* GammaFunc::Factorial is just the N! factorial function, code not provided here. | |
* | |
* The core algorithm and even the iterator can work without the missing classes/functions (just remove all references to them) | |
* | |
* The algorithm is "Lexicographic Permutations with Restricted Prefixes" from Dr. Knuth's "The Art of Computer Programming", Vol 4, Section 7.2.1.2 | |
*/ | |
template<class T, class Functor = NullFunctor<T>> | |
class PermuteIter | |
{ | |
struct State : public RefObj | |
{ | |
State(const std::vector<T>& list) : list(list), bFunc(FALSE), iCount(0), iCountMax(0), k(-1), n(0) {} | |
State(const std::vector<T>& list, Functor func) : list(list), bFunc(TRUE), func(func), iCount(0), iCountMax(0), k(-1), n(0) {} | |
const std::vector<T>& list; | |
boolean bFunc; | |
Functor func; | |
std::vector<T> perm; | |
int64 iCount; | |
int64 iCountMax; | |
std::vector<int32> a; | |
std::vector<int32> l; | |
std::vector<int32> u; | |
int32 p; | |
int32 q; | |
int32 k; | |
int32 n; | |
}; | |
public: | |
typedef std::forward_iterator_tag iterator_category; | |
typedef const std::vector<T> value_type; | |
typedef ptrdiff_t difference_type; | |
typedef const std::vector<T>* pointer; | |
typedef const std::vector<T>& reference; | |
PermuteIter() {} | |
PermuteIter(RefPtr<State> pState); | |
PermuteIter(const PermuteIter& it) { operator=(it); } | |
PermuteIter& operator++(); | |
PermuteIter& operator+=(int32 rhs) { for (int32 i = 0; i < rhs; ++i) ++*this; return *this; } | |
bool operator==(const PermuteIter& rhs) const; | |
bool operator!=(const PermuteIter& rhs) const { return !operator==(rhs); } | |
//! Get current permutation list | |
std::vector<T>& operator*() const { return m_ps->perm; } | |
std::vector<T>* operator->() const { return &m_ps->perm; } | |
//! Get current permutation number. Every perm has a unique associated number: the first perm is 1, the last perm is GetCountMax() | |
int64 GetCount() const { return m_ps->iCount; } | |
//! Get total number of permutations for this list | |
int64 GetCountMax() const { return m_ps->iCountMax; } | |
private: | |
boolean IsEnd() const { return m_ps == NULL; } | |
RefPtr<State> m_ps; | |
}; | |
template<class T, class Functor> | |
PermuteIter<T,Functor>::PermuteIter(RefPtr<State> pState) : m_ps(pState) | |
{ | |
if (IsEnd() || m_ps->list.size() == 0) | |
return; | |
m_ps->n = m_ps->list.size(); | |
m_ps->iCountMax = GammaFuncT<Double>::Factorial(m_ps->n); | |
m_ps->iCount = 0; | |
m_ps->a.resize(m_ps->n+1, -1); | |
m_ps->l.resize(m_ps->n+1, -1); | |
m_ps->u.resize(m_ps->n+1, -1); | |
for (int32 i = 0; i < m_ps->n; ++i) | |
m_ps->l[i] = i+1; | |
m_ps->l[m_ps->n] = 0; | |
m_ps->k = 1; | |
//Init level k | |
m_ps->p = 0; | |
m_ps->q = m_ps->l[0]; | |
operator++(); | |
} | |
template<class T, class Functor> | |
PermuteIter<T,Functor>& PermuteIter<T,Functor>::operator++() | |
{ | |
if (m_ps->k <= 0) | |
{ | |
if (m_ps->k == 0) | |
--m_ps->k; //Put iterator into end state | |
return *this; | |
} | |
while(1) | |
{ | |
//Call functor to test for level k culling | |
boolean bVisit = FALSE; | |
boolean bFunc = TRUE; | |
m_ps->a[m_ps->k] = m_ps->q; | |
//Only call functor if we're using one, otherwise assume it returned true | |
if (m_ps->bFunc) | |
{ | |
//Build permutation up to level k | |
m_ps->perm.clear(); | |
for (int32 i = 1; i <= m_ps->k; ++i) | |
m_ps->perm.push_back(m_ps->list[m_ps->a[i]-1]); | |
//Call functor for cull test | |
bFunc = m_ps->func(const_cast<const std::vector<T>&>(m_ps->perm)); | |
} | |
if (bFunc && m_ps->k < m_ps->n) | |
{ | |
//Functor true, not full permutation. Advance and init level k | |
m_ps->u[m_ps->k] = m_ps->p; | |
m_ps->l[m_ps->p] = m_ps->l[m_ps->q]; | |
++m_ps->k; | |
m_ps->p = 0; | |
m_ps->q = m_ps->l[0]; | |
continue; | |
} | |
else if (bFunc) | |
{ | |
//Functor true, full permutation. Visit | |
bVisit = TRUE; | |
m_ps->iCount++; | |
//If we're using a functor then the full permutation has already been built and is ready for visiting | |
if (!m_ps->bFunc) | |
{ | |
m_ps->perm.clear(); | |
for (int32 i = 1; i <= m_ps->k; ++i) | |
m_ps->perm.push_back(m_ps->list[m_ps->a[i]-1]); | |
} | |
} | |
else | |
{ | |
//Functor false, skip subtree. Increase a[k] | |
m_ps->p = m_ps->q; | |
m_ps->q = m_ps->l[m_ps->p]; | |
m_ps->iCount = m_ps->iCount + GammaFuncT<Double>::Factorial(m_ps->n - m_ps->k); | |
if (m_ps->q != 0) | |
continue; | |
} | |
while (1) | |
{ | |
//Fallback levels. Decrease k | |
--m_ps->k; | |
if (m_ps->k <= 0) | |
return *this; | |
m_ps->p = m_ps->u[m_ps->k]; | |
m_ps->q = m_ps->a[m_ps->k]; | |
m_ps->l[m_ps->p] = m_ps->q; | |
//Increase a[k] | |
m_ps->p = m_ps->q; | |
m_ps->q = m_ps->l[m_ps->p]; | |
if (m_ps->q != 0) | |
break; | |
} | |
if (bVisit) | |
break; | |
} | |
return *this; | |
} | |
template<class T, class Functor> | |
bool PermuteIter<T,Functor>::operator==(const PermuteIter& rhs) const | |
{ | |
if (!IsEnd() && !rhs.IsEnd()) | |
return m_ps == rhs.m_ps; | |
if (IsEnd() && rhs.IsEnd()) | |
return TRUE; | |
//Comparing to end, check if done | |
const PermuteIter& it = IsEnd() ? rhs : *this; | |
return it.m_ps->k < 0; | |
} | |
//! Get permutation begin iterator | |
template<class T, class Functor> | |
PermuteIter<T, Functor> PermuteBegin(const std::vector<T>& list, Functor func) { return PermuteIter<T,Functor>(new PermuteIter<T,Functor>::State(list, func)); } | |
//! Get permutation begin iterator without culling functor | |
template<class T> | |
PermuteIter<T> PermuteBegin(const std::vector<T>& list) { return PermuteIter<T>(new PermuteIter<T>::State(list)); } | |
//! Provides an end condition so iteration stops when all permutations have been generated. | |
template<class T, class Functor> | |
PermuteIter<T, Functor> PermuteEnd(const std::vector<T>& list, Functor func) { return PermuteIter<T,Functor>(NULL); } | |
//! Get permutation end iterator without culling functor | |
template<class T> | |
PermuteIter<T> PermuteEnd(const std::vector<T>& list) { return PermuteIter<T>(NULL); } | |
//Here's a usage example without culling functor: | |
std::vector<Real> list; | |
list.push_back(1); | |
list.push_back(2); | |
list.push_back(3); | |
list.push_back(4); | |
for (PermuteIter<Real> it = PermuteBegin(list); it != PermuteEnd(list); ++it) | |
{ | |
Debug::Print("Perm: "); | |
for (int32 i = 0; i < UTOS(it->size()); ++i) | |
Debug::Print(StringStream() << it->at(i) << " "); | |
Debug::Print(StringStream() << " ; Cnt: " << it.GetCount() << "\n"); | |
} | |
//Here's a usage example with culling functor: | |
struct Functor | |
{ | |
boolean operator()(const std::vector<Real>& perm) | |
{ | |
if (perm.size() == 2 && perm[0] == 1 && perm[1] == 4) | |
return FALSE; | |
if (perm.size() == 2 && perm[0] == 2 && perm[1] == 3) | |
return FALSE; | |
if (perm.size() == 3 && perm[0] == 2 && perm[1] == 4 && perm[2] == 3) | |
return FALSE; | |
if (perm.size() == 3 && perm[0] == 4 && perm[1] == 3 && perm[2] == 1) | |
return FALSE; | |
return TRUE; | |
} | |
}; | |
for (PermuteIter<Real, Functor> it = PermuteBegin(list, Functor()); it != PermuteEnd(list, Functor()); ++it) | |
{ | |
Debug::Print("Perm: "); | |
for (int32 i = 0; i < UTOS(it->size()); ++i) | |
Debug::Print(StringStream() << it->at(i) << " "); | |
Debug::Print(StringStream() << " ; Cnt: " << it.GetCount() << "\n"); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment