permuter.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include "permuter.h"


void Permuter::Swap(int x1, int x2)
// post: myList[x1] and myList[x2] swapped
{
    int temp = myList[x1];
    myList[x1] = myList[x2];
    myList[x2] = temp;
}

void Permuter::Reverse(int first, int last)
// post: myList[first..last] reversed
{
    while (first < last)
    {   Swap(first,last);
        first++;
        last--;
    }
}

Permuter::Permuter(const tvector<int>& list)
  : myList(list),
    myOriginal(list),
    myFirst(false)
{

}

void Permuter::Init()
{
    myList = myOriginal;  
    myFirst = true;
}

bool Permuter::HasMore()
// post: returns false iff myList == myFirst
//       so that all permutations generated
{
    if (! myFirst)
    {   int k;
        for(k=0; k < myList.size(); k++)
        {  if (myList[k] != myOriginal[k])
           {   return true;
           }
        }
        return false;
    }
    myFirst = false;
    return true;
}

void Permuter::Current(tvector<int>& list)
{
    list = myList;
}

void Permuter::Next()
{
    int curr = myList.size()-1;  // rightmost index
    while (true)
    {   int beforecurr = curr-1;
        if (myList[beforecurr] < myList[curr])
        {   // find rightmost entry that's larger than beforecurr
            // we know that curr is larger, so loop must terminate
            int lastBig = myList.size()-1;
            while (! (myList[beforecurr] < myList[lastBig]) )
            {   lastBig--;
            }
            Swap(beforecurr,lastBig);
            Reverse(curr,myList.size()-1);
            break; // out of outer while
        } 
        curr--;
        if (curr == 0)     // it's sorted, so reverse and keep going
        {   Reverse(0,myList.size()-1);
            break; // out of outer while
        }
    }
}