#include "stdafx.h"
#include <omp.h>
#include <iostream>
#include <stdlib.h>

using namespace std;

#define size 20
typedef int tab2[size][size], tab1[size];
#define random()    (float)rand()/(float)RAND_MAX

void gnp(int n, float p, tab2 A)
{
	int i, j;

	for (i = 0; i < n - 1; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			A[i][j] = A[j][i] = (random() <= p);
		}
	}

	for (i = 0; i < n; i++)
	{
		A[i][i] = 0;
	}

	for (i = 0; i < n - 1; i++)
	{
		for (j =0; j < n; j++)
		{
			cout << A[i][j] << " ";
		}
		cout << endl;
	}
}

void permInit(int n, tab1 p)
{
	int i;
	for (i = 0; i < n; i++)
	{
		p[i] = i;
	}
}


int permNext(int n, tab1 p)
{
	int i, j, x, b;
	b = 0;

	i = n - 1;

	while (i>0) {
		if (p[i]>p[i - 1]) {
			j = n - 1;
			while (p[j] < p[i - 1]) j--;
			x = p[j]; p[j] = p[i - 1]; p[i - 1] = x;
			while (i<n) {
				x = p[i]; p[i] = p[n - 1]; p[n - 1] = x;
				i++; n--;
			};
			b = 1;
			break;
		}
		i--;
	}
	return b;
}

int differ(int n, tab2 A, tab1 perm)
{

	int dist, best = 1;
	int i, j;
	for (i = 0; i<n - 1; i++)
		for (j = i + 1; j<n; j++) if (A[i][j])
		{
			dist = abs(perm[i] - perm[j]);
			if (dist>best) best = dist;
		}
	return best;
}

int _tmain(int argc, _TCHAR* argv[])
{
	tab2 A;
	tab1 perm;
	float p = 0.5;
	int n = 5;
	int g_diff, width;
	int L = 1;

	gnp(n, p, A);
	width = n - 1;

	permInit(n, perm);
	omp_lock_t lck1;
	omp_init_lock(&lck1);

#pragma omp parallel
	{
		do {
			g_diff = differ(n, A, perm);
			omp_set_lock(&lck1);
			if (g_diff < width) width = g_diff;
			omp_unset_lock(&lck1);
			L++;
		}
		while (permNext(n, perm));
	}

	return 0;
}