//////////////////////////////////////////////////////////////////////
//
// Compile options needed: /GX
//
// next_permutation.cpp : Illustrates how to use the
//                        next_permutation function.
//
// Functions:
//
//    next_permutation : Change the order of the sequence to the
//                       next lexicograhic permutation.
//////////////////////////////////////////////////////////////////////

// disable warning C4786: symbol greater than 255 character,
// okay to ignore
#pragma warning(disable: 4786)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std ;

char sta[8];
int top = 0;

int push(char c)
{
	if(top < 8)
	{
		sta[top] = c;
		top++;
		return 0;
	}
	return 1;
}



int empty()
{
	if(top <= 0)
		return 1;
	else
		return 0;
}

char pop()
{
	if(!empty())
	{
		top--;
		return sta[top];
	}
	else
		return 'v';
}

void main()
{
    const int VECTOR_SIZE = 7 ;
	char str[8] = "macbeth";

    // Define a template class vector of strings
    typedef vector<string> StrVector ;

    //Define an iterator for template class vector of strings
    typedef StrVector::iterator StrVectorIt ;

    //Define an ostream iterator for strings
    typedef ostream_iterator<string> StrOstreamIt;

    StrVector Pattern(VECTOR_SIZE) ;

    StrVectorIt start, end, it ;

    StrOstreamIt outIt(cout, " ") ;

    start = Pattern.begin() ;   // location of first
                                      // element of Pattern

    end = Pattern.end() ;       // one past the location last
                                       // element of Pattern

    int count = 0;
	//Initialize vector Pattern
    Pattern[0] = "m" ;
    Pattern[1] = "a" ;
    Pattern[2] = "c" ;
	Pattern[3] = "b" ;
	Pattern[4] = "e" ;
	Pattern[5] = "t" ;
	Pattern[6] = "h" ;

    // print content of Pattern
    cout << "Before calling next_permutation...\n" << "Pattern: " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << "\n\n" ;

    // Generate all possible permutations

    cout << "After calling next_permutation...." << endl ;
    while ( next_permutation(start, end) )
    {
        copy(start, end, outIt) ;

		char temp;
		for(int i = 0;i < 8;i++)
		{
			if(str[i] != StrVector::at(i))
			{
				if((temp = pop()) != str[i])
				{
					push(temp);
					push(str[i]);
				}
			}
		}

		if(empty())
			count++;

        cout << endl ;
    }
	cout << count;
}