Algorithm X

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");
}