#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <queue>
#include <QueueWithTwoStacks.h>

#define max_br 26

using namespace std;

bool word[max_br];

struct letters_container
{
	char letters[max_br];
} temp;

queue<letters_container> m_queue;//queue that contains strings(char arrays)

bool print(long K, int N)
{
	long nom;
	int i,j,sum;
	nom=1;
	while (!m_queue.empty())
	{
		temp = m_queue.front();//next element in the queue
		cout<< nom << ": " << temp.letters << endl;
		if ( nom == K )
		{
			sum = 0;
			//Checks the number of inversions in the permutation. Parity of this count
			//determines the parity of that particular permutation
			for (i=0;i<N-1;i++)
			{
				for (j=i+1;j<N;j++)
				{
					if (temp.letters[i]>temp.letters[j]) sum++;
				}
			}
         }
    m_queue.pop();
    nom++;
  }
  cout<<"Inversions sum for this combination "<<sum<<endl;
  return sum%2;
}

void permutation(int i, int N)
{
	int j;
	if (i > N)
	{
		m_queue.push(temp); //Pushes the next permutation
		return;
	}//Recursion bottom
	for (j = 0; j < N; j++)
	{
		if (!word[j])
		{
			word[j] = 1;
			temp.letters[i] = j+'A';//The letters are ABC...Z
			permutation(i+1,N); //recursive call
			word[j] = 0;
		}
	}
}

int main()
{
	int i,N;
	long long P;
	bool odd;

	cout<<"Enter number of letters: ";cin>>N;
	cout<<"Which permutation to check: ";cin>>P;
	for (i = 0; i< N; i++)
	{
		word[i] = 0;
	}//initial initialization
	cout<<"Generate all permutations:\n";
	permutation(0,N);//generates all the permutations
	odd=print(P,N);//output the queue elements
	cout<<"Permutation "<<P<< " is ";
	if (odd)
		cout<<"even\n";
	else
		cout<<"odd\n";
	system("pause");
	return 0;
}