#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>

using namespace std;

vector< vector<int> > perms;
list<int> start;
list<int> rest;
void generatePermutations()
{
	int nLeft = rest.size();
	if(nLeft == 0)
	{
		vector<int> perm;
		for(int i = 0; i < start.size(); i++)
		{
			perm.push_back(start.front());
			start.push_back(start.front());
			start.pop_front();
		}
		perms.push_back(perm);
		return;
	}
	
	for(int i = 0; i < nLeft; i++)
	{
		start.push_back(rest.front());
		rest.pop_front();
		generatePermutations();
		rest.push_back(start.back());
		start.pop_back();
	}
	
}

void generatePermutations(int numElems)
{
	for(int i = 0; i < numElems; i++)
		rest.push_back(i);	
	generatePermutations();
}

void inline swap(int & a, int & b)
{
	int temp = a;
	a = b;
	b = temp;
}

void populateGraph(vector< vector<bool> > &graph)
{
	for(int i = 0; i < perms.size(); i++)
	{
		vector<int> possibility;
		for(int j = 0; j < perms[i].size(); j++)
			possibility.push_back(perms[i][j]);
		
		// find the zero
		int zeroIdx = 0;
		for(int j = 0; j < possibility.size(); j++)
		{
			if(possibility[j] == 0)
			{
				zeroIdx = j;
				//cout << i << ": zeroIdx = " << zeroIdx << endl;
				break;
			}
		}
		
		// shift zero left
		if(zeroIdx > 0)
		{
			swap(possibility[zeroIdx], possibility[zeroIdx - 1]);
			for(int j = 0; j < perms.size(); j++)
				if(possibility == perms[j])
					graph[i][j] = true;
			swap(possibility[zeroIdx], possibility[zeroIdx - 1]);
		}
		
		// shift zero right
		if(zeroIdx < possibility.size() - 1)
		{
			swap(possibility[zeroIdx], possibility[zeroIdx + 1]);
			for(int j = 0; j < perms.size(); j++)
				if(possibility == perms[j])
					graph[i][j] = true;
			swap(possibility[zeroIdx], possibility[zeroIdx + 1]);
		}
		
		// jump zero left
		if(zeroIdx > 1)
		{
			swap(possibility[zeroIdx], possibility[zeroIdx - 2]);
			for(int j = 0; j < perms.size(); j++)
				if(possibility == perms[j])
					graph[i][j] = true;
			swap(possibility[zeroIdx], possibility[zeroIdx - 2]);
		}
		
		// jump zero right
		if(zeroIdx < possibility.size() - 2)
		{
			swap(possibility[zeroIdx], possibility[zeroIdx + 2]);
			for(int j = 0; j < perms.size(); j++)
				if(possibility == perms[j])
					graph[i][j] = true;
			swap(possibility[zeroIdx], possibility[zeroIdx + 2]);	
		}
	}
}

int main(int argc, char *argv[])
{
	if(argc != 2)
	{
		cout << "Usage: " << argv[0] << " <number of spaces>" << endl;
		exit(0);
	}
	
	int numElems = atoi(argv[1]);
	//cout << "Number of spaces: " << numElems << endl;
	cout << "digraph \"frogs\" {" << endl;
	// generate permutations
	generatePermutations(numElems);
	
	// print state
	for(int i = 0; i < perms.size(); i++)
	{
		cout << "// " << i << ": ";
		for(int j = 0; j < perms[i].size(); j++)
			cout << perms[i][j] << ' ';
		cout << endl;
	}
	
	// init graph
	int const numPerms = perms.size();
	vector< vector<bool> > graph;
	for(int i = 0; i < numPerms; i++)
	{
		vector<bool> row(numPerms, false);
		graph.push_back(row);
	}
	
	/*
	// print graph
	for(int i = 0; i < numPerms; i++)
	{
		for(int j = 0; j < numPerms; j++)
			cout << (graph[i][j] ? 1 : 0) << ' ';
		cout << endl;
	}
	*/
	
	// populate graph
	populateGraph(graph);
	
	/*
	// print graph
	cout << endl;
	for(int i = 0; i < numPerms; i++)
	{
		for(int j = 0; j < numPerms; j++)
			cout << (graph[i][j] ? 1 : 0) << ' ';
		cout << endl;
	}
	*/
	 
	// print graphviz graph
	cout << endl;
	for(int i = 0; i < numPerms; i++)
	{
		for(int j = i; j < numPerms; j++)
		{
			if(!graph[i][j])
				continue;
			
			// print start
			cout << "\"";
			for(int k = 0; k < perms[i].size(); k++)
				cout << perms[i][k];
			cout << "\"";
			
			// print arrow
			cout << " -> ";
			
			// print end
			cout << "\"";
			for(int k = 0; k < perms[j].size(); k++)
				cout << perms[j][k];
			cout << "\"";
			
			// add attribute
			cout << " [dir=both] ";
			
			// finish with semicolon
			cout << ';' << endl;
		}
	}
	cout << "}" << endl;
	
	// exit
	return 0;
}